牛客小白月赛106A-E题解

牛客小白月赛106

A.最后DISCO

注意到b!=0时， $a^b$ 与 $a$ 的奇偶性相同，则直接计算a*c+d即可。

特判b=0 , 此时直接令a=1即可。

// 该缺省头此后省略
#include <stdio.h>
#include <bits/stdc++.h>
#define yes printf("Yes\n")
#define no printf("No\n")
#define ll long long
#define all(x) x.begin(),x.end()
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

int main(){
	ll a,b,c,d;cin>>a>>b>>c>>d;
	if(b==0)a=1;
	if((a*c+d)%2==1)cout << "YES";
	else cout << "NO";
	return 0;
}

B.末日DISCO

条件3 x在所有集合的出现次数之和必须小于等于2 容易让人想到边。那么可以给两个集合“连边”，即把边的编号存到“连边”的集合中。只要每条边的编号各不相同，即可满足题目条件。

把n个集合全连起来，每个集合会连出n-1条边，还差一个元素可以用没用过的编号补齐。

int main(){
	int n;cin>>n;
	int cnt = 1;
	vector<vector<int>>ans(n);
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			ans[i].push_back(i*1000+j);
			ans[j].push_back(i*1000+j);
		}
	}
	for(int i=0;i<n;i++)ans[i].push_back(666666+i);
	for(auto x:ans){
		for(auto y:x) cout << y << " ";
		cout << "\n";
	}
	return 0;
}

C.明日DISCO

由于边界都是0，所以最终状态一定是所有数都要被操作变成0。

观察样例发现如果某数无法操作成0，那么他一定会操作成和周围某个非0的数相等，此时这两个数永远无法操作，无法达成目标。

把一个数操作成0之后，不影响旁边的数操作（或者说不会更劣）。考虑从容易操作到难操作的顺序，暴力操作每个数即可，发现不能操作时答案为NO。

赛时脑抽把相邻格子写成(i+1,j+1),(i+1,j-1),(i-1,j+1),(i-1,j-1),痛失一血，望周知。

int main(){
	int n;cin>>n;
	vector<vector<int>>a(n+2,vector<int>(n+2,0));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin >> a[i+1][j+1];
		}
	}
	for(int k=0;k<3;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(a[i][j] == 0)continue;
				vector<int> as;
				as.push_back(a[i][j]);
				as.push_back(a[i+1][j]);
				as.push_back(a[i-1][j]);
				as.push_back(a[i][j-1]);
				as.push_back(a[i][j+1]);
				sort(all(as));
				if(a[i][j] == as[0]) a[i][j] = min(as[1],0);
				if(a[i][j] == as[4]) a[i][j] = max(as[3],0);	
			}	
		}	
	}
	int cnt = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]==0)cnt++;
		}
	}
	if(cnt == n*n) cout << "YES";
	else cout << "NO";
	return 0;
}

D.太阳系DISCO

首先，无论按何种顺序走，只要确定最终每种走法的个数，先走x，先走y，先走n/2是没有区别的。

然后，注意到走两次n/2是无用的，因为这会回到原来的位置，删去两次走n/2后最终位置不变而时间减少2。所以只用考虑是否走一次n/2。可以钦定走n/2发生在最开始或最末，我在本题中钦定为发生在最末，那么问题转化为从a走到b或走到(b+n/2)%n。

采用BFS求解，计算出到每个点的最短时间，然后提取答案。

int main(){
	int n,k,a,b,x,y;cin>>n>>k>>a>>b>>x>>y;
	a--,b--;
	vector<int>vis(n,0);
	vis[a] = 1;
	queue<int>Q; Q.push(a);
	while(!Q.empty()){
		int tp = Q.front();Q.pop();
		if(!vis[(tp+x)%n]){
			vis[(tp+x)%n] = vis[tp] + 1;
			Q.push((tp+x)%n);
		}
		if(!vis[(tp-y+n)%n]){
			vis[(tp-y+n)%n] = vis[tp] + 1;
			Q.push((tp-y+n)%n);
		}
	}
	int ans = -1;
	if(k==0){
		if(vis[b])	ans = vis[b];
	}
	if(k>0){
		ans = 1e9;
		if(vis[b]) ans = min(ans,vis[b]);
		if(vis[(b+n/2)%n]) ans = min(ans,vis[(b+n/2)%n]+1);
		if(ans==1e9)ans = -1;
	}
	if(ans!=-1)ans--;
	cout << ans;
	return 0;
}

E.普通DISCO-1

首先肯定要求一遍树上每个点的深度，然后看深度最大的链，我们要从树上找到另一个“最深的分叉”加到深度最大的链的叶子上，构造出答案。

怎么找这个“最深的分叉”？下面证明：“最深的分叉”一定是深度最大的链上某个点第二深的子树。

考虑两种情况：①这个点在我们考虑的深度最大的链上。那么，此时该点第一深的子树就包含我们考虑的深度最大的链，选分叉时不能选该子树的根（违反lca要求）。那么只能选第二深子树的根，此时所选的两个点的lca就是该点。

②这个点不在我们考虑的深度最大的链上。那么考虑这个点的父亲，答案一定更优。而一直找这个点的父亲，一定能回到情况①。

证明完毕。那么做法就是一个dfs求最大深度，同时记下每个点第二深子树深度，答案即为树最大深度+最深的第二深子树深度-1。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

int main(){
	int n;cin>>n;
	vector<vector<int>>adj(n);
	for(int i=0;i<n-1;i++){
		int u,v;cin>>u>>v;
		u--;v--;
		adj[u].push_back(v);
		adj[v].push_back(u);	
	}
	vector<int>depth(n),ans(n);
	int an = 0;
	auto dfs = [&](auto && self,int u,int p)->void{
		depth[u] = 0; 
		ans[u] = 0;
		for(auto v:adj[u]){
			if(v==p)continue;
			self(self,v,u);
			if(depth[v]>depth[u]){
				ans[u] = depth[u];
				depth[u] = max(depth[u],depth[v]);	
			}
			else if(depth[v]>ans[u]){
				ans[u] = depth[v];
			}	
		}
		depth[u]++;	
		an = max(an,ans[u]);
	};
	dfs(dfs,0,-1);
	cout << depth[0] + max(an-1,0);
	return 0;
}