AtCoder Grand Contest 016

A - Shrinking

你可以进行一个串的变换，把一个长度为\(n\)的串\(S\)可以变成长度为\(n-1\)的串\(T\)，其中\(T_i\)要么是\(S_i\)要么是\(S_{i+1}\)。

现在问你最少进行多少次这个操作，能够使最终得到的\(T\)只由一个字符构成。

\(|S|\le 100\)

首先枚举最终字符是哪一个。那么首先在\(S\)末尾加上一个这个字符，那么这个最小步数等于对于所有位置而言，离它最近的枚举的字符到这个位置的距离。

那么直接模拟就行了，复杂度\(O(n\sum)\)。

#include
    
     #include
     
      #include
      
       using namespace std;char ch[111];int a[111],n,ans=2e9;int main(){    scanf("%s",ch+1);n=strlen(ch+1);    for(int i=1;i<=n;++i)a[i]=ch[i]-97;    for(int i=0;i<26;++i)    {        int mx=0,d=0;        for(int j=n;j;--j)            if(a[j]==i)d=0;            else mx=max(mx,++d);        ans=min(ans,mx);    }    printf("%d\n",ans);    return 0;}
      
     
    

B - Colorful Hats

有\(n\)个人，每个人有一顶帽子，现在每个人会告诉你除自己外的所有人的帽子一共有多少种颜色。

你要判断是否存在一个合并方案满足所有人的陈述。

\(n\le 10^5\)

首先不难发现最大值和最小值的差最大是\(1\)。那么我们可以得到最大值的颜色必定出现了多次，最小值的帽子必定只出现了一次。

那么直接大力讨论一下就好了。

#include
    
     #include
     
      #include
      
       using namespace std;inline int read(){    int x=0;bool t=false;char ch=getchar();    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();    if(ch=='-')t=true,ch=getchar();    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();    return t?-x:x;}int n,a[100100];void WA(){puts("No");exit(0);}int main(){    n=read();    for(int i=1;i<=n;++i)a[i]=read();    sort(&a[1],&a[n+1]);    if(abs(a[n]-a[1])>1){puts("No");return 0;}    if(a[n]==a[1])    {        if(a[n]==1||a[n]==n-1||2*a[n]<=n)puts("Yes");        else puts("No");        return 0;    }    int cnt=0;    for(int i=n;i;--i)if(a[i]==a[n])++cnt;    int v=a[n]-(n-cnt);    if(v>0&&2*v<=cnt&&a[1]==v+(n-cnt)-1)puts("Yes");    else puts("No");    return 0;}
      
     
    

C - +/- Rectangle

你需要构造一个\(H\times W\)的矩阵，每个值都是\([-10^9,10^9]\)之间，要求矩阵的所有元素和是正数，且每一个\(h\times w\)的子矩阵的和都是负数。

\(H,W,h,w\le 500\)

一个想法是首先把所有位置全部填满，然后把所有\(h\times w\) 的右下角给填上一个负数满足包含这个位置的子矩形都变成负数。那么就这样子构造一下然后\(check\)一下是否合法。

#include
    
     #include
     
      using namespace std;#define MAX 555inline int read(){    int x=0;bool t=false;char ch=getchar();    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();    if(ch=='-')t=true,ch=getchar();    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();    return t?-x:x;}int H,W,h,w;int a[MAX][MAX];long long sum=0;int main(){    H=read();W=read();h=read();w=read();    for(int i=1;i<=H;++i)        for(int j=1;j<=W;++j)            a[i][j]=1000;    for(int i=h;i<=H;i+=h)        for(int j=w;j<=W;j+=w)            a[i][j]=-h*w*1000+999;    for(int i=1;i<=H;++i)        for(int j=1;j<=W;++j)sum+=a[i][j];    if(sum<0)puts("No");    else    {        puts("Yes");        for(int i=1;i<=H;++i,puts(""))            for(int j=1;j<=W;++j)                printf("%d ",a[i][j]);    }    return 0;}
     
    

