CF Educational round 76 补题总结

CF 算法

前言

​ 教育场还是比较简单的……对着题解至少都能够做出来。

A Two Rival Students

​ 签到题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int times,n,x,a,b,maxm;

int main(){
cin>>times;
while(times--){
cin>>n>>x>>a>>b;
maxm=n-max(a,b)+min(a,b)-1;
cout<<abs(a-b)+min(maxm,x)<<"\n";
}
}

B Magic Stick

​ 给出两个操作:

    1. f (x : even int) -> x/2*3
    2. 2. f (x : int and larger than 1) -> x -1

​ 再给出两个数x和y,询问x是否能够经过有限次操作变到y。
​ 显然我们可以对于当前的x不断利用操作1直到大于y再不断调用操作2。所以我们只要找到某个阈值,在这个阈值以下的数无论怎么调用操作1也不会变大就OK了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cstring>

using namespace std;

int x,y,times;
char* str[2]{"YES\n","NO\n"};

int main(){
ios_base::sync_with_stdio(0);
cin>>times;
while(times--){
cin>>x>>y;
cout<<str[x==1&&y!=1||x<=3&&y>3];
}
}

C Dominated Subarray

​ 定义一个array被dominated by value v, first its length should be larger than 2, and second v 是整个数组中出现次数最多的元素。显然对于一个数组,若其被dominated则v唯一。

​ 给出一个数组求该数组的一个子串使得其为dominated array且长度最短。

​ 对于每一个元素x,我们记录其位置与上一次x的出现的位置的差值,将最小的差值作为答案。

​ 证明: 假设最后的最小差值出现在pos与上一次位置pos’,且pos-pos’不是答案。那么

​ 1. 若[pos’,pos]中每一个元素仅仅出现一次,则表明这是一个dominated array。假若其不是最优解,则表明存在另外一组[pos1’,pos1]且pos1-pos1’<pos-pos’,与题设矛盾

​ 2. 若[pos‘,pos]中存在一个元素出现次数大于一次,则表明这一段不是一个dominated array。设那个至少出现两次的元素的起始两次出现位置分别在pos1’和pos1,并且pos’<pos1’, pos1<pos。则有pos1-pos1’<pos-pos’,存在一组更小的差值,矛盾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>

using namespace std;
const int maxm=2*1e5+10;

int x,lst[maxm],times,n,ans=0x3f3f3f3f;

int main(){
cin>>times;
while(times--){
cin>>n;
memset(lst,0x3f,sizeof(int)*(n+5));
for(int i=0;i<n;++i){
cin>>x;
if(lst[x]!=0x3f3f3f3f)
ans=min(ans,i-lst[x]+1);
lst[x]=i;
}
cout<<(ans==0x3f3f3f3f?-1:ans)<<"\n";
ans=0x3f3f3f3f;
}
}

D Yet Another Moster Killing Problem

​ 给出一个长度为n的queue,再给出m种操作,每个操作由一个二元组<p,s>组成。对于第i种操作,<pi,si>代表着至多将队伍中的si个元素出队,且所有出队的元素要小于等于pi。求将队伍清空的最小操作次数,or无法清空。

​ 在这个题目中,si是∈[1,n]的,实际上大于也没有关系,上限只有n,取一个min就好。对于所有的k∈[1,n],求出能够出队k个元素的最大pkmax。对于一个queue,我们每一次贪心选择最大的k且保证出队的元素中最大值小于等于pkmax就好。

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
#include <iostream>
#include <cstring>

using namespace std;
const int maxm=2*1e5+10;

int n,m,mons[maxm],p,s,bst[maxm],times,ans;

int main(){
ios_base::sync_with_stdio(0);
cin>>times;
while(times--){
cin>>n;
for(int i=0;i<n;++i)cin>>mons[i];
cin>>m;
while(m--){
cin>>p>>s;
bst[s]=max(bst[s],p);
}

for(int i=n-1;i;--i)bst[i]=max(bst[i],bst[i+1]);
for(int cur=-1,tmpMax,j;cur<n-1;){
for(tmpMax=mons[cur+1],j=1;j+cur<n&&tmpMax<=bst[j];tmpMax=max(tmpMax,mons[(++j)+cur]));
if(j==1){
cout<<"-1\n";
goto endLoop;
}
cur+=j-1;
++ans;
}
cout<<ans<<"\n";
endLoop:
ans=0;
memset(bst,0,sizeof(int)*(n+5));
}
return 0;
}

E The Contest

​ 给出3个集合,pre,mid,post。三个集合的并集恰为{1,2,3,4,5,……,n}, i.e. 从1开始的n个自然数的集合。每次操作可以将一个数从一个集合放到另外一个集合中。求最小的操作次数使得pre为 {1,2,3,….k},mid为{k+1,k+2,…..,L},post为{L+1,L+2,…..,n}。其中pre或者mid或者post可以为空集

​ 定义状态dp[ i ] [ j ] 表示当前处理到{1,….,i}且i位于第j个集合中,0代表pre,1代表mid,2代表post。

