首页 > 代码库 > Codeforces 838A - Binary Blocks(二维前缀和+容斥)
Codeforces 838A - Binary Blocks(二维前缀和+容斥)
838A - Binary Blocks
思路:求一下前缀和,然后就能很快算出每一小正方块中1的个数了,0的个数等于k*k减去1的个数,两个的最小值就是要加进答案的值。
代码:
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset((a),(b),sizeof(a)) const int INF=0x3f3f3f3f; const int N=5000; char mp[N][N]; int Mp[N][N]={0}; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; for(int i=1;i<=n;i++)cin>>mp[i]+1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) Mp[i][j]=mp[i][j]-‘0‘; } for(int i=1;i<N;i++) { for(int j=1;j<N;j++) { Mp[i][j]+=Mp[i-1][j]+Mp[i][j-1]-Mp[i-1][j-1]; } } int minn=min(n,m); int ans=INF; for(int i=2;i<=minn;i++) { bool flag=true; int x=n/i; int y=m/i; if(n%i)x++; if(m%i)y++; int cnt=0; for(int j=1;j<=x;j++) { for(int k=1;k<=y;k++) { if(j==1&&k==1) { int t=Mp[j*i][k*i]; cnt+=min(i*i-t,t); } else { int t=Mp[j*i][k*i]+Mp[j*i-i][k*i-i]-Mp[j*i][k*i-i]-Mp[j*i-i][k*i]; cnt+=min(i*i-t,t); } } } ans=min(ans,cnt); } printf("%d\n",ans); return 0; }
Codeforces 838A - Binary Blocks(二维前缀和+容斥)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。