codeforces-#663-D

codeforces-#663-D

八月 11, 2020

D. 505

题意

给出一个n*m的01矩阵 其中(n<=m<1e6)

要求0/1置换其中的某些位置使得这个01矩阵中

任意偶数边长的正方形区域内都有奇数个1

问最小操作次数若不行则输出-1

题解

在分析如何计算最小操作次数前要发现

若 min(n,m)>3 无论如何都无法构造出符合题意的01矩阵

假设n=m=4 对于最小的偶数边长为2的矩阵 它们要满足其区域内只有奇数个1

如上图红框区域内都有奇数个1,但对于橙框区域即整个4×4的区域 4个奇数相加无论如何都为偶数

所以min(n,m)>3误解，另外当min(n,m)==1时不存在偶数边的正方形区域所以输出0

解决了这些问题之后 在考虑如何统计最小次数

构造dp(i,num)表示从左到右第i列01串组成的十进制数为num时转变为合法构造所需要的最小次数

于是dp的状态转移公式为

dp(i,cnum)=min(dp(i,cnum),dp(i-1,pnum)+bitcnt(a[i]^pnum) )

其中bitcount(a[i]^pnum)意思是若构造该列为pnum那与原本该列的01串 ai有多少位不同需要0/1置换操作

判断能否转移的前提是前一列的01串构造为cnum当前列01串构造为pnum是否合法

即是否会出现2×2的矩阵中有偶数个1 这里用到位运算

要求最小值则初始化dp项为无穷大

答案为 ans=min(ans,dp(m-1,i) ) i∈[0,1<<n) (从0开始所以第m-1列为最后一列)

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e6+5;
const double Pi=acos(-1);

/*
*/
string s[Max];
int bits[Max],dp[Max][10];
int n,m;
bool check(int cnum,int pnum){
    int maxn=(1<<n)-1,cnt=0,ti=0;
    bool flag=0;int carry[2];
    carry[0]=carry[1]=0;
    while(maxn){
        if((cnum&1)^(pnum&1))cnt++;
        //cout<<cnt<<" "<<carry[ti%2]<<endl;
        if(ti){
            cnt-=carry[ti%2];
            if(!(cnt&1))flag=1;
            if(flag)break;
        }
        carry[ti%2]=(cnum&1)^(pnum&1);
        ti++;
        cnum>>=1;pnum>>=1;
        maxn>>=1;
    }
    return flag;
}

int main(){
    Turnoff;
    /*
    int a,b;
    cin>>a>>b;
    cout<<check(a,b)<<endl;
    */

    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>s[i];
    if(n>3){
        cout<<-1<<endl;
        return 0;
    }
    else if(n==1){
        cout<<0<<endl;
        return 0;
    }
    for(int i=0;i<m;i++)for(int j=0;j<10;j++)dp[i][j]=1e9;
    for(int c=0;c<m;c++){
        int temp=0,ti=1;
        for(int r=0;r<n;r++){
            temp+=(s[r][c]=='1')*ti;
            ti*=2;
        }
        bits[c]=temp;
        //cout<<bits[c]<<endl;
    }
    int up=1<<n;
    //cout<<up<<endl;
    for(int cnum=0;cnum<up;cnum++){
        int cnt=0,temp=cnum^bits[0];
        while(temp){
            if(temp&1)cnt++;
            temp>>=1;
        }
        dp[0][cnum]=cnt;
    }
    for(int i=1;i<m;i++){
        for(int cnum=0;cnum<up;cnum++){
            for(int pnum=0;pnum<up;pnum++){
                //cout<<cnum<<" "<<pnum<<" "<<check(cnum,pnum)<<endl;
                    if(check(cnum,pnum))continue;
                int cnt=0,temp=(pnum^bits[i]);
                while(temp){
                if(temp&1)cnt++;
                    temp>>=1;
                }
                dp[i][pnum]=min(dp[i-1][cnum]+cnt,dp[i][pnum]);
            }
        }
    }
    int ans=1e9;
    for(int i=0;i<10;i++)ans=min(ans,dp[m-1][i]);
    cout<<ans<<endl;
    return 0;
}