Codeforces Round 897 (Div. 2) A~E

A：
原先数组里面最小的位置放最大的数，次小的放次大的即可。

void solve(){
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		c[i]={x,i};
	}
	sort(c+1,c+1+n);
	int num=n;
	for(int i=1;i<=n;i++){
		ans[c[i].second]=num;num--;
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" \n"[i==n];
	}
 }

B:
最後的结果是对称的，只需要知道一半就可以。

• 对于长度为\(odd\)的，一旦可以成功，之后每一次都可以成功。
• 对于长度为\(even\)的，有一次可以成功之后一定是\(0 / 1\)交错。
• 也可以通过当前最多有几个和之前的不一样，之前有多少个地方是不对称的关系来得到结果。

void solve(){
	int n; cin>>n;
	string s;
	cin>>s;
	s="?"+s;
 
	int num=0;
	for(int i=1;i<=n/2;i++){
		if(s[i]!=s[n-i+1]) num++;
	}
 
	if(n%2==1){
		vector<int>ans;
		for(int i=1;i<=n/2+1;i++){
			if(i<=num) ans.push_back(0);
			else ans.push_back(1);
		}
		for(auto v:ans){
			cout<<v;
		}
		reverse(ans.begin(),ans.end());
		for(auto v:ans){
			cout<<v;
		}
	}
	else{
		vector<int>ans;
		for(int i=1;i<=num;i++){
			ans.push_back(0);
		}
		int flag=1;
		for(int i=num+1;i<=(n+1)/2;i++){
			ans.push_back(flag);
			flag^=1;
		}
		for(auto v:ans) cout<<v;
		cout<<flag;
		reverse(ans.begin(),ans.end());
		for(auto v:ans){
			cout<<v;
		}
	}
	cout<<"\n";
}

C:
最开始放最大的\(MEX\)即可，之后删除什么就放什么。

void solve(){
	int n;
	cin>>n;
	
	for(int i=0;i<=n;i++) vis[i]=0;
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		if(x<=n) vis[x]++;
	}
	int num=-1;
	for(int i=0;i<=n;i++){
		if(vis[i]==0) {
			num=i;
			break;
		}
	}
 
	cout<<num<<endl;
	while(1){
		int x;
		cin>>x;
		if(x==-1) return ;
		else cout<<x<<endl;
	}
}

D:
从\(i\)向\(a_i\)建边，最后所有的点要么自身在一个长度为\(k\)的环里面，要目可以指向一个长度为\(k\)的环。
缩点建立新图，之后必须保证在新图里面没有出度的点的\(sz\)为k.

• 也可以通过while循环单纯判断所有的环是不是k元。码量会小很多。

void tarjan(int x){
    dfn[x]=low[x]=++cnt;
    q.push(x);
    vis[x]=1;
	for(auto v:tr[x]){
        int y=v;
        if(dfn[y]==0){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(vis[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        num++;
        while(1){
       	 	int t=q.top();
        	q.pop();
        	vis[t]=0;
        	col[t]=num;
        	sz[num]++;
        	if(t==x) break;
        }
    }
}
bool solve(){
	num=0;
	cin>>n>>k;
	if(k==1){
		bool ok=1;
		for(int i=1;i<=n;i++){
			int x; cin>>x;
			if(x!=i) ok=0;
		}
		return ok;
	}
	for(int i=1;i<=n;i++){
		g[i].clear();
		tr[i].clear(); du[i]=0;
		dfn[i]=low[i]=vis[i]=0;
		sz[i]=0; col[i]=0;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		tr[i].push_back(a[i]);
		du[a[i]]++;
	}

	for(int i=1;i<=n;i++){
		if(du[i]==0) tarjan(i);
	
	for(int i=1;i<=n;i++){
		if(dfn[i]==0) tarjan(i);
	
	for(int i=1;i<=n;i++) du[i]=0;
	for(int i=1;i<=n;i++){
		for(auto v:tr[i]){
			if(col[v]==col[i]) continue;
			else g[col[i]].push_back(col[v]),du[col[i]]++;
		}
	}

	for(int i=1;i<=num;i++){
		if(sz[i]!=1 && sz[i]!=k) return 0;
	}

	for(int i=1;i<=num;i++){
		if(du[i]==0){
			if(sz[i]!=k) return 0;
		}
	}
	return 1;
}

E:
要是看到没有奇数，可能10分钟就把E1过了
在一番操作之后，最后一定只剩下\(n \%k\) 长度的没有处理出来。

• 比如k长度为3的时候：当前处理{1,2,3}。下一次处理{2,1,4}.
  两个异或一下就知道了3^4的结果。
  通过此，可以把e1过了。
• 假设最后剩下的一部分的长度为t.
  把t分为两部分,第一次把第一部分作为一次询问的最后面得到异或结果ans1.
  之后这一部分会被翻转到前面，然后询问\(n-k+1\)，会把前一步进行了反转的非t部分和t的第二部分进行异或得到ans2。 ans1^ans2就是最后的长度为t部分的异或结果。

void solve(){
	cin>>n>>k;
	int ans=0;
	int l=1;
	while(1){
		if(l+k-1<=n){
			cout<<"? "<<l<<endl;
		}
		else{
			break;
		}
		int x; cin>>x;
		ans^=x;
		l+=k;
	}
	l--;
	int t=n-l;
	cout<<"? "<<n-k-t/2+1<<endl;
	int x; cin>>x;
	ans^=x;
	cout<<"? "<<n-k+1<<endl;
	cin>>x;
	ans^=x;
	cout<<"! "<<ans<<"\n";
	// if(l==n+1){
	// 	cout<<"! "<<ans<<endl;
	// 	return ;
	// }
	// while(1){
	// 	int p1,p2;
	// 	cout<<"? "<<l-k+1<<endl;
	// 	cin>>p1;
	// 	cout<<"? "<<l+1-k+1<<endl;
	// 	cin>>p2;
	// 	ans^=(p1^p2);
	// 	l+=2;
	// 	if(l==n+1){
	// 		cout<<"! "<<ans<<endl;
	// 		return ;
	// 	}
}

• 注释部分就是第一个思路的代码。。