牛客练习赛99

NP-Easy问题

solution

做法： 显然是完全图，然后考虑补图，那么补图中有连边的两个点可以共色，否则不能共色。于是只要有个三元环或者两条不交的边就是 ，否则就是 。发现直接找这个东西并不容易，再想想 是啥，发现只能是菊花图，所以就判完了。

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
//2022.5.27 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e3+10;
namespace MAIN{
    int n,m;
    int du[N];
    inline void MAIN(const res &Case){
        n=read(),m=read();
        vector<Pair> E;
        vector<int> A;
        for(res i=1;i<=m;i++){
            res u=read(),v=read();
            E.emplace_back(u,v);
            A.pb(u),A.pb(v);
        }
        if(n>=5000){puts("-2");return;}
        if(n*(n-1)/2==m){puts("0");return;}
        if(n*(n-1)/2-m>n-1){puts("-2");return;}
        sort(A.begin(),A.end());
        A.erase(unique(A.begin(),A.end()),A.end());
        for(auto [u,v]:E)du[u]++,du[v]++;
        if(A.size()==n){
            res id=1;
            for(res i=2;i<=n;i++)if(du[i]<du[id])id=i;
            if(n-1-du[id]==n*(n-1)/2-m)puts("-1");
            else puts("-2");
        }
        else {
            if(n-1==n*(n-1)/2-m)puts("-1");
            else puts("-2");
        }
        for(auto x:A)du[x]=0;
    }
}

相等距离

solution

做法：首先 个点显然可以，只要一条对角线加另外两个顶点，这样的话，所有不在顶点的都可以被对角线上对应的两个点控制，而顶点则可以被顶点控制。而题目要求 个点，所以要去掉两个点。容易注意到顶点是不能去掉的，考虑去掉的对角线上的点是 和 ，不妨令 。注意到此时可能不合法的点是 以及对角线上的点。我们发现这些点有些是容易被控制的，比如 ，考虑有一个控制它的点是 ，那么另一个点就该是 。于是就只有 这些个点以及对角线上的点可能不被控制。 注意到这样的话就是要有一个 的向量，使得和它们合并后都有点存在，这容易想到让 往中间靠，这样就一定能找到 了。小范围的不一定，所以小范围的打下表即可。

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
//2022.5.28 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    inline void MAIN(const res &Case){
        res n=read();
        if(n==2){
            puts("4\n1 1\n1 2\n2 1\n2 2");
            return;
        }
        if(n==3){
            puts("4\n2 1\n1 2\n2 3\n3 2");
            return;
        }
        if(n==4){
            puts("5\n1 1\n1 3\n2 2\n3 1\n3 3");
            return;
        }
        if(n==5){
            puts("5\n1 3\n3 1\n3 5\n5 3\n3 3");
            return;
        }
        if(n==6){
            puts("6\n1 3\n3 1\n3 5\n4 4\n3 3\n5 3");
            return;
        }
        if(n==7){
            puts("7\n2 4\n4 2\n4 6\n4 4\n5 5\n5 3\n6 4");
            return;
        }
        if(n==8){
            puts("8\n1 3\n3 1\n3 5\n4 4\n5 5\n5 3\n5 7\n7 5");
            return;
        }
        if(n==9){
            puts("9\n1 1\n2 2\n3 3\n7 7\n5 5\n8 8\n9 9\n1 9\n9 1");
            return;
        }
        printf("%d\n",n);
        printf("1 %d\n%d 1\n",n,n);
        for(res i=1;i<=n;i++)if(i!=n/2&&i!=n/2+1)printf("%d %d\n",i,i);
    }
}

AtCoder Beginner Contest 253

We Love Forest

solution

题面：给出 条边，每次可以随机选择一条边加入图中，问进行 次后，图为森林的概率。

做法：考虑直接算答案，设 表示点集为 选了 条边的森林数，那么答案就是 。这东西是个经典转移东西了，枚举一个编号最小的点，然后枚举包含这个点的树集，那么就只需要知道补集的森林数和这个集的树数了，这里的转移是 。而树集也是容易算的，设 表示点集为 的树数，然后考虑枚举两个不交集合合成这个树，那么就是 ，这个 可以容斥算，即总集减去两个集内部的边数，那剩下的就是两个集之间的边数了。这里的复杂度是 。所以总复杂度就是 。

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
//2022.5.30 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=14;
namespace MAIN{
    int n,m;
    int fac[N],u[500+10],v[500+10],e[1<<N],f[1<<N],g[1<<N][N];
    inline void MAIN(const res &Case){
        n=read(),m=read(),fac[0]=1;
        for(res i=1;i<n;i++)fac[i]=mul(fac[i-1],i);
        for(res i=1;i<=m;i++)u[i]=read()-1,v[i]=read()-1;
        for(res S=0;S<1<<n;S++){
            for(res i=1;i<=m;i++){
                if(S&(1<<u[i])&&S&(1<<v[i]))e[S]++;
            }
        }
        f[0]=1;
        for(res S=1;S<1<<n;S++){
            if(pc(S)==1){f[S]=1;continue;}
            for(res nS=S&(S-1);nS;nS=(nS-1)&S){
                add(f[S],mul(mul(f[nS],f[S^nS]),e[S]-e[nS]-e[S^nS]));
            }
            f[S]=mul(f[S],qpow(2*(pc(S)-1)));
        }
        for(res i=0;i<n;i++){
            for(res S=0;S<1<<n;S++){
                if(i==pc(S)-1)g[S][i]=f[S];
                res T=lowbit(S);
                for(res nS=S;nS;nS=(nS-1)&S){
                    if(nS&T){
                        if(i-pc(nS)+1>=0){
                            add(g[S][i],mul(f[nS],g[S^nS][i-pc(nS)+1]));
                        }
                    }
                }
            }
        }
        res sz=(1<<n)-1;
        for(res i=1;i<n;i++)printf("%d\n",mul(g[sz][i],mul(fac[i],qpow(qpow(m,i)))));
    }
}

AtCoder Regular Contest 141

Non-divisible Set

solution

题面：一个集合被称为好集合，当且仅当里面的任意两个不同元素之间都是倍数关系。现给出 个小于等于 不同的数，问对于每一个数而言，是否存在一个大小为 的好集合包含它。

做法： 其实是个很大的提示，虽然任意大小也能做。

考虑所有奇数只有 个，这意味着对一个数 而言（ 其中 为奇数），好集合中的 是独一无二。而若要合法，则要求所有整除 或者被 的整除的 有一些大小关系，一边是最小值要大于，一边是最大值要小于，同时要一定存在一组解。那么按照这东西维护就行了，时间复杂度 。

任意大小的话就多个二分而已，那样时间复杂度是不变的。

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
//2022.6.4 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=6e5+10;
namespace MAIN{
    int n,m;
    int a[N],mx[N],mn[N],lmn[N],lmx[N],ans[N],p[N];
    vector<int> B[N],G[N];
    inline void MAIN(const res &Case){
        n=read(),m=read();
        for(res i=1;i<=2*m;i++)mn[i]=lmn[i]=100,lmx[i]=mx[i]=-1;
        for(res i=1;i<=n;i++)a[i]=read();
        sort(a+1,a+n+1);
        for(res i=1;i<=n;i++){
            res A=a[i],c=0;
            while(~A&1)A>>=1,c++;
            mx[A]=max(mx[A],c);
            mn[A]=min(mn[A],c);
            p[a[i]]=c;
            B[A].pb(a[i]);
        }
        for(res i=2*m-1;i>=1;i-=2){
            if(mx[i]==-1){
                for(res j=1;j<=n;j++)puts("No");
                return;
            }
            res u=-1;
            for(res j=i+i+i;j<=2*m;j+=i+i){
                u=max(u,lmx[j]);
            }
            for(auto x:B[i])if(p[x]>u){lmx[i]=p[x];break;}
            if(lmx[i]==-1){
                for(res j=1;j<=n;j++)puts("No");
                return
            }
        }
        for(res i=1;i<=2*m;i++)for(res j=i;j<=2*m;j+=i)G[j].pb(i);
        for(res i=1;i<=2*m;i+=2){
            res u=100;
            for(auto x:G[i])if(x<i)u=min(u,lmn[x]);
            for(auto x:B[i])if(p[x]<u)lmn[i]=p[x];
        }
        for(res i=1;i<=n;i++){
            res A=a[i],c=0;
            while(~A&1)A>>=1,c++;
            if(c<=lmn[A]&&c>=lmx[A])puts("Yes");
            else puts("No");
        }
    }
}

