PKUCPC2022题解

xiaolilsq / 2023-05-16 / 原文

PKUCPC2022题解

马上要打 PKUCPC2023 了，来刷一下 PKUCPC2022 的题目练练手。

A Random Sequence

题意

Alice 和 Bob 生成了两个长度为 \(n=10^5\) 的仅由 \(1\sim 6\) 构成的序列，生成方式如下：

Alice 从 \(1\sim 6\) 随机选择一个作为第一个数，然后如果当前数字为 \(t\)，生成的下一个数字有 \(1/2\) 概率为 \(t\)，有 \(1/2\) 概率等概率随机从其它 \(5\) 个中选一个。

Bob 每个数都是等概率随机从 \(1\sim 6\) 中选取的。

现在给定他们两个生成的序列，问哪个是 Alice 哪个是 Bob 生成的。

题解

显然 Alice 生成的序列相邻相同数概率为 \(1/2\) 而 Bob 为 \(1/6\)，所以直接看哪个相邻相同数字多就行了。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
int main(){
    int n,p,q,c0=0,c1=0;scanf("%d",&n);
    scanf("%d",&p);
    for(int i=2;i<=n;++i,p=q)
        scanf("%d",&q),c0+=p==q;
    scanf("%d",&p);
    for(int i=2;i<=n;++i,p=q)
        scanf("%d",&q),c1+=p==q;
    puts(c0>c1?"Alice Bob":"Bob Alice");
    return 0;
}

B Oshin Impact

题意

构造一个网络流图，从一个源点连到 \(n+1\) 个汇点，其中源点流出的流量为 \(515n\)，第 \(i(1\le i\le n)\) 个汇点流入的流量为 \(a_i\)，第 \(n+1\) 个汇点流入的流量任意（你可以认为这个汇点是垃圾桶）。你可以增加不超过 \(5n\) 个（包含源点）节点，中间节点要么出度小于 \(2\)，要么所有出边的流量相等，并且这些出边连向不同的点。另外你还需要保证 \(\forall 1\le i\le n\)，有源点到第 \(i\) 个汇点的最长链长度恰好为 \(5\)。给出任意一种构造方案。

\(1\le n\le 2022,\sum_{i=1}^na_i\le 515n,1\le a_i\le 2\times 10^5\)。

题解

被阴间构造题踩爆了，本来想复杂了想了好久，后来发现构造真的巨简单。

既然本来是 \(515n\)，那么自然而然地分成 \(n\) 份，每份 \(515\)，然后看这些 \(515\) 要是需要构造出来的流量都是大于等于 \(515\) 那么很好做，就是按照任意顺序填充，依次看每个 \(515\) 是拆成两份还是一份。考虑如果小于 \(515\) 怎么办，那就直接用一个 \(515\) 拆开就行了，剩下的部分再一起考虑填充就行。

整个图点数形如 \(1\to 1\to 1\to n\to [n,2n]\to n\)，最多使用点数 \(3n+3\)，可以通过，然后 \(n=1\) 要特判。

