发布时间：2023-09-04

CF1770

A. Koxia and Whiteboards

题意：
给定长度为n的数组a，m次操作，第i次操作用 $b_i$ 替换数组任意数，求数组最后的最大总和
思路：
优先队列建小根堆，每次弹出最小值，加入 $b_i$

void solve(){
	int n,m;
	cin>>n>>m;
	priority_queue<int,vector<int>,greater<int>> q;
	ll sum=0;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		q.push(x);
		sum+=x;
	}
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		sum-=q.top();
		q.pop();
		q.push(x);
		sum+=x;
	}
	cout<<sum<<"\n";
}

B. Koxia and Permutation

题意： 给定一个长度为n数组a（permulation），一个整数k
构造数组c
$c_i=max(a_i,a_{i+1},...,a_{i+k-1})+min(a_i,a_{i+1},...,a_{i+k-1})$
构造代价为 $max(c_1,c_2,...,c_{i+k-1})$
求最小代价的数组a 思路：
易得最小代价为n+1
每次最大一个数最小一个数依次输出即可

void solve(){
	int n,k;
	cin>>n>>k;
	for(int i=1,j=n;i<=j;i++,j--){
		if(i!=j)cout<<j<<" "<<i<<" ";
		else cout<<i<<" ";
	}
	cout<<"\n";
}

Koxia and Number Theory(数论+中国剩余定理+鸽巢原理)

题意：
对数组每个数加上x,使数组两两互质gcd=1，输出YES或NO
思路：
如果有相同的数，输出NO
考虑奇偶性对数组的影响，若奇数和偶数均大于等于2个，则当选择加奇数时，原来的若干对奇数能被2整除；若选择加偶数，则原来的若干对偶数能被2整除
将2推广到一般质数p
定义 $cnt_j$ 为数组模p后为j的个数
若 $min(cnt_0,cnt_1,...,cnt_{p-1})>=2$ 则输出NO 鸽巢原理：只需要枚举 $\lfloor \frac{n}{2} \rfloor$ 个质数
证明： 因为 $min(cnt_0,cnt_1,...,cnt_{p-1})>=2$,
且 $n=cnt_0+cnt_1+cnt_{p-1}$，
所以 $n>=2 \cdot (p-1)$
所以只需枚举小于等于 $\frac{n}{2}$ 的质数

void solve(){
	int n;
	cin>>n;
	vector<ll> a(n+1);
	int one=0,two=0;
	map<ll,bool> vis;
	bool g=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(vis[a[i]])g=1;
		vis[a[i]]=1;
	}
	if(g){
		cout<<"NO\n";
		return;
	}
	for(int i=2;i<=n/2;i++){
		vector<int> cnt(i);
		for(int j=1;j<=n;j++)cnt[a[j]%i]++;
		if(*min_element(all(cnt))>=2){
			cout<<"NO\n";
			return;
		}
	}
	cout<<"YES\n";
}

D. Koxia and Game(集合(并查集)+bfs)

题意：
A，B两个人在玩游戏，有a,b,c三个数组长度为n，a,b给定，游戏有n轮，第i轮A先从 $a_i,b_i,c_i$ 选一个数，B再从剩下里面选一个数，n轮后B选的数包含1-n的所有数，求c有多少种
思路：
注意1：每一轮剩下的两个数必须相同，才能固定B的选法
每一轮从a,b选出一个数能组成1-n的数
将 $(a_i,b_i)$ 看成一条边
每个数可以分成多个集合， 建双向边，遍历完一个环后每个节点的边数总和为edge，节点个数ver
当且仅当edge/2==ver时，才表示节点能遍历完形成闭环且不影响其他数字成环，否则直接输出0 在闭环中，遍历方法有两种(顺时针和逆时针)，ans*=2;
如果环内有自环，当前节点有n种可能，环的遍历方式只有一种了，ans/=2,ans*=n

ll ksm(ll a){
	ll ans=1;
	ll b=mod-2;
	for(;b;b>>=1){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
	}
	return ans%mod;
}
void solve(){
	int n;
	cin>>n;
	vector<int> a(n+1),b(n+1);
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	vector<int> adj[n+1];
	for(int i=1;i<=n;i++){
		adj[a[i]].pb(b[i]);
		adj[b[i]].pb(a[i]);
	}
	vector<int> vis(n+1);
	ll ans=1;
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		vis[i]=1;
		queue<int> q;
		q.push(i);
		int edge=0,ver=0;
		while(!q.empty()){
			int x=q.front();
			q.pop();
			edge+=adj[x].size();
			ver++;
			for(auto y:adj[x]){
				if(!vis[y]){
					vis[y]=1;
					q.push(y);
				}
			}
		}
		edge/=2;
		if(edge!=ver){
			cout<<"0\n";
			return;
		}
		ans*=2;
		ans%=mod;
	}
	int n2=ksm(2);
	for(int i=1;i<=n;i++){
		if(a[i]==b[i]){
			ans*=n2;
			ans%=mod;
			ans*=n;
			ans%=mod;
		}
	}
	cout<<ans<<"\n";
}