Codechef Starters 41

Parity Fun

solution

题面：合并两个数的方式是，若它们同奇偶，则合并为两数之差（ 这样显然可能有两个 ），否则合并为两数之和。给 个数，合并成一个，问最终不同数的可能数。

做法：那天晚上后来去吃 rng 的瓜了，今天候机时想了想发现不难。

首先注意到全偶数时，一定是一个减另一个，这个可以特判掉。若存在两个奇数，则可以让其中一个奇数加掉所有偶数，另一个奇数又可以减这个奇数，那么偶数的符号就是任意的了。若只有一个奇数，除了所有偶数的和不能减掉后，其他符号也是任意的。于是只用考虑全奇数的情况，经过手玩或者归纳法证明，可以发现奇数符号为正的是奇数个数除以二上取整，那么直接背包算出答案。注意到背包是只有 的，所以 bitset 压个位，这里复杂度就是 。算完所有奇数后合并奇偶数，这也可以 bitset 优化，所以总复杂度就是 。

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
//2022.6.3 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e2+10;
namespace MAIN{
    int n;
    int f[N][N*N*2];
    bitset<20000+10> B,C,g[N][N];
    inline void MAIN(const res &Case){
        n=read();
        vector<int> A[2];
        res s=0,t=0;
        for(res i=1;i<=n;i++){
            res x=read();
            A[x&1].pb(x);
            if(x&1)s+=x;
            else t+=x;
        }
        if(A[0].size()==n){
            f[0][10000]=1;
            res i=1;
            for(auto x:A[0]){
                for(res j=-10000;j<=10000;j++){
                    if(!f[i-1][j+10000])continue;
                    f[i][j-x+10000]=1,f[i][x-j+10000]=1;
                }
                i++;
            }
            res ans=0;
            for(res j=-10000;j<=10000;j++)ans+=f[i-1][j+10000];
            printf("%d\n",ans-2);
            return;
        }
        f[0][10000]=1;
        res i=1;
        for(auto x:A[0]){
            for(res j=-10000;j<=10000;j++){
                if(!f[i-1][j+10000])continue;
                f[i][j-x+10000]=1,f[i][x-j+10000]=1,f[i][j+x+10000]=1;
            }
            i++;
        }
        res ax=i;
        g[0][0].set(10000,true);
        i=1;
        for(auto x:A[1]){
            for(res j=0;j<i;j++){
                g[i][j+1]|=g[i-1][j]<<x;
                g[i][j]|=g[i-1][j]>>x;
            }
            i++;
        }
        if(i>2);
        else f[ax-1][-t+10000]=0;
        for(res j=-10000;j<=10000;j++){
            if(f[ax-1][j+10000])B.set(j+10000,true);
        }
        res p=i/2;
        for(res j=-10000;j<=10000;j++){
            if(g[i-1][p][j+10000]){
                if(j>0)C|=B<<j;
                else C|=B>>(-j);
            }
        }
        printf("%d\n",(int)C.count());
    }
}

Codeforces Round #792

Euclid Guess

solution

题面：对一个数对执行 的流程如下：

1
2
3
4
5
6
7
8
9
10
11
12
function Euclid(a, b):
    if a < b:
        swap(a, b)

    if b == 0:
        return a

    r = reminder from dividing a by b
    if r > 0:
        append r to the back of t

    return Euclid(b, r)

现给出长度为 的序列 ，试构造长度小于等于 每个数小于等于 的数对序列使得对每个数对执行 后的序列的某一个排列等于给出的序列。

做法：首先有个显然的想法是一步到位，即对一个 ，我们直接用 只用递归一次就出它且只出它。此时 最小是 ， 则最小是 。但有个 的限制，所以对于 的数要有不同的处理方式。考虑此时出 的 出来的序列是 ，由于 ，所以 。考虑最后一个 ，这个是 ，于是也是 的因子。同时，此时 一定小于 ，而且 此时只能等于 ， 等于 ，这说明了 。而小于 的，自己就可以构造出解。那么我们不妨让 ，这样一定不劣。于是此时要满足 。那么这就是个二分图匹配，网络流算就 了，当然这题匈牙利也行，因为最坏情况下 也是要除以 的。

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
//2022.6.25 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e3+10;
namespace MAIN{
    int n,m;
    vector<int> G[N];
    int a[N],vis[N];
    int dfs(res x){
        if(vis[x])return 0;
        vis[x]=1;
        for(auto tox:G[x]){
            if(!vis[tox]){vis[tox]=x;return 1;}
        }
        for(auto tox:G[x]){
            if(dfs(vis[tox])){vis[tox]=x;return 1;}
        }
        return 0;
    }
    inline void MAIN(const res &Case){
        n=read(),m=read();
        vector<int> l,r;
        for(res i=1;i<=n;i++){
            a[i]=read(),vector<int>().swap(G[i]),vis[i]=0;
            if(a[i]<=m/3)l.pb(i);
            else r.pb(i);
        }
        for(auto x:l)for(auto y:r){
            if(a[y]%a[x]==0&&(LL)a[y]*2+a[x]<=m)G[y].pb(x);
        }
        res cnt=0;
        for(auto x:r){
            for(auto y:r)vis[y]=0;
            cnt+=dfs(x);
        }
        if(cnt<r.size()){puts("-1");return;}
        vector<Pair> ans;
        for(auto x:l){
            if(!vis[x])ans.emplace_back(3*a[x],2*a[x]);
            else ans.emplace_back(2*a[vis[x]]+a[x],a[vis[x]]+a[x]);
        }
        printf("%d\n",(int)ans.size());
        for(auto [x,y]:ans)printf("%d %d\n",x,y);
    }
}

Codeforces Round #803 (Div. 2)

Long Binary String

solution

题意：开局有一个长度为 的全零串，给出一个长度为 的 字符串，每次可以拿这个串去异或开始那个串的任意连续位置，使得那个串只有两个 ，且 的位置最靠前（ 字典序最大 ），或输出无解。

做法：考虑将字符串看成模 意义下的多项式，同时去掉首零和末零后，于是题意等价于找到最小的 使得存在一个 满足 ，此时的 是任意的，所以也等价于 。这东西就是个 bsgs，时间复杂度 。

稍微讲下如何做多项式乘法，考虑到 bsgs 的第二轮时是做一个 乘 的过程，考虑把 写成 ，然后每一项乘上去，再加起来。乘上去的过程等价于每次乘 再取模，而取模恰好是异或，所以就很好地完成了乘法任务。

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
//2022.6.29 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int HashMod=100007;
namespace MAIN{
    int n;
    char str[50];
    struct HashTable{
        struct Line{
            LL u,v;
            int next;
        }e[10000000];
        int h[HashMod],cnt;
        inline void Add(const LL &u,const LL &v,const LL &w){
            e[++cnt]={w,v,h[u]},h[u]=cnt;
        }
        inline void Hash(const LL &x,const LL &k){
            Add(x%HashMod,k,x);
        }
        inline LL Query(const LL &x){
            LL s=x%HashMod;
            for(res i=h[s];i;i=e[i].next)if(e[i].u==x)return e[i].v;
            return -1;
        }
    }Hash;
    inline LL bsgs(const LL &p){
        res m=(int)sqrtl(p),u=63-__builtin_clzll(p);
        LL t=1;
        for(res i=1;i<=m;i++){
            t<<=1;
            if(t>>u&1)t^=p;
            if(t==1)return i;
            Hash.Hash(t,i);
        }
        LL tt=t;
        for(res i=2;i<=2*m;i++){
            LL ret=0,x=tt;
            for(res j=0;j<u;j++){
                if(t>>j&1)ret^=x;
                x<<=1;
                if(x>>u&1)x^=p;
            }
            t=ret;
            LL k=Hash.Query(t);
            if(k!=-1)return (LL)i*m-k;
        }
    }
    inline void MAIN(const res &Case){
        scanf("%s",str+1);
        n=(int)strlen(str+1);
        LL P=0;
        res m=0,s=0;
        while(str[n]=='0'&&n>=1)n--;
        if(n==0){puts("-1");return;}
        for(res i=1;i<=n;i++){
            if(str[i]=='1'){m=i;break;}
        }
        for(res i=1;i<=n;i++)s+=str[i]=='1';
        if(s==1){
            printf("%d %d\n",m,m+1);
            return;
        }
        for(res i=m;i<=n;i++)P|=((LL)str[i]-'0')<<(i-m);
        LL op=bsgs(P);
        if(op==-1)puts("-1");
        else printf("%lld %lld\n",m,m+op);
    }
}