​ 定义函数cost(s,val),表示将val放入s中的代价,假若val在s中则为0,否则为1。

​ 初始条件dp[ 0 ] [ 0 ] = dp [ 0 ] [ 1 ] = dp [ 0 ] [ 2 ] = 0

​ 对于dp [ i ] [ 0 ]来说,i只能放在0中,因此dp [ i ] [ 0 ] = dp [ i ] [ 0 ] + cost(0,i)

​ 对于dp [ i ] [ 1 ]来说,i只能继续放在1中或者之前一直放在0中现在开始放到1中,因此 dp [ i ] [ 1 ] = cost(1,i) + min (dp [ i - 1 ] [ 0 ], dp[ i - 1 ] [ 1])

​ 对于dp [ i ] [ 2 ]来说,i可以继续放在2中,也可以之前放在1中现在开始放到2中,也可以之前放在0中现在开始跳过1直接放到2中,因此 dp [ i ] [ 2 ] = cost(2,i) + min(dp [ i - 1] [ 0 ], dp [ i - 1] [ 1 ], dp [ i - 1] [2])

​ 最终的答案就是min(dp [ n ] [ 0 ], dp [ n ] [ 1 ], dp [ 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
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstring>
#include <unordered_set>
#include <algorithm>

using namespace std;
const int maxm=2e5+10;

unordered_set<int> us[3];
int k[3],dp[maxm][3],cost(int now,int val),n;

int main(){
ios_base::sync_with_stdio(0);
for(int i=0;i<3;++i)cin>>k[i];
n=k[0]+k[1]+k[2];
for(int i=0;i<3;++i){
for(int j=0,tmp;j<k[i];++j){
cin>>tmp;
us[i].insert(tmp);
}
}

memset(dp,0x3f,(n+5)*3*sizeof(int));
dp[0][0]=dp[0][1]=dp[0][2]=0;
for(int i=1;i<=n;++i){
dp[i][0]=dp[i-1][0]+cost(0,i);
dp[i][1]=cost(1,i)+min(dp[i-1][0],dp[i-1][1]);
dp[i][2]=cost(2,i)+min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]));
}

// for(int i=0;i<=n;++i){
// cout<<dp[i][0]<<' '<<dp[i][1]<<' '<<dp[i][2]<<endl;
// }
cout<<min(dp[n][0],min(dp[n][1],dp[n][2]))<<endl;
return 0;
}

int cost(int now,int val){
return us[now].find(val)==us[now].end();
}

F Make The Similar

​ 定义[0,(1<<30)-1]上的二元等价关系similar<a,b>为a与b的二进制位中的1的个数相同,给出一个长度为n的数组(n∈[2,100]),求任意一个x,使得将数组中的每一个元素与x做xor之后均相互similar

​ 考虑到这里二进制一共只考虑30位,我们先考虑其前15位。枚举x∈[0,(1<<15)),每次记录一个数组,which is x与数组中的每一个元素的前15位做xor的产物。无妨说x与数组的第i位的前15位的xor值为cnt(0,x,i)。同理,我们考虑后15位,枚举x∈[0,(1<<15)),每次记录一个数组,which is x与数组中的每一个元素的后15位做xor的产物。无妨说x与数组的第i位的后15位的xor值为cnt(0,x,i)。我们的目的就是要找到一组x与x’使得对于任意的i与j有cnt(0,x,i)+cnt(1,x’,i)==cnt(0,x,j)+cnt(1,x’,j),随后将x与x’合并输出即可。

​ 更进一步,为了方便找到这样的一组x与x’,我们将以上等式变形,实际上i和0也没有区别,对吧?

​ cnt(0,x,0)+cnt(1,x’,0) == cnt(0,x,j)+cnt(1,x’,j) < – >

​ cnt(0,x,0)-cnt(0,x,j) == -cnt(1,x’,0)+cnt(1,x’,j) < – >

​ cnt(0,x,0)-cnt(0,x,j) == -(cnt(1,x’,0)-cnt(1,x’,j))

​ 所以我们实际在储存数组的时候是仅仅储存的cnt(0,x,0)-cnt(0,x,j),而且不储存第一项。而查询的时候,等到后15位查询的时候,将构建出的数组中的每一个元素取相反数,直接查询该数组是否存在即可。

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#define loopUp(i,from,to) for(int i=(from);i<(to);++i)
using namespace std;
const int maxm=110;

int n,arr[110];
map<vector<int>,int> m;
vector<int> tmp;

inline int getBitsCount(int x){
return __builtin_popcount(x);
// x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
// x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
// x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
// x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
// x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
// return x;
}

