官方题解

最后DISCO

定义一个变量 $x$ ，初始值为 $a \mod 2$ 。

如果 $b=0$ ，那么把 $x$ 改为 $1$ 。

如果 $c$ 为偶数，则把 $x$ 改为 $0$ 。

最后判断 $x+d$ 的奇偶性即可。

#include<bits/stdc++.h>
using namespace std;
inline void solve(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	int ji=a%2;
	if(b==0)ji=1;
	if(c%2==0)ji=0;
	ji=(ji+d)%2;
	if(ji)cout<<"YES\n";
	else cout<<"NO\n";
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

末日DISCO

对于一对每一对 $i,j$ ，我们让它们只共用一个数。

可以写双重循环构造。

void solve(){
	int n;cin>>n;
	int cnt=0;
	for(int i=0;i<n;++i)
        for(int j=i+1;j<n;++j)
            ++cnt,v[i].push_back(cnt),v[j].push_back(cnt);
	for(int i=0;i<n;++i)++cnt,v[i].push_back(cnt);
	for(int i=0;i<n;++i){
		for(int j:v[i])cout<<j<<' ';
		cout<<endl;
	} 
}

明日DISCO

可以证明如果存在两个相邻（有共用边）的点，如果它们的正负性相同，那么无解。

假如存在一个位置 $(i,j)$ 与 $(p,q)$ 相邻且 $a_{i,j}$ 和 $a_{p,q}$ 同号，那么不妨设 $a_{i,j} \geq a_{p,q} > 0$ 。（ $a_{i,j} \le a_{p,q}< 0$ 同理）由于 $a_{i,j}\geq a_{p,q}$ ，所以我们此时无法对 $a_{p,q}$ 进行操作。而当我们对 $a_{i,j}$ 操作到 $a_{i,j}=a_{p,q}$ 之后，就形成了一个“死局”。我们既无法改变 $a_{i,j}$ 也无法改变 $a_{p,q}$ ，所以输出 NO。

反之，我们只要依次操作把所有数变为 $0$ 即可，输出 YES。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[505][505];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
inline void solve(){
	cin>>n;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			if(a[i][j]!=0){
				for(int f=0;f<4;++f){
					int tx=i+dx[f],ty=j+dy[f];
					if(a[tx][ty]!=0){
						if(a[tx][ty]*a[i][j]>0){
							cout<<"NO\n";
							return;
						}
					}
				}
			}
		}
	}
	cout<<"YES\n";
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

太阳系DISCO

观察到最多只会用一次技能，如果用了偶数次相当于没有用。直接跑最短路，然后看到（ $b$ 的距离）和（到和 $b$ 对面的那个点的距离+1）的较小值即可。