2022 Hubei Provincial Collegiate Programming Contest

C. Potion(hard version)

solution

题意：有一个容量 且仅有一个刻度 （从底部往上）的量杯，有两类水，求最小接水步数使得杯子里面两类水的比例为 ，或者输出无解。

做法：首先 和 互相约分是显然的，这个证明也不算太难。然后考虑每次操作是做了啥，假设此时的两类水的比例分别是 ，如果当前添加第一类，那么比例就是 ，添加第二类就换一下。注意到每次总和就是乘上个 ，也可以证明 约分后 等于 是有解的一个条件，同时 就是最小操作次数。

接下来考虑 次操作后 分别可以变成啥样，注意到 的幂次都是每次添加一次，这意味着最终 的和式中每一项的 的幂次都是一致的。考虑第 次给某一个接水到了第 次所占的贡献，发现是 ，第一次特殊点，是 。通分一下，于是 总是 的某个子集和，其中 从 到 。

接下来只要算 是不是某个子集和就行，这个是容易的，注意到除了 ，其他都是 的倍数，所以讨论下有没有 ，然后看看是不是 的倍数，以此来确定最小的 的幂次，接着除掉，随便算算即可。

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
//2022.7.3 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    LL c;
    LL pw[70];
    int solve(LL S,res n){
        res fl=0;
        if(n<0)return 0;
        if(S<0)return 0;
        if(S==0)return 1;
        if(S%c==0)fl|=solve(S/c,n-1);
        if((S-pw[n-1])%c);
        else fl|=solve((S-pw[n-1])/c,n-1);
        return fl;
    }
    inline void MAIN(const res &Case){
        LL x=Read(),y=Read(),a=Read(),b=Read();
        LL g=gcd(x,y);
        x/=g,y/=g,g=gcd(a,b),a/=g,b/=g;
        c=a+b;
        pw[0]=1;
        for(res i=1;i<=68;i++)pw[i]=pw[i-1]*a;
        LL ret=c,r=1;
        res n=0;
        for(res i=1;;i++){
            r*=a;
            if(ret==x+y){n=i;break;}
            if(ret>((ld)x+y)/c){puts("-1");return;}
            ret*=c;
        }
        res fl=0;
        if(x%b==0)fl|=solve(x/b,n);
        if(x>=pw[n]){
            x-=pw[n];
            if(x%b==0)fl|=solve(x/b,n);
        }
        if(fl)printf("%d\n",n+1);
        else puts("-1");
    }
}

D. Transition

solution

题意：有两个操作，一是反转某位，代价为 ，另一个是交换两个位置，代价是两者位置绝对值之差。求把 序列 变成 的最小代价下的操作集合数量。

做法：显然最小代价下交换操作只能交换相邻的，或者交换距离为 ，而且交换的特点是只有两个刚好一次匹配上才会用交换，否则都不会使用交换，证明非常显然，随便算下贡献就可以发现了。于是就随便 dp 下即可，设 表示当前算到了 ， 位分别是 的方案数，直接转移就好了。时间复杂度 。

实际实现时可以发现没必要记录前两位的情况，直接枚举就行了，因为对 位以前是无影响的。

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
//2022.7.3 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=3e5+10;
namespace MAIN{
    int n;
    char str[N];
    int a[N],b[N];
    int f[N],g[N];
    inline void upd(const res &x,const res &y,const res &c){
        if(f[x]>f[y]+c)f[x]=f[y]+c,g[x]=g[y];
        else if(f[x]==f[y]+c)add(g[x],g[y]);
    }
    inline void MAIN(const res &Case){
        n=read(),scanf("%s",str+1);
        for(res i=1;i<=n;i++)a[i]=str[i]-'0';
        scanf("%s",str+1);
        for(res i=1;i<=n;i++)b[i]=str[i]-'0';
        g[0]=1;
        for(res i=1;i<=n;i++){
            f[i]=n+1;
            if(a[i]==b[i])upd(i,i-1,0);
            if(a[i]!=b[i])upd(i,i-1,1);
            if(i>=2&&a[i]!=b[i]&&a[i-1]!=b[i-1]&&a[i]!=a[i-1])upd(i,i-2,1);
            if(i>=3&&a[i]!=b[i]&&a[i-2]!=b[i-2]&&a[i]!=a[i-2]){
                if(a[i-1]==b[i-1])upd(i,i-3,2),upd(i,i-3,2);
            }
        }
        printf("%d\n",g[n]);
    }
}

G. Brick

solution

题意：给一个正整数数组 ，每次可以把一个 加 或者把两个相等的 同时加 ，问使得所有 相等的最小高度或者输出无解。

做法：首先能发现的是否高度相等仅仅等价于奇偶性是否相等。另一个重要结论，删去两个相邻的奇偶性相等的数不影响结果，这也是显然的。于是，剩下来的就是一堆奇偶间隔的东西了。如果有剩两个及以上，那显然无解。如果只剩一个或者没剩，那么肯定有解。接下来就是考虑答案是多少了。稍微想一想，我们能整出一个贪心手段，考虑每个凹形区域，显然凹的地方必须加二，然后相邻相等的位置显然可以直接消掉，必不会影响答案。用个 vector 维护这个过程即可，时间复杂度 。

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
//2022.7.5 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    int n;
    int a[N],las[N],nxt[N];
    inline void MAIN(const res &Case){
        n=read();
        res mx=0;
        for(res i=1;i<=n;i++)a[i]=read(),mx=max(mx,a[i]),las[i]=i-1,nxt[i]=i+1;
        res m=n,now=1;
        while(now<n&&now){
            if((a[now]&1)==(a[nxt[now]]&1)){
                m-=2;
                nxt[las[now]]=nxt[nxt[now]];
                las[nxt[nxt[now]]]=las[now];
                if(las[now])now=las[now];
                else now=nxt[nxt[now]];
            }
            else {
                now=nxt[now];
            }
        }
        if(m>1)puts("-1");
        else {
            a[0]=a[n+1]=2000000000;
            vector<Pair> A,B;
            for(res i=1;i<=n;i++){
                if(a[i]&1){
                    if(!A.empty()&&(A.back().fi&1)!=(i&1)){
                        res l=A.back().fi,r=i;
                        res d=0;
                        while(!B.empty()&&B.back().fi>=l)d=max(d,B.back().se),B.pop_back();
                        if(max(a[l],a[r])>d)B.emplace_back(i,max(a[l],a[r])+1);
                        else B.emplace_back(i,d+2);
                        A.pop_back();
                    }
                    else A.emplace_back(i,a[i]);
                }
                else B.emplace_back(i,a[i]);
            }
            res ans=0;
            for(auto [x,y]:B)ans=max(ans,y);
            if(!A.empty())ans=inf;
            vector<Pair>().swap(A),vector<Pair>().swap(B);
            for(res i=1;i<=n;i++){
                if(~a[i]&1){
                    if(!A.empty()&&(A.back().fi&1)!=(i&1)){
                        res l=A.back().fi,r=i;
                        res d=0;
                        while(!B.empty()&&B.back().fi>=l)d=max(d,B.back().se),B.pop_back();
                        if(max(a[l],a[r])>d)B.emplace_back(i,max(a[l],a[r])+1);
                        else B.emplace_back(i,d+2);
                        A.pop_back();
                    }
                    else A.emplace_back(i,a[i]);
                }
                else B.emplace_back(i,a[i]);
            }
            res ret=0;
            for(auto [x,y]:B)ret=max(ret,y);
            if(!A.empty())ret=inf;
            printf("%d\n",min(ans,ret));
        }
    }
}