D - XOR Replace

给你一个数列\(a_i\)，每次你可以把\(a\) 中的一个数替换为\(a\)中所有数的异或和。

问能否把\(a\)变成给定的\(b\)。如果能，给出最小的步骤。

\(n\le 10^5,a_i\le 2^{30}\)

首先手玩一下，可以把这个步骤理解为：额外补充一个\(a_{n+1}\)位置，为前面所有数的异或和，每次操作等价于把\(i\in [1,n]\)的一个数和\(a_{n+1}\)进行交换。

那么这样子就可以很容易的把\(-1\)给判掉。

对于剩下的部分，考虑每一对一一对应的位置，如果\(a_i=b_i\)，那么显然不用管了。否则的话从\(a_i\)向\(b_i\)连一条边，那么这一条边至少要贡献一次操作。这样子会把若干个代表值域的点连起来。首先先考虑一下特殊点的情况，假如每个元素都只出现了一次，那么这样子就会形成一堆链，显然从链首到链尾一路走过去就行了，跨越链的时候需要额外进行一次交换操作，所以答案还需要加上联通块个数-1。显然对于权值多次出现的情况联通块的问题也是一样的。

所以答案就是边数加上联通块个数减一。

注意这样一个问题，因为最后一个元素，即初始的异或和我们没有连边出去，那么此时等于需要先进行一次交换到达某个联通块才能继续操作，所以如果有这样子的情况的话答案要额外加一。

#include
    
     #include
     
      #include
      
       #include
       
      
     
    

E - Poor Turkeys

有\(n\)只火鸡被摆成了一排。依次来了\(m\)个人。

每个人会进行如下操作：

如果火鸡\(x_i\)和火鸡\(y_i\)都还活着，那么就等概率的吃掉其中一只。

如果只剩下一只就吃掉那一只。

如果都死了就啥都不干。

问有多少对鸡\((i,j)\)满足\(m\)个人都操作完了之后，这两只鸡都还可能活着。

\(n\le 400,m\le 10^5\)

考虑一个枚举任意一对之后怎么计算，那么显然只要存在一个人要吃这两只鸡中的任何一只，那么就直接钦定吃掉另外一只，如果不行的话那么这一对肯定不合法。

但是这样子的复杂度是\(O(n^2m)\) 的。我们需要寻求更加优秀的方法。

一个不难想到的想法是对于每只鸡维护一个集合，表示如果这只鸡最后想要活下来，那么哪些鸡必须死。如果我们能够求出这个东西的话，我们只需要判断两个点的集合是否有交就行了。

考虑这个东西怎么求，如果我们按照顺序进行的话，因为我们只钦定了这一只鸡不被吃掉，所以与这只鸡无关的鸡我们都不知道会发生什么，那么对于两个集合判交的时候显然不具备有正确性。那么我们时间倒流，既然这只鸡必须存活，那么此时我们就可以知道在进行这次操作之前某只鸡是否必须存活，这样子我们就可以得到一个如果这只鸡最后或者，哪些鸡必须不能死。

接下来再口胡一下为什么如果两个集合有交就不合法。如果两只不同的鸡不想死，那么在这两者的集合中有一只相同的鸡不能死（注意一下这个所谓的死是指在某次操作以前不能死，也就是这只鸡为会了救某只特定的鸡而死，那么在救到这只特定的鸡之前这只鸡就不能死）。这里讨论一下，如果这只鸡在两个集合中救的是同一只鸡，那么递归处理。否则就的鸡是不同的，因为这只鸡只能死一次，所以它只能救下一只鸡，所以必定有一只鸡救不活，导致目标鸡也救不活。

