CodeForces - 426D Sereja and Table
题目链接
https://codeforces.com/problemset/problem/426/D
解题思路
首先应当得出点结论:
- 数据规模小。
- 如果01矩阵中所有0的连通块以及1的连通块都是矩阵的话,那么其实可以确定01矩阵的每一行与下一行的关系,要么这两行的元素全部相等,要么就全部相反。
- ** 当 n<=k 时,可以枚举第一列的01状态,其他各行都根据第一列**的状态进行变换操作以保证所有01连通块都为矩阵。
同时注意,枚举的是第一列的状态,因为是行数小于等于k,k又小于等于10,2^10是可行的,但是列数最多为100,2^100是不可行的。当然,这只是其中一个很片面的原因,望自行理解。 - 当 n>k 时,意味着最多进行k次变换,最多将这k次变换分别施加到不同行,即最多施加到k行,由于n>k,所以至少有一行是没有进行过变换的。枚举没进行过变换的行,其他各行以此行为标准进行变换操作以保证所有01连通块都为矩阵。
同时注意,只需要枚举一行就行,尽管可能有多行不会发生变换操作,但是不会发生变换操作这一过程会在代码中隐式包括了,望自行理解。 - 注意,两种情况的讨论都是在确定某一行/列的状态为标准的情况下,对每一行/列进行变换操作以保证所有01连通块都为矩阵。
尽管这句话说了两遍了,但还是想重复一遍整体思想。 - 这不禁让我想到了一个题: 费解的开关。
说实话,要不是这道题当列题学的,根本想不到是个二进制枚举,通过下一行去维护上一行的状态。是我,不是你们……
AC代码
#include<bits/stdc++.h> using namespace std; const int N=110; const int INF=0x3f3f3f3f; int a[N][N],n,m,k,ans=INF; int main() { scanf("%d%d%d",&n,&m,&k); for(int i=0;i<n;i++) for(int j=0;j<m;j++)//从0开始方便状压移位 scanf("%d",&a[i][j]); if(n<=k) { for(int t=0;t<(1<<n);t++)//枚举第一行的状态 { int tmp=0; for(int j=0;j<m;j++)//遍历列 { int cnt=0; for(int i=0;i<n;i++)//遍历行 if(a[i][j]==(t>>i&1)) cnt++;//变成与第一行状态需要的操作次数 tmp+=min(cnt,n-cnt);//可以选择变成相反的或者变成相同的,要选当然是选变换操作次数少的//太细节了!! } ans=min(ans,tmp);//记录所有方案中最小的操作次数 } } else { for(int t=0;t<n;t++)//枚举未进行变换操作的行,以此行为标准 { int tmp=0; for(int i=0;i<n;i++)//遍历行 { int cnt=0; for(int j=0;j<m;j++)//遍历列 if(a[i][j]==a[t][j]) cnt++; tmp+=min(cnt,m-cnt);//注意是m-cnt了 } ans=min(ans,tmp);//记录所有方案中最小的操作次数 } } if(ans<=k) printf("%d\n",ans); else puts("-1"); }
附图
解释一下解题思路中的第二点
假设确定某一行/列为标准,其中白代表0连通块,黑代表1连通块,其他各行/列的各个与标准行/列对应的区域的颜色要么相同要么相反,即各个红***域与其上方的黑白连通块对应。这是对于解出本题,至关重要的一点,另外一个突破点就是数据规模。
总结
难点在于得出第二点结论,和分情况讨论!
感觉看题解很容易懂,但自己做还是一点思路没有。
ref
https://blog.csdn.net/qq_36679229/article/details/89014919
https://www.cnblogs.com/kuangbin/p/3702113.html
思维 文章被收录于专栏
思维题都会了,ACM金牌就稳了! 我骗你的!