藍橋杯曆屆試題題解2

4月11日省賽，給自己加油！在bin神的交流群裡認識了一位鄭州輕工業學院的巨巨，可以面基了。。。一起去北京吧

國王的煩惱。前面連通的之後不連通的明顯的用并查集處理啊。。。但是是使用逆序的并查集，即為之後不連通的，過了一天之後加上這個橋就連通了那麼ans++。看看代碼就懂了的。。。逆序并查集用的很多的，還有帶權值并查集的使用。。食物鍊是個特别經典的題（當然也有不帶權值的巧妙做法）

const int maxn=10050;
const int maxm=100050;

int fa[maxn],n,m;

struct node{
	int u,v,day;
}edge[maxm];

int cmp(node a,node b){
	return a.day>b.day;
}

int getf(int x){
	if (x==fa[x]) return x;
	return fa[x]=getf(fa[x]);
}

int main(){
	//freopen("input.txt","r",stdin);
	int i,j,k;
	int day=0,ans=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].day);
		day=max(day,edge[i].day);
	}
	for(i=1;i<=n;i++) fa[i]=i;
	i=1;
	sort(edge+1,edge+m+1,cmp);
	while(day>0){
		while(edge[i].day==day){
			int u=getf(edge[i].u),v=getf(edge[i].v);
			if (u!=v){
				fa[u]=v;
				ans++;
				break;
			}
			else i++;
		}
		while(edge[i].day==day){
			int u=getf(edge[i].u),v=getf(edge[i].v);
			fa[u]=v;
			i++;
		}
		day--;
	}
	printf("%d\n",ans);
	return 0;
}
           

網址尋路：看到題就知道又是dfs。。。藍橋杯暴力方法萬歲！細節：層數已經固定好了，為3！另外，起點和終點可以是相同的要特殊判斷，而且vis數組不能修改标記

struct node{
	int to,next;
}edge[200050];

int n,m;
int tot=0,ans=0;
int head[100050];
int vis[100050];
int Print[10];

void addedge(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}

void print(){
	for(int i=0;i<=3;i++) printf("%d%c",Print[i],i==3?'\n':' ');
}

void dfs(int start,int pos,int num){
	if (num==4){
		ans++;
		//print();友善自己調試，看到完整的路徑過程 
		return;
	}
	int k;
	for(k=head[pos];k!=-1;k=edge[k].next){
		int v=edge[k].to;
		if (!vis[v]){
			vis[v]=1;
			Print[num]=v;
			dfs(start,v,num+1);
			vis[v]=0;
		}
		else if (v==start&&num==3){
			Print[num]=v;
			dfs(start,v,num+1);
			//跟上面的唯一差別是不用标記vis
			//因為已經判定過，下一步輸出而且這個點就是起點是以不會導緻死循環
			//而且vis也不能置0，置0會導緻1-2-1-2的情況出現
			// 
		}
	}
}

int main(){
	//freopen("input.txt","r",stdin);
	int i,j,k,u,v;
	memset(head,-1,sizeof(head));
	memset(edge,0,sizeof(edge));
	memset(vis,0,sizeof(vis));
	scanf("%d%d",&n,&m);
	while(m--){
		scanf("%d%d",&u,&v);
		addedge(u,v); 
		addedge(v,u);
		//較大的n和m值一般要學會放棄矩陣，用鄰接表 
	}
	for(i=1;i<=n;i++){
		vis[i]=1;
		Print[0]=i;
		dfs(i,i,1);
		vis[i]=0;
	}
	printf("%d\n",ans);
	return 0;
}
           

最大子陣。比較難的想到的DP題。大家應該會字首和的做法吧，如果是一維數組中求最大連續子序列和怎麼做的。。就是把每個的字首放進去然後循環一次相減就好了是吧。是以呢，把每行都求出字首和。然後暴力各類連續行，然後去求單行的最大連續子序列和。比如行數為3，那麼我需要求1，2，3，1和2，2和3，1和2和3，每個逗号分開，把這些行中的列号相對的數相加得到一個新行，求此行的最大。。。

const long long maxnum=550;
long long num[maxnum];
long long ans;
long long a[maxnum][maxnum];
long long n,m;

void calc(){
	long long i,j,k,l;
	long long temp=num[1],Max=num[1];
	for(i=2;i<=m;i++){
		if (temp>0) temp+=num[i];
		else temp=num[i];
		Max=max(Max,temp);
	}
	ans=max(ans,Max);
}

int main(){
	//freopen("input.txt","r",stdin);
	long long i,j,k,l;
	scanf("%I64d%I64d",&n,&m);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%I64d",&a[i][j]);
	ans=-99999999;
	for(i=1;i<=n;i++){ 
		memset(num,0,sizeof(num));
		for(j=i;j<=n;j++){
			long long sum=0;
			for(k=1;k<=m;k++)
				num[k]+=a[j][k];
			calc();
		}
	}
	printf("%I64d\n",ans);
	return 0;
}
           

大臣的旅費：題意中廢話去掉之後：求樹的直徑

方法：兩次dfs。第一次：從任意點出發，找到離該點距離最大的點i；第二次，從i點出發，找到離i的最大距離點j

注意：本題資料量比較大，必須學會使用鄰接表。。。矩陣實在太浪費空間了

int dis[10050][10050];
int vis[12000];
int n,i,j,k;
int ans=0;

void dfs(int pos,int dist){
	int i,j,k;
	ans=max(dist,ans);
	for(k=1;k<=n;k++)
		if (dis[pos][k]&&!vis[k]){
			vis[k]=1;
			dfs(k,dist+dis[pos][k]);
		}
}

int main(){
	freopen("input.txt","r",stdin);
	memset(dis,0,sizeof(dis));
	int u,v,cost;
	scanf("%d",&n);
	for(i=1;i<=n-1;i++){
		scanf("%d%d%d",&u,&v,&cost);
		dis[v][u]=dis[u][v]=cost;
	}
	for(i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		vis[i]=1;
		dfs(i,0);
	}
	//printf("%d\n",ans);
	printf("%d\n",ans*10+ans*(1+ans)/2);
	return 0;
}
           

波動數列：dp[i][j]考慮，其中j表示對n的餘數

小朋友排隊：跟逆序對一樣的思路，二分的歸并查找