int main(){
ios_base::sync_with_stdio(0);
cin>>n;
loopUp(i,0,n)cin>>arr[i];
loopUp(x,0,(1<<15)){
int cnt01=getBitsCount((arr[0]^x)&0x7fff);
loopUp(i,1,n)tmp.push_back(cnt01-getBitsCount((arr[i]^x)&0x7fff));
m.insert(make_pair(tmp,x));
tmp.clear();
}
loopUp(x,0,(1<<15)){
int cnt11=getBitsCount(((arr[0]>>15)^x)&0x7fff);
loopUp(i,1,n)tmp.push_back(getBitsCount(((arr[i]>>15)^x)&0x7fff)-cnt11);
if(m.find(tmp)!=m.end()){
cout<<((x<<15)|m[tmp])<<endl;
return 0;
}
tmp.clear();
}
cout<<-1<<endl;
return 0;
}

G Divisor Set

​ 给出n个素数,求一个集合的最大的势,这个集合里的每个元素都是由n个素数中选择0个或者多个的乘积(选择0个则为1)并且元素之间不能相互整除。

​ 可以画一个整除关系的哈斯图,可以发现在哈斯图中假若x>y则x一定位于y的上方,而且处于相同层的元素不能相互整除。而且在图中是从下到上是先变宽后再变窄的近似对称的图形,所以直接取最中间那一层(n/2)就好。

​ 所以实际上这里就出现了一个多重背包。假设第i个素数出现了cnt(i)次,则求出在所有素数中拿取n/2个数的方法。

​ 此外另外一种做法就是把第i个素数当成一个多项式 1 + x + x^2 + …. + x ^(cnt(i)),将所有多项式相乘,求出幂为n/2项的系数即可,这里用NTT。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <cassert>
#define loopUp(i,from,to) for(int i=(from);i<(to);++i)

using namespace std;
const int mod=998244353;
const int logn=18;
const int maxm=(1<<logn)+10;

struct cmp{
bool operator()(const vector<int>& a,const vector<int> &b)const{
return a.size()<b.size();
}
};

int n,p[maxm],aa[maxm],bb[maxm],cc[maxm],g=3;
unordered_map<int,int> cnt;
multiset<vector<int>,cmp> polys;

vector<int> mul(const vector<int>& a,const vector<int>& b);
int mul(int a,int b){return (a*1ll*b)%mod;}
int pow(int a,int k){
int ans=1;
for(;k;k>>=1){
if(k&1)ans=mul(ans,a);
a=mul(a,a);
}
return ans;
}
int inv(int a){return pow(a,mod-2);}
int norm(int a){
while(a>=mod)a-=mod;
while(a<0)a+=mod;
return a;
}

void fft(int arr[],int n,bool inverse),precalc();
vector<int> w[logn],r;

int main(){
ios_base::sync_with_stdio(0);
cin>>n;
loopUp(i,0,n){
cin>>p[i];
++cnt[p[i]];
}
for(const auto& pair:cnt)polys.emplace(pair.second+1,1);
precalc();
while(polys.size()>1){
auto tmp1=*polys.begin();
polys.erase(polys.begin());
auto tmp2=*polys.begin();
polys.erase(polys.begin());

polys.insert(mul(tmp1,tmp2));
}

cout<<(*polys.begin())[n/2]<<endl;
return 0;
}

vector<int> mul(const vector<int>& a,const vector<int>& b){
int ln=1;
while(ln<a.size()+b.size())ln<<=1;
loopUp(i,0,ln)aa[i]=(i<a.size()?a[i]:0),bb[i]=(i<b.size()?b[i]:0);

fft(aa,ln,0);
fft(bb,ln,0);

loopUp(i,0,ln)cc[i]=mul(aa[i],bb[i]);

fft(cc,ln,1);
vector<int> ans(cc,cc+ln);
while(!ans.empty()&&ans.back()==0)ans.pop_back();
return ans;
}

void fft(int arr[],int n,bool inverse){
int ln=__builtin_ctz(n);
assert((1<<ln)<(1<<logn)+3);
assert((1<<ln)==n);

loopUp(i,0,n){
int ni=r[i]>>(logn-ln);
if(i<ni)swap(arr[i],arr[ni]);
}

for(int st=0;(1<<st)<n;++st){
int len=(1<<st);
for(int k=0;k<n;k+=(len<<1)){
loopUp(pos,k,k+len){
int l=arr[pos];
int r=mul(arr[pos+len],w[st][pos-k]);
arr[pos]=norm(l+r);
arr[pos+len]=norm(l-r);
}
}
}

if(inverse){
int in=inv(n);
loopUp(i,0,n)arr[i]=mul(arr[i],in);
reverse(arr+1,arr+n);
}
}

void precalc(){
// int wb=pow(g)
int wb=pow(3,(mod-1)/(1<<logn));
loopUp(st,0,logn){
w[st].assign(1<<st,1);
int bw=pow(wb,1<<(logn-st-1));
int cw=1;
loopUp(k,0,1<<st){
w[st][k]=cw;
cw=mul(cw,bw);
}
}
r.assign(1<<logn,0);
loopUp(i,1,r.size()){
r[i]=(r[i>>1]>>1)|((i&1)<<(logn-1));
}
}