I. Latitude Compressor

solution

题意：求所有 阶排列的 次方有多少种不同的取值。

做法：我们都很熟悉置换群，知道旋转 次的形成了 个大小为 的环。那么这题直接考虑排列的 次是多少个环，假设此时大小为 的环有 个，那么对原排列的所有环而言，环大小 满足 的，要求 。于是显然取构造 ，设 表示是否可以有上述情况，那么答案就是

这东西就很显然了，随便转化下，就有

其中 。

所有 直接求就是调和级数的了，然后乘积换成 后再 ，于是总复杂度就是 了。

的求法显然，直接背包即可，不过好像有规律，但问题不大。

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
//2022.7.6 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=4e5+10;
namespace MAIN{
    int pos[N],inv[N];
    inline void NTT(res *A,const res &type,const res &lim){
        for(res i=0;i<lim;i++)if(i<pos[i])swap(A[i],A[pos[i]]);
        for(res mid=1;mid<lim;mid<<=1){
            res wn=qpow(type==1?G:GI,(kcz-1)/(mid<<1));
            for(res j=0;j<lim;j+=mid<<1){
                res w=1;
                for(res k=0;k<mid;k++,w=mul(w,wn)){
                    res x=A[j+k],y=mul(w,A[j+mid+k]);
                    A[j+k]=Add(x,y),A[j+mid+k]=Add(x,kcz-y);
                }
            }
        }
        if(type==-1){
            res INV=qpow(lim,kcz-2);
            for(res i=0;i<=lim;i++)A[i]=mul(A[i],INV);
        }
    }
    inline void derivation(const res *A,res *B,const res &lim){
        for(res i=1;i<lim;i++)B[i-1]=mul(i,A[i]);
        B[lim-1]=0;
    }
    inline void integral(const res *A,res *B,const res &lim){
        for(res i=1;i<lim;i++)B[i]=mul(A[i-1],inv[i]);
        B[0]=0;
    }
    int A[N],B[N],D[N],E[N];
    void getinv(const res *a,res *b,res lim){
        if(lim==1){b[0]=qpow(a[0]);return;}
        getinv(a,b,lim>>1);
        for(res i=0;i<lim;i++)A[i]=a[i],B[i]=b[i];
        res qaq=0,len=1;
        while(len<=lim)len<<=1,qaq++;
        for(res i=0;i<len;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(qaq-1));
        NTT(A,1,len),NTT(B,1,len);
        for(res i=0;i<len;i++)A[i]=mul(A[i],mul(B[i],B[i]));
        NTT(A,-1,len);
        for(res i=0;i<lim;i++)b[i]=Add(b[i],Add(b[i],kcz-A[i]));
        for(res i=0;i<len;i++)A[i]=B[i]=0;
    }
    inline void getln(const res *a,res *b,const res &lim){
        derivation(a,D,lim),getinv(a,E,lim);
        res qaq=0,len=1;
        while(len<=lim)len<<=1,qaq++;
        for(res i=0;i<len;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(qaq-1));
        NTT(D,1,len),NTT(E,1,len);
        for(res i=0;i<len;i++)D[i]=mul(D[i],E[i]);
        NTT(D,-1,len);
        integral(D,b,lim);
        for(res i=0;i<len;i++)D[i]=E[i]=0;
    }
    int F[N],G[N];
    void getexp(const res *a,res *b,res lim){
        if(lim==1){b[0]=1;return;}
        getexp(a,b,lim>>1);
        getln(b,G,lim);
        for(res i=0;i<lim;i++)F[i]=b[i],G[i]=Add(kcz-G[i],a[i]);
        G[0]=Add(G[0],1);
        res qaq=0,len=1;
        while(len<=lim)len<<=1,qaq++;
        for(res i=0;i<len;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(qaq-1));
        NTT(F,1,len),NTT(G,1,len);
        for(res i=0;i<len;i++)F[i]=mul(F[i],G[i]);
        NTT(F,-1,len);
        for(res i=0;i<lim;i++)b[i]=F[i];
        for(res i=0;i<len;i++)F[i]=G[i]=0;
    }
    int n,m;
    map<int,int> b[N];
    int a[N],finv[N],c[N],d[N];
    inline void MAIN(const res &Case){
        n=read(),m=read();
        inv[0]=inv[1]=finv[0]=finv[1]=1;
        for(res i=2;i<=n;i++)inv[i]=mul(inv[kcz%i],kcz-kcz/i);
        for(res i=2;i<=n;i++)finv[i]=mul(finv[i-1],inv[i]);
        for(res i=1;i<=n;i++)b[i][0]=1;
        for(res k=1;k<=m;k++){
            if(m%k==0){
                for(res i=1;i*k<=n;i++){
                    if(gcd(i*k,m)==k){
                        for(res j=k;(LL)j*i<=n;j++){
                            if(b[i].count(j-k))b[i][j]=1;
                        }
                    }
                }
            }
        }
        for(res i=n;i;i--){
            for(res j=0;j*i<=n;j++){
                a[j]=mul(b[i][j],finv[j]);
            }
            res l=1;
            while(l<=n/i)l<<=1;
            getln(a,c,l);
            for(res j=0;j*i<=n;j++){
                add(d[j*i],mul(c[j],qpow(qpow(i,j))));
            }
        }
        res l=1;
        while(l<=n)l<<=1;
        for(res i=0;i<=l;i++)a[i]=0;
        getexp(d,a,l);
        res ans=a[n];
        for(res i=1;i<=n;i++)ans=mul(ans,i);
        printf("%d\n",ans);
    }
}

M. Super Star Spectacle

solution

题意：收集器（华恋）在树的路径上巡逻，问确认树上没有很会润的 Star 最少需要几个收集器。

做法：首先题意要读懂，大概说的是一棵树，有一个可以光速润的东西，你可以卡住某些口让他不能经过，然后你的人也可以动，去搜寻他。

首先能注意到链是最舒适的，因为一条链只用一个人搜一下就行。但如果几条链有个根呢？容易发现，这样的答案显然为 。我们只要一个人卡住根的位置，然后让另一个人随便搜寻。于是这给我们一个思路，然后一个人占住某个节点，使得那个光速润的东西没法从这个节点的某一个分支润到另一个分支，此时再让另一个人去大力搜寻即可。

这样的话，我们考虑一个叶子到根的路径，这个路径上所有有分支的节点都占住一个人，然后叶子占了一个人。这个叶子上的人可以迅速搜到第一个分支节点处，然后把这个节点的其他几个分支全搜寻完。然后再让这个分支上的人往上搜到下一个分支处，然后它占住另一个位置，再让叶子上的这个人去照葫芦画瓢地搜完接下来的东西，以此类推，我们肯定能搜完所有节点。

但是，这仅仅叫能搜完，并不是最优解。为什么会这样呢？我们仔细考虑到底是不是必须要每个分支的节点都住一个人，发现不是必须的。容易发现，比如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
22
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
6 13
6 14
7 15
7 16
8 17
8 18
9 19
9 20
10 21
10 22

我们能发现当最开始的时候就选择最大的那个分支后，我们同时往回走，那么这就可以保证这个分支不被入侵了，也就意味着可以省下一个人。实际上，这题确实还是可以 做，论文链接。稍微看了下，大概就是所有情况只有七八类，大讨论下就能过了，那我肯定是不补了。

