Spica's blog
home tags archives about

CF Educational round 76 补题总结

2019-11-27 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));
    }
}

更新于 2019-11-28

# 总结
Previous Post
How to set up Alive2 on Ubuntu 20.04 LTS from scratch
Next Post
Hollow Knight游戏总结