Codeforces Round #663 (Div. 2)

太水了

打表发现答案是n!-2^n-1，但是不能就这样草草了事，理性分析：考虑不成环的方案（因为看起来远少于成环的），加入一个新元素的时候，如果原图成环，则怎么放都成环，如果不成环，放在开头和结尾则不成环，故方案数每次*2

当n>=4时不符合条件输出-1，对于每个2*2的矩阵都满足条件，则拼在一起的4*4的矩阵势必不满足条件，因为四个奇数的和必为偶数

当n=1时，答案为0

当n=2/3时，直接状压DP即可，复杂度O(4^n*m)

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+7;
int n,m,ans,f[N][8],c[8][8];
char a[3][N];
int main()
{
    scanf("%d%d",&n,&m);
    if(n==1||m==1){puts("0");return 0;}
    if(n>=4){puts("-1");return 0;}
    for(int i=0;i<n;i++)scanf("%s",a[i]+1);
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<(1<<n);j++)
        {
            int a1=(i&1),a2=(bool)(i&2),a3=(bool)(i&4),b1=(j&1),b2=(bool)(j&2),b3=(bool)(j&4);
            if((a1+a2+b1+b2)%2&&(n==2||(a2+a3+b2+b3)%2))c[i][j]=1;
        }
        for(int j=0;j<n;j++)if(a[j][1]!='0'+((i>>j)&1))f[1][i]++;
    }
    for(int i=2;i<=m;i++)
    for(int j=0;j<(1<<n);j++)
    {
        f[i][j]=n*m+1;
        for(int k=0;k<(1<<n);k++)if(c[k][j])f[i][j]=min(f[i][j],f[i-1][k]);
        for(int k=0;k<n;k++)if(a[k][i]!='0'+((j>>k)&1))f[i][j]++;
    }
    ans=n*m+1;
    for(int i=0;i<(1<<n);i++)ans=min(ans,f[m][i]);
    if(ans==n*m+1)puts("-1");else printf("%d",ans);
}

View Code

题都看不懂还写啥

真实手速场，因为D数组开小RE了一发，只有rk66，新号rating+=199，卡线上橙了！