代码

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=2025,maxm=maxn*5;
int n,a[maxn],sum[maxn],val[maxn*2];
struct Node{
    int id,type;
    int ot1,ot2;
    int v1,v2;
    Node(int id=0,int type=0,int ot1=0,int ot2=0,int v1=0,int v2=0):
        id(id),type(type),ot1(ot1),ot2(ot2),v1(v1),v2(v2){}
    void output(void){
        if(type==1){
            printf("%d %d %d %d\n",id,type,ot1,v1);
        }
        else if(type==2){
            printf("%d %d %d ",id,type,n);
            for(int i=1;i<=n;++i)
                printf("%d ",id+i);
            printf("%d\n",v1);
        }
        else if(type==3){
            printf("%d %d %d %d %d %d\n",id,type,ot1,ot2,v1,v2);
        }
    }
}nd[maxm+maxn];
int num;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    num=n;
    nd[++num]=Node(n+1,1,n+2,0,n*515,0);
    nd[++num]=Node(n+2,1,n+3,0,n*515,0);
    if(n==1){
        nd[++num]=Node(n+3,1,n+4,0,n*515,0);
        nd[++num]=Node(n+4,1,n+5,0,n*515,0);
        if(a[1]<n*515)
            nd[++num]=Node(n+5,3,1,-1,a[1],n*515-a[1]);
        else
            nd[++num]=Node(n+5,1,1,0,n*515,0);
    }
    else{
        nd[++num]=Node(n+3,2,0,0,515,0);
        int sp=0;
        for(int i=1;i<=n;++i){
            if(a[i]<515){
                ++sp;++num;
                nd[num]=Node(num,3,n*2+3+i,n*3+3+sp,a[i],515-a[i]);
                val[n+sp]=515-a[i];val[i]=0;
            }
            else{
                ++num;
                nd[num]=Node(num,1,n*2+3+i,0,515,0);
                val[i]=515;
            }
        }
        int p=1;
        a[n+1]=515*(n+1);
        for(int i=1;i<=n+sp;++i){
            ++num;
            if(val[i]){
                while(a[p]<515)++p;
                if(val[i]+sum[p]>a[p]){
                    int pp=p;++p;while(a[p]<515)++p;
                    nd[num]=Node(num,3,pp,(p>n?-1:p),a[pp]-sum[pp],val[i]-a[pp]+sum[pp]);
                    sum[p]+=val[i]-a[pp]+sum[pp];
                }
                else{
                    nd[num]=Node(num,1,(p>n?-1:p),0,val[i],0);
                    sum[p]+=val[i];if(sum[p]==a[p])++p;
                }
            }
            else{
                nd[num]=Node(num,1,i,0,a[i],0);
            }
        }
    }
    printf("%d\n",num-n);
    for(int i=n+1;i<=num;++i)
        nd[i].output();
    return 0;
}

C Phone and Cup

题意

给定两条边平行于坐标轴的长方形和一个圆，问圆是否被长方形完全包含。

\(t\) 组数据，保证坐标 \([0,100]\) 半径 \([1,100]\) 且均为整数。

题解

平行于坐标轴，所以直接判最左边最右边最上面最下面有没有超过就行了。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
int main(){
    int t;scanf("%d",&t);
    while(t--){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        int e,f,g;
        scanf("%d%d%d",&e,&f,&g);
        puts(e-g>=a&&e+g<=c&&f-g>=b&&f+g<=d?"Y":"N");
    }
    return 0;
}

D Network Transmission

题意

\(n\) 个点 \(m\) 条无向边的图，点有点权 \(t_i\) 边 \((u_i,v_i)\) 有边权 \(w_i\)，询问将一个点点权置为 \(0\) 后 \(1\) 到 \(n\) 的最短路最短是多少。（路径长度定义为点权和加上边权和）

\(3\le n\le 2\times 10^5,1\le m\le 2\times 10^5,1\le t_i,w_i\le 10^9\)。

题解

最短路，求出 \(1\) 到每个点最短路和 \(n\) 到每个点最短路，然后枚举选择哪个点置零。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=200005,maxm=200005;
struct Edge{
    int v,w,nt;
    Edge(int v=0,int w=0,int nt=0):
        v(v),w(w),nt(nt){}
}e[maxm*2];
int hd[maxn],num;
void qwq(int u,int v,int w){
    e[++num]=Edge(v,w,hd[u]),hd[u]=num;
}
struct Val{
    int id;long long val;
    Val(int id=0,long long val=0):
        id(id),val(val){}
    bool operator < (const Val o)const{
        return val>o.val;
    }
};
std::priority_queue<Val>q;
int t[maxn];
void dijkstra(int s,long long *dis){
    q.push(Val(s,dis[s]=0));
    while(!q.empty()){
        Val tmp=q.top();q.pop();
        int u=tmp.id;if(tmp.val!=dis[u])continue;
        for(int i=hd[u];i;i=e[i].nt){
            int v=e[i].v,w=e[i].w;
            if(dis[v]>dis[u]+t[u]+w)
                q.push(Val(v,dis[v]=dis[u]+t[u]+w));
        }
    }
}
long long dis0[maxn],dis1[maxn];
int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=2;i<=n-1;++i)scanf("%d",&t[i]);
    for(int i=1;i<=m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        qwq(u,v,w);qwq(v,u,w);
    }
    memset(dis0,0x3f,sizeof dis0);
    memset(dis1,0x3f,sizeof dis1);
    dijkstra(1,dis0);dijkstra(n,dis1);
    long long ans=0x3f3f3f3f3f3f3f3fll;
    for(int i=1;i<=n;++i)
        ans=std::min(ans,dis0[i]+dis1[i]);
    printf("%lld\n",ans);
    return 0;
}

