C/C++教程

Codeforces Round #733 (Div. 1 + Div. 2)题解

本文主要是介绍Codeforces Round #733 (Div. 1 + Div. 2)题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

快两年没有碰OI了orz,打一次直接橙变紫掉200分。


 

A题 水题

B题 水题

C题 水题

D题 

 贪心,可以想到有多少个不同的a[i]就有多少最终答案。匹配上,贪心选择,然后乱匹配。如果发现i自己对应自己了,那么将i对应向a[i],而a[i]对应的人对上自己就可以了。

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>

 
using namespace std;
int n,T;
int a[200005],b[200005];
int cnt[200005];
int main() {
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&n); int m = 0;
		for(int i=1;i<=n+1;i++) cnt[i] = 0,a[i]=b[i]=0;
		for(int i=1;i<=n;i++) {
			scanf("%d",&a[i]);
			if(!cnt[a[i]]) {
				m++; b[i] = a[i]; cnt[a[i]] = i;
			}
		}
		int zz = 1;
		for(int i=1;i<=n;i++) {
			if(!b[i]) {
				while(cnt[zz]) zz++;
				b[i] = zz; cnt[zz] = i; zz++;
			}
		}
	//	cerr<<cnt[3]<<"fu"<<endl;
		printf("%d\n",m);
		for(int i=1;i<=n;i++) {
			if(b[i]==i) {
				b[i] = a[i]; 
				b[cnt[a[i]]] = i;
				cnt[a[i]] = i;
			}
		}
		for(int i=1;i<=n;i++) printf("%d ",b[i]);
		puts("");
	}
}

E题

 

未完待续。。 

这篇关于Codeforces Round #733 (Div. 1 + Div. 2)题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!