The 19th Zhejiang Provincial Collegiate Programming Contest

D. The Profiteer

solution

题意：给定 个商品的原价、涨价后的价格以及价值，令 表示花不超过 元钱最多能买走总价值多少的商品。 给定 和 ，统计有多少区间 满足将编号在该区间内 的商品涨价出售时，期望收益 。

做法：

K. Dynamic Reachability

solution

题意：给定 个点 条边的有向图，每条边的颜色是黑色或白色。 次操作，每次要么反转一条边的颜色，要么询问从 点出 发只沿着黑边走能否到达 点。

做法：

2022 Jiangsu Collegiate Programming Contest

B. Prime Ring Plus

solution

题意：将 分成若干个环，每个环上相邻两数之和是质数。

做法：

D. Finding Pairs

solution

题意：给定一个序列和一个数 ，每次询问一个区间，问在区间中找若干对不含重复元素的距离为 的数的最大权值和。

做法：本来以为想出了 的做法，结果发现还是关于 的，有点可惜。

我的想法是直接分治的，然后把经过中点的询问算一下，考虑此时右端点递增，然后左端点维护个后缀 dp 值，这样计算每个询问的时候，复杂度就是 ，那么总复杂度就是 。另一方面，当 特别大的时候，我们注意到模 的组不会太长，于是直接对原序列分块，每块长度为 。这样的话，我们处理出每块的信息，然后直接枚举块的所有区间处理出答案。这里复杂度是 ，然后注意到零散的时候，更新时间是 ，且只用更新和相邻的，所以这里也是能预处理的，复杂度一致。那么询问答案是直接得出的。综上，总复杂度 ，当 同阶。

实际上，直接回滚莫队就行，不过很难写罢了，时间复杂度一致的。

代码我写的回滚莫队，要注意多类讨论，比如分块点处向右 距离的位置是否要选，因为回滚左边的时候可能是要用到的。

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
//2022.7.13 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
const int block=320;
namespace MAIN {
	int n,K,q;
	int a[N];
	struct Q{
		int l,r,id;
		inline bool operator < (const Q &A) const {
			return l/block!=A.l/block?l/block<A.l/block:r<A.r;
		}
	}que[N];
	int id[N];
	LL ans[N];
	LL f[N][2],g[N][2],AAns[N],nf[N][2],ng[N][2],nans[N];
	int pos[N],Pos[N],vis[N],npos[N];
	inline void MAIN(const int &Case) {
		n=read(),K=read(),q=read();
		for(int i=1;i<=n;i++)a[i]=read(),id[i]=i%K;
		for(int i=1;i<=q;i++){
			int l=read(),r=read();
			que[i]={l,r,i};
		}
		sort(que+1,que+q+1);
		for(int i=1;i<=q;i++){
			if(que[i].l/block==que[i].r/block){
				auto [l,r,I]=que[i];
				for(int j=l;j<=r;j++){
					int t=id[j];
					LL F=f[t][0],G=f[t][1];
					f[t][0]=max(F,G);
					if(pos[t])f[t][1]=F+a[pos[t]]+a[j];
					else f[t][1]=0;
					pos[t]=j;
				}
				for(int j=l;j<=r;j++){
					int t=id[j];
					ans[I]+=max(f[t][0],f[t][1]);
					f[t][0]=f[t][1]=pos[t]=0;
				}
				continue;
			}
			int j=i;
			while(que[i].l/block==que[j].l/block&&j<=q)j++;
			int pr=(que[i].l/block+1)*block,p=pr;
			LL Ans=0;
			for(int _=i;_<j;_++){
				auto [l,r,I]=que[_];
				while(pr<=r){
					int t=id[pr];
					if(pr>p+K-1){
						LL F=f[t][0],G=f[t][1];
						f[t][0]=max(F,G);
						if(pos[t])f[t][1]=F+a[pos[t]]+a[pr];
						else f[t][1]=0;
					}
					if(pr>p+2*K-1){
						LL F=g[t][0],G=g[t][1];
						g[t][0]=max(F,G);
						if(pos[t])g[t][1]=F+a[pos[t]]+a[pr];
						else g[t][1]=0;
					}
					pos[t]=pr;
					if(pr<=p+K-1)Pos[t]=pr;
					LL F=max({f[t][0],f[t][1],g[t][0],g[t][1]});
					nf[t][1]=max(f[t][0],f[t][1]),nf[t][0]=max(g[t][0],g[t][1]);
					if(F>AAns[t])Ans+=F-AAns[t],AAns[t]=F;
					pr++;
				}
				LL nAns=Ans;
				int pl=p-1;
				while(pl>=l){
					int t=id[pl];
					if(!vis[t]){
						ng[t][0]=nf[t][0],ng[t][1]=nf[t][1],nans[t]=AAns[t],npos[t]=Pos[t];
						vis[t]=1;
					}
					LL F=ng[t][0],G=ng[t][1];
					ng[t][0]=max(F,G);
					if(npos[t])ng[t][1]=F+a[npos[t]]+a[pl];
					else ng[t][1]=0;
					npos[t]=pl;
					F=max({ng[t][0],ng[t][1]});
					if(F>nans[t])nAns+=F-nans[t],nans[t]=F;
					pl--;
				}
				ans[I]=nAns;
				pl=p-1;
				while(pl>=l){
					int t=id[pl];
					vis[t]=0,pl--;
				}
			}
			while(p<pr){
				int t=id[p];
				f[t][0]=f[t][1]=g[t][0]=g[t][1]=AAns[t]=nf[t][0]=nf[t][1]=pos[t]=Pos[t]=0;
				p++;
			}
			i=j-1;
		}
		for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	}
}

E. Playing Cards

solution

题意：给定两个序列 和 ，求一个全排列 ，求最小的可能的 ，输出方案。

做法：

G. GCD on Bipartite Graph

solution

题意：将 划分到两个集合，一个集合有 个元素，另一个有 个， 要求：从一个集合任选两个数，另一个集合也任选两个数， 这四个数的 。判断是否有解并构造方案。

做法：

H. Super Gray Pony

solution

题意：求长为 的 串 求 次格雷码后的结果，求格雷码是指将 看做二进制数，求其在 阶格雷码序列中的下标。

做法：

“蔚来杯”2022牛客暑期多校训练营1

B. Spirit Circle Observation

solution

题意：给定长度为 的数字串 ，计算满足下列条件的二元组 个数： 是 的子串； 长度相同； 。 即使有两个子串相同，只要它们在原串位置不同，则认为是不同的子串。

做法：注意到此刻的 满足分别等于 和 。考虑建出 SAM 后，枚举 parent 树上的一个结点，那么这个节点对应了我们枚举 ，然后暴力枚举 ，递归下去求解后面两个的个数。可以证明这样的个数是 的？所以预处理出 parent 树，然后 dfs 一遍处理出每个 right 集合的大小即可，时间复杂度 ， 是记忆化后的结果。