E Form a Honor of Kings Team

题意

要用 \(M\) 块钱组建一直五人队伍，市场上有 \(N\) 个队伍可以购买，每个人有单独的价钱和能力，也有整队的价钱，可以整队购买或者单人购买，整队购买了队伍中任意一个人都可以用，询问组建得到的五人队伍所有人能力值之和最大为多少。

\(1\le N,M\le 100,0\le Ability,value,Price\le 10^6\)。

题解

背包，直接状压考虑玩前若干个队伍其中哪些位置已经被钦定了已经用了多少钱。唯一比较麻烦就是整队购买，不过可以用前缀最大值的方法得到整队购买时最大可能的贡献。设队伍人数为 \(K\)，时间复杂度就是 \(O(NM2^KK)\)。此题 \(K=5\) 可以通过。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxm=105,K=5;
int dp[maxm][1<<K],f[maxm][1<<K];
int v[K],p[K];
int main(){
    int U=(1<<K)-1;
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=0;j<K;++j)
            scanf("%d%d",&v[j],&p[j]);
        int sp=0;scanf("%d",&sp);
        for(int j=0;j<=m;++j){
            for(int s=1;s<=U;++s){
                f[j][s]=dp[j][s];
                for(int k=0;k<K;++k){
                    if((s>>k)&1)
                        f[j][s]=std::max(f[j][s],f[j][s^(1<<k)]+v[k]);
                }
            }
        }
        for(int j=sp;j<=m;++j)
            for(int s=1;s<=U;++s)
                dp[j][s]=std::max(dp[j][s],f[j-sp][s]);
        for(int j=0;j<=m;++j){
            for(int s=1;s<=U;++s){
                for(int k=0;k<K;++k){
                    if(j<p[k])continue;
                    if((s>>k)&1){
                        dp[j][s]=std::max(dp[j][s],dp[j-p[k]][s^(1<<k)]+v[k]);
                    }
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=m;++i)
        for(int j=0;j<=U;++j)
            ans=std::max(ans,dp[i][j]);
    printf("%d\n",ans);
    return 0;
}

F A problem about deques

你先别急，让我先急。

G A Game of Jumping

你先别急，让我先急。

H Shuffles on the Tree

题意

给定一棵 \(n\) 个点的有根树，每个点有权值 \(a_i\)。对于每个 \(1\le i\le n\)，问将以 \(i\) 为根的子树中的点权值 shuffle 后得到 \(b_i\)，满足 \(b_i>a_i\) 的点数最多有多少。

\(1\le n\le 1.5\times 10^5,1\le a_i\le n\)。

题解

考虑长度为 \(n\) 的序列 \(a_i\) shuffle 后得到 \(b_i\) 满足 \(b_i>a_i\) 的最多的有多少，答案是 \(n-\max_{t}(\sum_{i=1}^n[a_i=t])\)，或者说答案是 \(n\) 减去出现次数最多的数的出现次数。证明也很简单，考虑答案能否大于等于 \(k\)，我们当然是希望尽可能大的匹配到尽可能小的，也就是我们用前 \(k\) 个和后 \(k\) 个对应匹配一下，或者说 \(a_i\) 排序后要求 \(\forall 1\le i\le k\) 有 \(a_i< a_{n-k+i}\)，由此容易得证。

然后问题转化成了对于每个子树求出现次数最多的权值的出现次数，感觉也许可以线性？不过我只会一个 \(\log\)。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1500005;
int a[maxn];
struct Edge{
    int v,nt;
    Edge(int v=0,int nt=0):
        v(v),nt(nt){}
}e[maxn*2];
int hd[maxn],num;
void qwq(int u,int v){
    e[++num]=Edge(v,hd[u]),hd[u]=num;
}
int sz[maxn],mxp[maxn];
void dfs1(int u,int p){
    sz[u]=1;mxp[u]=0;
    for(int i=hd[u];i;i=e[i].nt){
        int v=e[i].v;
        if(v==p)continue;
        dfs1(v,u);sz[u]+=sz[v];
        if(sz[v]>sz[mxp[u]])mxp[u]=v;
    }
}
int mx[maxn],cnt[maxn];
void dfs3(int u,int p,int rt){
    mx[rt]=max(mx[rt],++cnt[a[u]]);
    for(int i=hd[u];i;i=e[i].nt){
        int v=e[i].v;
        if(v==p)continue;
        dfs3(v,u,rt);
    }
}
void dfs4(int u,int p){
    --cnt[a[u]];
    for(int i=hd[u];i;i=e[i].nt){
        int v=e[i].v;
        if(v==p)continue;
        dfs4(v,u);
    }
}
void dfs2(int u,int p,int er){
    for(int i=hd[u];i;i=e[i].nt){
        int v=e[i].v;
        if(v==p||v==mxp[u])continue;
        dfs2(v,u,true);
    }
    if(mxp[u])
        dfs2(mxp[u],u,false);
    mx[u]=mx[mxp[u]];
    mx[u]=max(mx[u],++cnt[a[u]]);
    for(int i=hd[u];i;i=e[i].nt){
        int v=e[i].v;
        if(v==p||v==mxp[u])continue;
        dfs3(v,u,u);
    }
    if(er)dfs4(u,p);
}
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        qwq(u,v);qwq(v,u);
    }
    dfs1(1,0);
    dfs2(1,0,true);
    for(int i=1;i<=n;++i)
        printf("%d%c",sz[i]-mx[i]," \n"[i==n]);
    return 0;
}

