CF1770(div2)题解(Good Bye 2022)
CF1770
A. Koxia and Whiteboards
题意：
给定长度为n的数组a，m次操作，第i次操作用 $b_i$ 替换数组任意数，求数组最后的最大总和
思路：
优先队列建小根堆，每次弹出最小值，加入 $b_i$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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
每次最大一个数最小一个数依次输出即可
1
2
3
4
5
6
7
8
9
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}$ 的质数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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";
}