注意 节点的最长长度需要特判。

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
//2022.7.20 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=8e5+10;
namespace MAIN {
	struct Sam{
		int vis[10],par,len;
		inline void init(){
			memset(vis,0,sizeof(vis));
			par=len=0;
		}
	}sam[N];
	int cnt,las,rt,sz[N];
	inline void INIT(){
		cnt=las=rt=1;
	}
	inline void extend(const int &x){
		int p=las,np=++cnt;
		sam[np].len=sam[p].len+1;
		for(;p&&!sam[p].vis[x];p=sam[p].par)sam[p].vis[x]=np;
		if(!p)sam[np].par=rt;
		else {
			int q=sam[p].vis[x];
			if(sam[q].len==sam[p].len+1)sam[np].par=q;
			else {
				int nq=++cnt;
				memcpy(sam[nq].vis,sam[q].vis,sizeof(sam[nq].vis));
				sam[nq].par=sam[q].par;
				sam[nq].len=sam[p].len+1;
				sam[q].par=sam[np].par=nq;
				for(;p&&sam[p].vis[x]==q;p=sam[p].par)sam[p].vis[x]=nq;
			}
		}
		las=np,sz[np]=1;
	}
	int n;
	char str[N];
	int fa[N];
	vector<int> G[N];
	map<Pair,LL> f;
	void dfs(int x){
		for(auto tox:G[x])dfs(tox),sz[x]+=sz[tox];
	}
	LL solve(int x,int y){
		if(!x||!y)return 0;
		if(f.count({x,y}))return f[{x,y}];
		return f[{x,y}]=(LL)sz[x]*sz[y]+solve(sam[x].vis[9],sam[y].vis[0]);
	}
	inline void MAIN(const int &Case) {
		sam[0].len=-1;
		n=read(),scanf("%s",str+1),INIT();
		for(int i=1;i<=n;i++)extend(str[i]-'0');
		for(int i=1;i<=cnt;i++)G[fa[i]=sam[i].par].pb(i);
		dfs(1);
		LL ans=0;
		for(int i=1;i<=cnt;i++){
			LL ret=0;
			for(int p=0;p<9;p++)ret+=solve(sam[i].vis[p],sam[i].vis[p+1]);
			ans+=ret*(sam[i].len-sam[fa[i]].len);
		}
		printf("%lld\n",ans);
	}
}

C. Grab the Seat!

solution

题意：二维平面，屏幕是 的线段。有 行 列座位在屏幕前面，是坐标范围 的整点。有 个座位已经有人，求出到屏幕的视线不被任何人挡住的座位数量。 次询问，每次修改一个人的坐标后求出答案。

做法：这题没做就离谱，纯纯的签到题。

题意等价于有 个点，分别连向 与 ，问没被这个区域覆盖的点数 。考虑对每个 维护最小的 ，分别考虑两种线段的贡献。对于左线段而言，显然对一个固定的 而言，斜率越小的 越小，而此刻对一个点而言，它对应的 所对应到的 都是单调的。右线段也同理。直接就 了。

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
//2022.7.18 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN {
	int n,m,k,q;
	int x[N],y[N];
	int mn[N],A[N],B[N];
	inline void MAIN(const int &Case) {
		n=read(),m=read(),k=read(),q=read();
		for(int i=1;i<=k;i++)x[i]=read(),y[i]=read();
		while(q--){
			int p=read();
			x[p]=read(),y[p]=read();
			for(int i=1;i<=m;i++)mn[i]=n+1;
			for(int i=1;i<=k;i++)mn[y[i]]=min(mn[y[i]],x[i]);
			for(int i=1,t=0;i<=m;i++){
				if(mn[i]){
					if(!t)t=i;
					else if((LL)mn[i]*(t-1)<(LL)mn[t]*(i-1))t=i;
				}
				if(!t)A[i]=n;
				else {
                    if(t==1)A[i]=mn[i]-1;
                    else {
					   LL K=((LL)mn[t]*i-mn[t]-1)/(t-1);
					   if(K<=n)A[i]=(int)K;
					   else A[i]=0;
                    }
				}
			}
			for(int i=m,t=0;i>=1;i--){
				if(mn[i]){
					if(!t)t=i;
					else if((LL)mn[i]*(m-t)<(LL)mn[t]*(m-i))t=i;
				}
				if(!t)B[i]=n;
				else {
                    if(t==m)B[i]=mn[i]-1;
                    else {
					   LL K=(-(LL)mn[t]*i+(LL)mn[t]*m-1)/(m-t);
					   if(K<=n)B[i]=(int)K;
					   else B[i]=0;
                    }
				}
			}
			LL ans=0;
			for(int i=1;i<=m;i++){
				ans+=min(A[i],B[i]);
			}
			printf("%lld\n",ans);
		}
	}
}

E. LTCS

solution

题意：定义一棵带点权的有根树 是 的子序列当且仅当满足以下条件： 的点到 的点存在一个单射 对于 中的所有点 有 。如果 在 中是 的祖先，则 在 中是 的祖先。如果 在 中是 的父亲，则在 中 在 的简单路径上。求两棵以 为根的树 的最大公共子序列大小。

做法：考虑一个暴力 dp，设 表示 的子树与 的子树匹配后的最大值，转移就是要么 不匹配，则从 与 中找最大值，要么就是匹配，则此刻要将它们的儿子分别匹配上，儿子的匹配等价于二分图最大权匹配，看起来复杂度是 ，实际上每个节点的匹配复杂度都是儿子数量，于是总复杂度实际上是 ，这东西放放缩就是 了。

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
//2022.7.20 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1000+10;
namespace MAIN {
	struct KM{
		int g[N][N];
		int vis[N],pre[N],mat[N];
		int cur,pn;
		int w[N],slack[N];
		int n,m;
		inline void init(const int &p,const int &q){
			n=p,m=q;
			for(int i=1;i<=n+m;i++)mat[i]=w[i]=0;
			for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)g[i][j]=0;
		}
		inline void add(const int &u,const int &v,const int &w){
			g[u][v]=w;
		}
		inline void bfs(const int &S){
			for(int i=0;i<=n+m;i++)vis[i]=0,slack[i]=inf,pre[i]=0;
			cur=pn=0,mat[0]=S;
			while(233){
				int x=mat[cur];
				int dis=inf;
				vis[cur]=1;
				for(int i=n+1;i<=n+m;i++){
					if(vis[i])continue;
					int tmp=w[i]+w[x]-g[x][i-n];
					if(tmp<slack[i])slack[i]=tmp,pre[i]=cur;
					if(slack[i]<dis)dis=slack[i],pn=i;
				}
				w[mat[0]]-=dis,w[0]+=dis;
				for(int i=n+1;i<=n+m;i++){
					if(vis[i])w[i]+=dis,w[mat[i]]-=dis;
					else slack[i]-=dis;
				}
				cur=pn;
				if(!mat[cur])break;
			}
			while(cur)mat[cur]=mat[pre[cur]],cur=pre[cur];
		}
		inline int solve(){
			for(int i=1;i<=n;i++)bfs(i);
			int ret=0;
			for(int i=n+1;i<=n+m;i++)ret+=g[mat[i]][i-n];
			return ret;
		}
	}A;
	int c1[N],c2[N];
	vector<int> G[N],E[N];
	int f[N][N];
	int dfs(int x,int fax,int y,int fay){
		if(~f[x][y])return f[x][y];
		int &ret=f[x][y];
		ret=0;
		for(auto tox:G[x])if(tox!=fax)ret=max(ret,dfs(tox,x,y,fay));
		for(auto toy:E[y])if(toy!=fay)ret=max(ret,dfs(x,fax,toy,y));
		if(c1[x]==c2[y]){
			int n=(int)(G[x].size()),m=(int)(E[y].size());
			if(n<m){
				A.init(n,m);
				for(int i=0;i<n;i++){
					if(G[x][i]==fax)continue;
					for(int j=0;j<m;j++){
						if(E[y][j]==fay)continue;
						A.add(i+1,j+1,dfs(G[x][i],x,E[y][j],y));
					}
				}
			}
			else {
				A.init(m,n);
				for(int j=0;j<m;j++){
					if(E[y][j]==fay)continue;
					for(int i=0;i<n;i++){
						if(G[x][i]==fax)continue;
						A.add(j+1,i+1,dfs(G[x][i],x,E[y][j],y));
					}
				}
			}
			ret=max(ret,A.solve()+1);
		}
		return ret;
	}
	inline void MAIN(const int &Case) {
		int n=read(),m=read();
		for(int i=1;i<=n;i++)c1[i]=read();
		for(int i=1;i<=m;i++)c2[i]=read();
		for(int i=1;i<n;i++){
			int u=read(),v=read();
			G[u].pb(v),G[v].pb(u);
		}
		for(int i=1;i<m;i++){
			int u=read(),v=read();
			E[u].pb(v),E[v].pb(u);
		}
		memset(f,-1,sizeof(f));
		printf("%d\n",dfs(1,0,1,0));
	}
}

