P16166 [ICPC 2015 NAIPC] Magic Checkerboard · ooliver

P16166 [ICPC 2015 NAIPC] Magic Checkerboard 特殊情况：n=1 或 m=1 这个很好想，应为在这种情况下不存在两个格子只有一个公共角，所以只需要贪心地满足横向或者纵向是递增的就可以了，期间加上对已经放了数的格子的判断。一般情况：n\neq1 且 m\neq1 我们可以把表格按对角线染成黑白两种颜色，如下图：黑白格子里只要知道其中一个格子的奇偶，就能推出其他同颜色的格子的奇偶。并且在图中，格子内圆圈颜色相同的一定同奇偶。注意这是建立在表格是二维的情况下的推论，所以我们需要特判一维的情况。知道这点就很好写了，我们用两个布尔类型的变量存储 (1,1) 与 (1,2) 两个格子的奇偶性，就可以推出整个表格的奇偶性，最后贪心填数即可。代码： C++ #include using namespace std; #define int long long const int N=2e3+5; int n,m; int a[N][N],b[N][N]; int solve(int tag1,int tag2){ int ans=0; for(int i=1;i>n>>m; if(n==1||m==1){//特判一维的情况 ans=0; for(int i=1;i>a[i][j]; if(!a[i][j]) a[i][j]=max(a[i-1][j],a[i][j-1])+1; else if(a[i][j]>a[i][j]; if(!a[i][j]) continue; if(i%2==1&&j%2==1){ if(tag1==-1) tag1=a[i][j]%2; else if(tag1!=a[i][j]%2){cout `#include using namespace std; #define int long long const int N=2e3+5; int n,m; int a[N][N],b[N][N]; int solve(int tag1,int tag2){ int ans=0; for(int i=1;in;i++) for(int j=1;jm;j++){ b[i][j]=a[i][j]; int x=max(b[i-1][j],b[i][j-1])+1,y; if(i%2==1&&j%2==1) y=tag1; if(i%2==0&&j%2==0) y=!tag1; if(i%2==1&&j%2==0) y=tag2; if(i%2==0&&j%2==1) y=!tag2; if(x%2!=y) x++; if(b[i][j]){ if(xb[i][j]) ans+=b[i][j]; else return 1e18; } else ans+=(b[i][j]=x); } return ans; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int ans=1e18,tag1=-1,tag2=-1; cin>>n>>m; if(n==1||m==1){//特判一维的情况 ans=0; for(int i=1;in;i++) for(int j=1;jm;j++){ cin>>a[i][j]; if(!a[i][j]) a[i][j]=max(a[i-1][j],a[i][j-1])+1; else if(a[i][j]max(a[i-1][j],a[i][j-1])+1){cout-1;return 0;} ans+=a[i][j]; } coutans; return 0; } for(int i=1;in;i++) for(int j=1;jm;j++){ cin>>a[i][j]; if(!a[i][j]) continue; if(i%2==1&&j%2==1){ if(tag1==-1) tag1=a[i][j]%2; else if(tag1!=a[i][j]%2){cout-1;return 0;} } if(i%2==0&&j%2==0){ if(tag1==-1) tag1=(a[i][j]+1)%2; else if(tag1!=(a[i][j]+1)%2){cout-1;return 0;} } if(i%2==1&&j%2==0){ if(tag2==-1) tag2=a[i][j]%2; else if(tag2!=a[i][j]%2){cout-1;return 0;} } if(i%2==0&&j%2==1){ if(tag2==-1) tag2=(a[i][j]+1)%2; else if(tag2!=(a[i][j]+1)%2){cout-1;return 0;} } } //如果所有黑格子或所有白格子都不确定，那就枚举 if(tag1==-1&&tag2==-1){ ans=min(ans,solve(1,1)); ans=min(ans,solve(1,0)); ans=min(ans,solve(0,1)); ans=min(ans,solve(0,0)); } else if(tag1!=-1&&tag2==-1){ ans=min(ans,solve(tag1,1)); ans=min(ans,solve(tag1,0)); } else if(tag1==-1&&tag2!=-1){ ans=min(ans,solve(1,tag2)); ans=min(ans,solve(0,tag2)); } else ans=min(ans,solve(tag1,tag2)); cout(ans==1e18?-1:ans); return 0; } `