#include<bits/stdc++.h>
using namespace std;
const int mxn=2e5+5;
int dist[mxn];
int n,k,a,b,x,y;
int go(int t,int p){
	t+=p;
	t=(t-1)%n+1;
	return t;
}
inline void solve(){
	cin>>n>>k>>a>>b>>x>>y;
	memset(dist,63,sizeof(dist));
	dist[a]=0;
	queue<int>q;q.push(a);
	while(q.size()){
		int p=q.front();q.pop();
		int t1=go(p,x);
		if(dist[t1]>dist[p]+1){
			dist[t1]=dist[p]+1;
			q.push(t1);
		}
		int t2=go(p,n-y);
		if(dist[t2]>dist[p]+1){
			dist[t2]=dist[p]+1;
			q.push(t2);
		}
	}
	int mn=dist[b];
	if(k>=1)mn=min(mn,dist[go(b,n/2)]+1);
	if(mn<=n)cout<<mn<<endl;
	else cout<<-1<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

普通DISCO-1

找到这棵树的最深的点，然后拎出这个点到根的这条链（记这条链为 $x$ ）。

对于 $x$ 上所有点 $i$ ，记 $a_i$ 为点 $i$ 在删除了连接它与它在 $x$ 上的儿子的边之后，它的子孙中到它的距离的最大值。

那么答案就是 $x$ 的长度加上 $a_i$ 的最大值。

#include<bits/stdc++.h>
using namespace std;
const int mxn=1e6+6;
vector<int>g[mxn];
int n,dep[mxn],son[mxn],ans;
void dfs(int x,int fa=0){
	dep[x]=1;
	for(int y:g[x])if(y!=fa){
		dfs(y,x);
		dep[x]=max(dep[x],dep[y]+1);
		if(dep[y]>dep[son[x]])son[x]=y;
	}
}
void go(int x,int fa=0){
	for(int y:g[x])if(y!=fa and y!=son[x])ans=max(ans,dep[y]);
	if(son[x])go(son[x],x);
}
inline void solve(){
	cin>>n;
	for(int i=1,u,v;i<n;++i){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1);
	go(1);
	cout<<dep[1]+max(ans-1,0)<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

普通DISCO-2

二分答案。

假设我们最后能得到的深度为 $x$ ，那么我们把树上所有深度大于 $x$ 的点都标记上“坏的”。

记 $a$ 为所有“坏的” 点 的父亲 的LCA（如果LCA是根那么显然不行），那么我们至少需要断掉 $a$ 和 $a$ 的父亲的边。（其实也可以断掉 $a$ 的某个祖先和 $a$ 的某个祖先和它的父亲的边，但这样不优）

然后我们枚举所有可能和 $a$ 执行操作的点。如果存在一个点满足交换之后深度小于等于 $x$ ，那么 $x$ 就合法，否则不合法。可以通过预处理每个节点的子树的深度快速计算。

使用欧拉序+ST表求LCA可以在总时间复杂度 $O(n\log n)$ 内解决本题。

#pragma gcc optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int mxn=1e6+6;
vector<int>g[mxn];
int n,dep[mxn],son[mxn],ans;
vector<int>e[mxn];
int tol[mxn];
int cord[mxn],cco;
int st[mxn],ed[mxn],par[mxn];
int lg[mxn],mi[22][mxn]; 
void dfs(int x,int fa=0){
	cord[++cco]=x;
	st[x]=cco;ed[x]=cco;
	dep[x]=dep[fa]+1;
	e[dep[x]].push_back(x);
	int isl=1;
	tol[x]=1;par[x]=fa;
	for(int y:g[x])if(y!=fa){
		dfs(y,x),isl=0,tol[x]=max(tol[x],tol[y]+1);
		cord[++cco]=x;
		ed[x]=cco;
	}
}
inline void init(){
	lg[1]=0;
	for(int i=2;i<mxn;++i)lg[i]=lg[i>>1]+1;
	for(int i=1;i<=cco;++i)mi[0][i]=cord[i];
	for(int k=1;k<22;++k){
		for(int i=1;i<=cco-(1<<k)+1;++i){
			int x=mi[k-1][i],y=mi[k-1][i+(1<<(k-1))];
			if(dep[x]<dep[y])mi[k][i]=x;
			else mi[k][i]=y;
		}
	}
}
inline int lca(int x,int y){
	int fx=st[x],fy=ed[y];
	if(fx>fy)swap(fx,fy);
	int l=lg[fy-fx];
	int ax=mi[l][fx],ay=mi[l][fy-(1<<l)+1];
	if(dep[ax]<dep[ay])return ax;
	else return ay;
} 
bool ok(int depth){
	int l=-1;
	for(int i=n;i>depth;--i){
		for(int j:e[i]){
			if(l==-1)l=par[j];
			else l=lca(l,par[j]);
		}
	}
	for(int i=1;i<=n;++i){
		int t=lca(l,i);
		if(t!=i and t!=l){
			if(dep[i]-1+tol[l]<=depth and dep[l]-1+tol[i]<=depth)return 1;
		}
	}
	return 0;
}
inline void solve(){
	cin>>n;
	for(int i=1,u,v;i<n;++i){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1);init();
	int lo=1,hi=n,md;
	while(lo<hi-1){
		md=lo+hi>>1;
		if(ok(md))hi=md;
		else lo=md;
	}
	cout<<hi<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	solve();
	return 0;
}