I Anipop

题意

有一个两行 \(n\) 列的 01 矩阵 \(s_{i,j}\)，每次你可以选择以下两种操作之一进行：

改变。选择 \(1,2,\dots,n\) 的一个子序列 \(i_1,i_2,\dots,i_m\)，然后令第一行 \(s_{1,i_2}\gets s_{1,i_1},s_{1,i_3}\gets s_{1,i_2},\dots,s_{1,i_m}\gets s_{1,i_{m-1}},s_{1,i_1}\gets s_{1,i_m}\)，该赋值操作为同时进行；
消去。选择 \(1,2,\dots,n\) 的一个子序列 \(i_1,i_2,\dots,i_m\)，满足 \(\forall 1\le j\le m,s_{1,i_j}=s_{2,i_j}\)，然后消去这些列。

问最少次数操作使得矩阵消除为空，或者判断无解。

\(1\le n\le 10^5\)。

题解

无解判 \(01\) 数量是否相同即可。

肯定是最后进行一次消去操作。相同的列可以不用考虑，所以我们只考虑不同的列，形如：

110100010
001011101

注意一次改变操作改变的成功归位的列形如：

10101010
01010101

或者：

01010101
10101010

这样贪心地从前往后匹配就行了，具体而言记录两个数字 \(c_0,c_1\) 分别表示第一列结尾为 \(0\) 或者 \(1\) 的匹配数量，每次第一列遇到 \(1\) 就 \(c_0\gets \max(0,c_0-1),c_1\gets c_1+1\)，遇到 \(0\) 就 \(c_1\gets\max(0,c_1-1),c_0\gets c_0+1\)。最后 \(c_0+c_1\) 就是消去次数，加上 \(1\) 就是答案。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=100005;
char S0[maxn],S1[maxn];
int main(){
    int n;scanf("%d",&n);
    scanf("%s",S0+1);int s0=0,c0=0;
    scanf("%s",S1+1);int s1=0,c1=0;
    for(int i=1;i<=n;++i){
        s0+=(S0[i]=='b');
        s1+=(S1[i]=='b');
        if(S0[i]!=S1[i]){
            if(S0[i]=='b'){
                if(c1)--c1;
                ++c0;
            }
            else{
                if(c0)--c0;
                ++c1;
            }
        }
    }
    if(s0!=s1)puts("Impossible");
    else printf("%d\n",c0+c1+1);
    return 0;
}

J Gene recombination

题意

一个生物有 \(n\) 对染色体，第 \(i\) 对染色体上面有 \(k_i\) 对等位基因，考虑这个生物的减数分裂过程，仅考虑交叉互换，其中第 \(i\) 对染色体上的第 \(j\) 对等位基因发生交叉互换导致这两个基因互换位置的概率为 \(p_{i,j}\)。现在任意取该生物的 \(m\) 个配子，问这些配子期望有多少种不同种类。

Subtask1: \(n\le 10,d=\sum_{i=1}^nk_i\le 20,m\le 10^5\)。