F. Cut

solution

题意：给定 到 的排列 ，有 次以下三种操作： 将 从小到大排序。 将 从大到小排序。 询问 中最长的奇偶交替子序列。

做法：考虑类似 ODT 那样的想法，这里是把有序区间看成一个连续段，然后每个连续段用权值线段树维护，注意到连续段都是有序的，所以很凑巧，权值线段树的下标也正好是有序的，然后所有连续段用一棵大线段树维护信息。考虑询问的东西，发现可以 dp，然后经典的 dp 转成矩阵形式，于是就可以维护了。排序操作等价于线段树分裂再合并，虽然我一直不理解线段树合并的复杂度，不过听说是看总结点数，那这个就简单了，势能分析下就可以知道拆分的次数是 ，所以总复杂度就是 ，假设 同阶。

代码实现上我加了个节点回收，不想算空间了。

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
//2022.7.20 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN {
	struct P{
		int l,r,mx,sz;
	}tr[N*60],Tr[N<<2];
    inline P operator + (const P &A,const P &B){
        if(!A.sz)return B;
        if(!B.sz)return A;
        return {A.l,B.r,A.mx+B.mx+(A.r!=B.l),A.sz+B.sz};
    }
	int ls[N*60],rs[N*60];
	int st[N*60],top,tot;
	inline int newnode(){
		return top?st[top--]:++tot;
	}
	inline void del(const int &x){
		st[++top]=x,ls[x]=rs[x]=0;
	}
	void modify(int &rt,int l,int r,const int &p){
		if(!rt)rt=newnode();
		if(l==r){
			tr[rt]={p&1,p&1,0,1};
			return;
		}
		int mid=(l+r)>>1;
		if(p<=mid)modify(ls[rt],l,mid,p);
		else modify(rs[rt],mid+1,r,p);
		tr[rt]=tr[ls[rt]]+tr[rs[rt]];
	}
	int merge(int x,int y){
		if(!x||!y)return x|y;
		ls[x]=merge(ls[x],ls[y]);
		rs[x]=merge(rs[x],rs[y]);
		del(y),tr[x]=tr[ls[x]]+tr[rs[x]];
		return x;
	}
    void split_in(int x,int &y,int k){
		if(!k)return;
		y=newnode();
		if(k>=tr[rs[x]].sz)split_in(ls[x],ls[y],k-tr[rs[x]].sz),swap(rs[x],rs[y]);
		else split_in(rs[x],rs[y],k);
		tr[x]=tr[ls[x]]+tr[rs[x]];
		tr[y]=tr[ls[y]]+tr[rs[y]];
	}
	void split_de(int x,int &y,int k){
		if(!k)return;
		y=newnode();
		if(k>=tr[ls[x]].sz)split_de(rs[x],rs[y],k-tr[ls[x]].sz),swap(ls[x],ls[y]);
		else split_de(ls[x],ls[y],k);
		tr[x]=tr[ls[x]]+tr[rs[x]];
		tr[y]=tr[ls[y]]+tr[rs[y]];
	}
	int RT[N];
	int opt[N];
	void update(int rt,int l,int r,const int &p){
		if(l==r){
			Tr[rt]=tr[RT[l]];
			if(opt[l])swap(Tr[rt].l,Tr[rt].r);
			return;
		}
		int mid=(l+r)>>1;
		if(p<=mid)update(rt<<1,l,mid,p);
		else update(rt<<1|1,mid+1,r,p);
		Tr[rt]=Tr[rt<<1]+Tr[rt<<1|1];
	}
	P query(int rt,int l,int r,const int &L,const int &R){
		if(L<=l&&r<=R)return Tr[rt];
		int mid=(l+r)>>1;
		if(L<=mid&&R>mid)return query(rt<<1,l,mid,L,R)+query(rt<<1|1,mid+1,r,L,R);
		if(L<=mid)return query(rt<<1,l,mid,L,R);
		return query(rt<<1|1,mid+1,r,L,R);
	}
	set<int> S;
    int n,m;
	auto split(const int &x){
		auto p=S.lower_bound(x);
		if(*p==x)return p;
		p--;
		if(opt[*p]==0)split_in(RT[*p],RT[x],*next(p)-x);
		else split_de(RT[*p],RT[x],*next(p)-x);
		update(1,1,n,*p),opt[x]=opt[*p],update(1,1,n,x);
		return S.insert(x).fi;
	}
	inline void MAIN(const int &Case) {
		n=read(),m=read(),S.insert(n+1);
		for(int i=1;i<=n;i++){
			S.insert(i);
			int v=read();
			modify(RT[i],1,n,v),update(1,1,n,i);
		}
		for(int i=1;i<=m;i++){
			int op=read()-1,l=read(),r=read();
			auto L=split(l),R=split(r+1);
            L++;
			if(op<=1){
				for(auto it=L;it!=R;it++)merge(RT[l],RT[*it]),RT[*it]=0,update(1,1,n,*it);
				S.erase(L,R),opt[l]=op,update(1,1,n,l);
			}
			else printf("%d\n",query(1,1,n,l,r).mx+1);
		}
	}
}

H. Fly

solution

题意： 种物品每种有无数个，第 个物品的体积为 ，求解选择物品总体积不超过 的方案数。 此外，有 个限制，第 个限制形如第 个物品所选的数量二进制表示下从低到高第 位必须为 。

做法：考虑数位 dp，设 表示当前 dp 到了第 位， 表示 以内的位是否比 大， 表示超过 的位是多少。发现转移很容易，设 表示第 位背包容量为 的方案数，这个东西就是 然后除以限制，前者直接分治 FFT 就是 ，其中 ，后者每次暴力除掉，每次复杂度 ，一共 次。然后转移就是 ，按照数位 dp 的逻辑判一判即可。总时间复杂度 。