#include
    
     #include
     
      using namespace std;#define MAX 100100inline int read(){    int x=0;bool t=false;char ch=getchar();    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();    if(ch=='-')t=true,ch=getchar();    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();    return t?-x:x;}int ans,n,m,a[MAX],b[MAX];bool alv[404][404],book[MAX];int main(){    n=read();m=read();    for(int i=1;i<=m;++i)a[i]=read(),b[i]=read();    for(int i=1;i<=n;++i)    {        alv[i][i]=true;        for(int j=m;j;--j)        {            int u=a[j],v=b[j];            if(alv[i][u]&&alv[i][v]){book[i]=true;break;}            if(alv[i][u]||alv[i][v])alv[i][u]=alv[i][v]=true;        }    }    for(int i=1;i<=n;++i)        for(int j=i+1;j<=n;++j)        {            if(book[i]||book[j])continue;            bool fl=false;            for(int k=1;k<=n;++k)if(alv[i][k]&&alv[j][k]){fl=true;break;}            if(!fl)++ans;        }    printf("%d\n",ans);    return 0;}
     
    

F - Games on DAG

给你一个\(n\)个点\(m\)条边的\(DAG\)，问你这个\(DAG\)的所有\(2^m\)个生成子图中，两个人在上面玩游戏，初始时在\(1,2\)两个点放上一个棋子，然后把一个棋子沿着一条边移动，不能操作者输。

问先手胜的子图个数。

\(n\le 15\)

显然要考虑的是\(SG\)值那套理论，先手必胜就是两个点\(SG\)值异或和不为\(0\)。这个东西显然不好算，那么就容斥一下，改成要算\(1,2\)两个点的异或和必须为\(0\)。

边数可以到\(O(n^2)\)级别，所以显然不能对于边进行状压。那么考虑对于点进行状压。

设\(f[S]\)表示考虑点集\(S\)之间的连边的时候\(SG(1)=SG(2)\)的方案数。

考虑怎么进行转移，那么我们显然是要考虑两个集合然后将他们合并。

假设两个集合分别是\(S,T\)。显然直接枚举两个集合我们是没法做的。

不妨令必败点集合为\(S\)，那么其补集\(T\)就是必胜点集合。

考虑\(S,T\)之内的连边情况，首先\(S\)内部不能有边(显然必败点之间不相邻)，然后必胜点必定存在一个后继是必败点，所以\(T\)中每个点至少有一条边连向\(S\)。而\(S\)向\(T\)连边是随意的。

接下来考虑\(T\)内部的连边方案数，虽然在枚举的时候我们钦定了\(T\)是必胜点集合，但是单独把\(T\)拿出来看\(T\)可能存在一些点\(SG\)值为\(0\)，于是我们新构一个虚拟点，让所有\(T\)中的点都连向这个虚拟点，这样子所有点的\(SG\)值都增加了\(1\)，也就全部变成了必胜点。而在前面的连边过程中，我们\(T\)中任意一个点都连向了一个\(SG\)值等于零的必败点集合\(S\)，而必败点的\(SG\)值恰好为\(0\)，因此\(T\)内部连边且满足\(SG(1)=SG(2)\)的方案数就是\(f[T]\)。

同时注意因为\(SG(1)=SG(2)\)，所以点集中必须\(1,2\)同时出现，否则就是一个不合法的状态。

#include
    
     #include
     
      using namespace std;#define MOD 1000000007inline int read(){    int x=0;bool t=false;char ch=getchar();    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();    if(ch=='-')t=true,ch=getchar();    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();    return t?-x:x;}int n,m,G[15],bul[1<<15],bin[25],f[1<<15];int main(){    n=read();m=read();    for(int i=1,u,v;i<=m;++i)u=read()-1,v=read()-1,G[u]|=1<
      
       >1]+(i&1);    bin[0]=1;for(int i=1;i<=n;++i)bin[i]=(bin[i-1]<<1)%MOD;    for(int i=2;i<=N;++i)        if((i&1)==((i>>1)&1))            for(int U=i;U;U=(U-1)&i)                if((U&1)==((U>>1)&1))                {                    int T=i^U,w=1;                    for(int j=0;j