Subtask2: \(n\le 10^3,d=\sum_{i=1}^nk_i\le 2\times 10^3,m\le 100\)。

题解

题意挺阴间的。。。要是没学过生物就不能做了是吧。

考虑枚举可能的基因序列，如果我们知道了配子为某个基因序列 \(T\) 的概率为 \(q_T\)，那么依次考虑 \(m\) 个配子中某种基因序列出现的概率，可以得到答案为：

\[\sum_{T}(1-(1-q_T)^m) \]

然后求 \(q_T\)，考虑记 \(T_{i,j}\) 表示第 \(i\) 对染色体上的第 \(j\) 对基因该配子选择的是基因序列 \(T\) 对应位置的基因的概率，也就是说 \(T_{i,j}=p_{i,j}\) 或者 \(T_{i,j}=1-p_{i,j}\)，然后考虑每对染色体选择的是哪一条，可以得到：

\[q_T=\prod_{i=1}^n(\frac{1}{2}\prod_{j=1}^{k_i}T_{i,j}+\frac{1}{2}\prod_{j=1}^{k_i}(1-T_{i,j})) \]

由此 Subtask1 枚举 \(T\) 即可做，复杂度 \(O(2^d(d+\log m))\)。

然后 Subtask2 的 \(m\) 特别小，考虑直接拆开要算的东西，那么也就相当于我们对于任意 \(1\le t\le m\)，要求 \(\sum_{T}q_T^t\)，然后继续拆：

\[\sum_{T}q_T^t =\sum_{T}(\prod_{i=1}^n(\frac{1}{2}\prod_{j=1}^{k_i}T_{i,j}+\frac{1}{2}\prod_{j=1}^{k_i}(1-T_{i,j})))^t\\ =\sum_{T}\prod_{i=1}^n(\frac{1}{2}\prod_{j=1}^{k_i}T_{i,j}+\frac{1}{2}\prod_{j=1}^{k_i}(1-T_{i,j}))^t\\ =\prod_{i=1}^n(\sum_{T_i}(\frac{1}{2}\prod_{j=1}^{k_i}T_{i,j}+\frac{1}{2}\prod_{j=1}^{k_i}(1-T_{i,j}))^t)\\ \]

然后里面的括号继续二项式拆开，也就是要对于任意的 \(0\le a,b\le m\)，要求：

\[\sum_{T_i}(\frac{1}{2}\prod_{j=1}^{k_i}T_{i,j})^a(\frac{1}{2}\prod_{j=1}^{k_i}(1-T_{i,j}))^b = (\frac{1}{2})^{a+b}\prod_{j=1}^{k_i}(\sum_{T_{i,j}}T_{i,j}^a(1-T_{i,j})^b) \\ = (\frac{1}{2})^{a+b}\prod_{j=1}^{k_i}(p_{i,j}^a(1-p_{i,j})^b+p_{i,j}^b(1-p_{i,j})^a) \]