其实细细想来就是常系数线性递推的魔改，只是把快速幂魔改成了数位 dp。

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//2022.7.20 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
namespace MAIN {
	namespace NTT {
		const int G=3,GI=332748118;
		inline vector<int> Omega(const int &L){
			int wn=qpow(G,kcz/L);
			vector<int> w(L);
			w[L>>1]=1;
			for(int i=L/2+1;i<=L-1;i++)w[i]=mul(w[i-1],wn);
			for(int i=L/2-1;i>=1;i--)w[i]=w[i<<1];
			return w;
		}
		auto W=Omega(1<<21);
		inline void DIF(int *A,const int &n){
			for(int k=n>>1;k;k>>=1)
				for(int i=0;i<n;i+=k<<1)
					for(int j=0;j<k;j++){
						int x=A[i+j],y=A[i+j+k];
						A[i+j]=Add(x,y),A[i+j+k]=mul(Add(x,kcz-y),W[k+j]);
					}
		}
		inline void IDIT(int *A,const int &n){
			for(int k=1;k<n;k<<=1)
				for(int i=0;i<n;i+=k<<1)
					for(int j=0;j<k;j++){
						int x=A[i+j],y=mul(A[i+j+k],W[k+j]);
						A[i+j]=Add(x,y),A[i+j+k]=Add(x,kcz-y);
					}
			int INV=kcz-(kcz-1)/n;
			for(int i=0;i<n;i++)A[i]=mul(A[i],INV);
			reverse(A+1,A+n);
		}
	}
	inline int norm(const int &n){
		return 1<<(__lg(n-1)+1);
	}
	struct Poly : public vector<int>{
#define T (*this)
		using vector<int>::vector;
		inline int deg()const{
			return (int)(size());
		}
		inline Poly &operator^=(const Poly &b){
			if(b.deg()<deg())resize(b.deg());
			for(int i=0,sz=deg();i<sz;i++)T[i]=mul(T[i],b[i]);
			return T;
		}
		inline Poly &operator <<= (const int &k){
			return insert(begin(),k,0),T;
		}
		inline Poly operator << (const int &r) const {
			return Poly(T)<<=r;
		}
		inline Poly operator >> (const int &r) const {
			return r>=deg()?Poly():Poly(begin()+r,end());
		}
		inline Poly & operator >>= (const int &r){
			return T=T>>r;
		}
		inline Poly mod(const int &k) const {
			return k<deg()?Poly(begin(),begin()+k):T;
		}
		inline friend void dft(Poly &a){
			NTT::DIF(a.data(),(int)(a.size()));
		}
		inline friend void idft(Poly &a){
			NTT::IDIT(a.data(),(int)(a.size()));
		}
		inline friend Poly conv(Poly a,Poly b,const int &n) {
			a.resize(n),dft(a);
			b.resize(n),dft(b);
			return idft(a^=b),a;
		}
		inline friend Poly operator*(const Poly &a,const Poly &b){
			int n=(int)(a.size()+b.size())-1;
			return conv(a,b,norm(n)).mod(n);
		}
		inline Poly rev() const {
			return Poly(rbegin(),rend());
		}
		inline Poly mulT(const Poly& b){
			return T*b.rev()>>(b.deg()-1);
		}
#undef T
	};
	int a[N];
	LL p[N];
	Poly solve(int l,int r){
		if(l==r){
			Poly A(a[l]+1);
			A[0]=A[a[l]]=1;
			return A;
		}
		int mid=(l+r)>>1;
		return solve(l,mid)*solve(mid+1,r);
	}
	Poly f[2];
	inline void MAIN(const int &Case) {
		int n=read();
		LL m=Read();
		int K=read(),s=0;
		for(int i=1;i<=n;i++)a[i]=read(),s+=a[i];
		for(int i=1;i<=K;i++){
			int b=read(),c=read();
			p[b]|=1ll<<c;
		}
		Poly A=solve(1,n);
		f[0].pb(1);
		for(int t=0;t<60;t++){
			Poly B=A;
			for(int i=1;i<=n;i++){
				if(p[i]>>t&1)
					for(int k=a[i];k<=s;k++)add(B[k],kcz-B[k-a[i]]);
			}
			Poly g=f[0]*B,h=f[1]*B;
			Poly o[2];
			o[0].resize(max(g.size(),h.size())/2+1);
			o[1].resize(max(g.size(),h.size())/2+1);
			int c=(int)(m>>t&1);
			if(c==1){
				for(int i=0,sz=(int)g.size();i<sz;i++){
					add(o[0][i/2],g[i]);
				}
				for(int i=0,sz=(int)h.size();i<sz;i++){
					if(~i&1)add(o[0][i/2],h[i]);
					else add(o[1][i/2],h[i]);
				}
			}
			else {
				for(int i=0,sz=(int)g.size();i<sz;i++){
					if(~i&1)add(o[0][i/2],g[i]);
					else add(o[1][i/2],g[i]);
				}
				for(int i=0,sz=(int)h.size();i<sz;i++){
					add(o[1][i/2],h[i]);
				}
			}
			f[0]=o[0],f[1]=o[1];
		}
		printf("%d\n",f[0][0]);
	}
}

I. Chiitoitsu

solution

题意：初始手牌有 张麻将牌，相同牌至多出现 张。每轮可以从牌堆摸牌，若达成七对子则自摸胡牌。若不然则选择手牌中某张牌并丢弃之。给定初始手牌，求最优策略下达成七对子的期望轮数。

做法：首先把题意读对，我上来就以为和 ZJOI 那道题一致，直接卡了一年的时间。于是最优策略显然是若到手的牌已经有一张，那就随便丢弃一张单的，否则丢弃这张到手的。这样的话，实际上初始情况只有 种，我们只需要看初始对子几张即可。于是在外面打个 的暴力就可以通过此题。否则直接期望 dp，设 表示当前牌山里剩 张牌，手上单张的为 张，注意到此时这 张牌在牌山里一定剩 张，所以可以直接转移。

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
//2022.7.18 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN {
	inline void MAIN(const int &Case) {
		string A;
		cin>>A;
		map<string,int> M;
		for(int i=0,sz=(int)A.size();i<sz;i+=2){
			string B;
			B+=A[i],B+=A[i+1];
			M[B]++;
		}
		int s=0;
		for(auto [x,y]:M)if(y==2)s++;
		printf("Case #%d: ",Case);
		if(s==0)puts("927105416");
		else if(s==1)puts("745749140");
		else if(s==2)puts("707741534");
		else if(s==3)puts("882102328");
		else if(s==4)puts("781250051");
		else if(s==5)puts("100000041");
		else if(s==6)puts("31");
	}
}

J. Serval and Essay

solution

题意：有一张 个点 条边的无重边无自环的有向图。初始时可以选择一个点染黑，其余点均为白点。若某个点所有入边的起点均为黑点，则该点可以被染黑。最大化图中黑点数量。

做法：设 表示 染黑之后黑点的集合，显然集合之间要么包含要么不交，于是就形成了一个森林，那么答案就是最大的树。考虑去找这个森林，对每棵树，我们自底而上地去合并节点。若一个相关联的点的所有入点都被某个 的 所包含，那么显然 是会包含这个关联点的。但显然这样合并复杂度是 ， 是用 set 维护入点情况。不过启发式合并下就 了，可以通过。

题解还有个做法是考虑随机合并这些节点，可以证明期望复杂度是 。

代码是启发式合并的。

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
//2022.7.18 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN {
	int n;
	set<int> out[N],in[N];
	int fa[N];
	inline int find(int x){
		while(x!=fa[x])x=fa[x]=fa[fa[x]];
		return x;
	}
	void merge(int x,int y){
		x=find(x),y=find(y);
		if(x==y)return;
		if(out[x].size()<out[y].size())swap(x,y);
		vector<Pair> A;
		for(auto p:out[y]){
			out[x].insert(p),in[p].insert(x);
			if(in[p].find(y)!=in[p].end())in[p].erase(y);
			if(in[p].size()==1)A.emplace_back(p,*in[p].begin());
		}
		fa[y]=x;
		for(auto [p,q]:A)merge(p,q);
	}
	int ans[N];
	inline void MAIN(const int &Case) {
		n=read();
		for(int i=1;i<=n;i++)fa[i]=i,ans[i]=0,set<int>().swap(out[i]),set<int>().swap(in[i]);
		for(int i=1;i<=n;i++){
			int k=read();
			while(k--){
				int x=read();
				out[x].insert(i),in[i].insert(x);
			}
		}
		for(int i=1;i<=n;i++){
			if(in[i].size()==1)merge(i,*in[i].begin());
		}
		for(int i=1;i<=n;i++)ans[find(i)]++;
		printf("Case #%d: %d\n",Case,*max_element(ans+1,ans+n+1));
	}
}

2022“杭电杯”中国大学生算法设计超级联赛（1）

D. Ball

solution

题意：在 的网格上有 个给定的点，问有多少由三个点构成的集合，使得点与点两两之间的距离的中位数是质数，距离为曼哈顿距离。

做法：sb 分类讨论题。

考虑先曼哈顿转切比雪夫，然后枚举中位数的那两个点，发现剩余的就是二维数点，两个大正方形的和减去小正方形的两倍，好像很简单？

错误的！首先容易发现距离相同的点对会算两遍，三条边都相同的更是会算三遍，而且当减去小正方形两倍的时候，边界上的点就直接没有算进去了，怎么都不对。于是，我们先将减法部分改成减去完整的小正方形和小正方形的内部，即去掉边界。另一方面，距离相同的点对我们考虑容斥，对每个点直接暴力算出和它距离都为 的点个数，那么这些都会多算，于是减去点对个数，这样两边相同的就好了。但此时三边相同的是 ，这下好了。于是考虑枚举一组点对，然后看看第三个点有几个，这些都是可以预处理的，然后发现这样恰好每个三边相同的都算了三遍，所以独立计算这个，然后除以 即可。时间复杂度 ，我实现的比较难看，是