然后就可以做了，复杂度 \(O(dm^2)\)。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int mod=998244353,inv2=(mod+1)/2;
void UP(int&x,int y){x+=y;x-=x>=mod?mod:0;}
void DN(int&x,int y){x+=mod-y;x-=x>=mod?mod:0;}
int power(int a,int x){
    int re=1;
    while(x){
        if(x&1)re=1ll*re*a%mod;
        a=1ll*a*a%mod,x>>=1;
    }
    return re;
}
void inP(int&x){
    const int INV=power(100000,mod-2);
    int a,b;scanf("%d.%05d",&a,&b);
    x=1ll*INV*(a*100000+b)%mod;
}
namespace solve1{
    const int maxn=1005,maxd=2005,maxm=105;
    int C[maxm][maxm],S[maxm][maxm];
    int prod[maxm],k[maxn];
    int p[maxd][maxm],rp[maxd][maxm];
    void solve(int n,int m){
        for(int i=0;i<=m;++i){
            C[i][0]=prod[i]=1;
            for(int j=1;j<=i;++j){
                C[i][j]=C[i-1][j];UP(C[i][j],C[i-1][j-1]);
            }
        }
        for(int i=1;i<=n;++i){
            scanf("%d",&k[i]);
        }
        for(int i=1;i<=n;++i){
            int K=k[i];
            for(int j=1;j<=K;++j){
                inP(p[j][1]);p[j][0]=1;
                rp[j][0]=1;rp[j][1]=1;
                DN(rp[j][1],p[j][1]);
                int pro=p[j][1],rpro=rp[j][1];
                for(int l=2;l<=m;++l)
                    p[j][l]=1ll*p[j][l-1]*pro%mod,
                    rp[j][l]=1ll*rp[j][l-1]*rpro%mod;
            }
            for(int a=0,i1s=1;a<=m;++a,i1s=1ll*i1s*inv2%mod){
                for(int b=0,i2s=i1s;b<=m;++b,i2s=1ll*i2s*inv2%mod){
                    int s=i2s;
                    for(int j=1;j<=K;++j){
                        int tmp=1ll*p[j][a]*rp[j][b]%mod;
                        UP(tmp,1ll*p[j][b]*rp[j][a]%mod);
                        s=1ll*s*tmp%mod;
                    }
                    S[a][b]=s;
                }
            }
            for(int i=0;i<=m;++i){
                int sm=0;
                for(int a=0,b=i;a<=i;++a,--b){
                    UP(sm,1ll*C[i][a]*S[a][b]%mod);
                }
                prod[i]=1ll*prod[i]*sm%mod;
            }
        }
        int ans=0;
        for(int i=1;i<=m;++i){
            int tmp=1ll*C[m][i]*prod[i]%mod;
            if(i&1)UP(ans,tmp);else DN(ans,tmp);
        }
        printf("%d\n",ans);
    }
}
namespace solve2{
    const int maxn=15,maxd=21,maxm=100005;
    int k[maxn];
    int p[maxn][maxd];
    void solve(int n,int m){
        int sk=0;
        for(int i=1;i<=n;++i)
            scanf("%d",&k[i]);
        for(int i=1;i<=n;++i){
            sk+=k[i];
            for(int j=1;j<=k[i];++j)inP(p[i][j]);
        }
        int U=(1<<sk),ans=0;
        for(int S=0;S<U;++S){
            int cS=S,pds=1;
            for(int i=1;i<=n;++i){
                int s1=inv2,s2=inv2;
                for(int j=1;j<=k[i];++j){
                    if(cS&1){
                        s1=1ll*s1*p[i][j]%mod;
                        s2=1ll*s2*(mod+1-p[i][j])%mod;
                    }
                    else{
                        s2=1ll*s2*p[i][j]%mod;
                        s1=1ll*s1*(mod+1-p[i][j])%mod;
                    }
                    cS>>=1;
                }
                UP(s1,s2);pds=1ll*pds*s1%mod;
            }
            UP(ans,1);
            DN(ans,power((mod+1-pds)%mod,m));
        }
        printf("%d\n",ans);
    }
}
int main(){
    int n,m;scanf("%d%d",&n,&m);
    if(m<=100)solve1::solve(n,m);
    else solve2::solve(n,m);
    return 0;
}

K Peaceful Gomoku

题意

\(H\times W\) 的网格上，每个格子要么为空要么放着黑色方块，设黑色方块总数量为 \(n\)，将不超过 \(\lfloor\frac{n}{5}\rfloor\) 个黑色方块改成白色方块使得每行每列不存在相邻连续的 \(5\) 个格子都是同样颜色的方块。

\(1\le H,W\le 500\)。

题解

太典了。考虑每行或者每列某个连续的 \(5\) 个格子他们的行列编号之和模 \(5\) 恰好占据 \(0,1,2,3,4\) 五种余数各一次，所以只要把某种余数全部改掉就行，而鸽巢原理可以知道这 \(5\) 个中至少有一个出现次数小于等于 \(\lfloor\frac{n}{5}\rfloor\)。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=505;
char s[maxn][maxn];
int c[5];
int main(){
    int H,W;scanf("%d%d",&H,&W);
    for(int i=1;i<=H;++i){
        scanf("%s",s[i]+1);
        for(int j=1;j<=W;++j){
            if(s[i][j]=='B'){
                ++c[(i+j)%5];
            }
        }
    }
    int t=0;
    for(int i=0;i<4;++i)
        if(c[i]<c[t])t=i;
    for(int i=1;i<=H;++i)
        for(int j=1;j<=W;++j)
            if((i+j)%5==t&&s[i][j]=='B')
                s[i][j]='W';
    for(int i=1;i<=H;++i)
        printf("%s\n",s[i]+1);
    return 0;
}