https://www.cometoj.com/contest/39/problem/C?myself=0&result=0&page=2&contestID=39&problemID=C
题意： n*m方格0为空，1为障碍物，k次切割行或列切，使得每部分0个数一样；
题解：暴力枚举行切a刀，列就b=k-a;此时方法是已经固定的，行列分开处理平均每行或每列的平均0个数。找到相应位置再枚举每个块看符合不；
总结：vector还可以直接比较！！！没意识到行列可以分开处理；
#include<algorithm> #include<set> #include<queue> #include<cmath> #include<cstring> #include<iostream> #include<set> #include<vector> #include<queue> #include<cmath> #include<cstdio> #include<map> #include<stack> #include<string> #include<bits/stdc++.h> using namespace std; #define sfi(i) scanf("%d",&i) #define pri(i) printf("%d\n",i) #define sff(i) scanf("%lf",&i) #define ll long long #define ull unsigned long long #define mem(x,y) memset(x,y,sizeof(x)) #define INF 0x3f3f3f3f #define eps 1e-16 #define PI acos(-1) #define lowbit(x) ((x)&(-x)) #define zero(x) (((x)>0?(x):-(x))<eps) #define fl() printf("flag\n") #define MOD(x) ((x%mod)+mod)%mod #define endl '\n' #define pb push_back #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) const int maxn=1e3+9; const int mod=1e9+7; inline ll read() { ll f=1,x=0; char ss=getchar(); while(ss<'0'||ss>'9') { if(ss=='-')f=-1;ss=getchar(); } while(ss>='0'&&ss<='9') { x=x*10+ss-'0';ss=getchar(); } return f*x; } vector<int>ans; char s[maxn][maxn]; int R[maxn],C[maxn],sum[maxn][maxn]; int n,m,k,tot; void ch(int a,int b) { vector<int>tr,tc,tmp; int rnum=tot/(a+1); int cnum=tot/(b+1); int avg=tot/(a+1)/(b+1); for(int i=1;i<=a;i++) { int rpos=lower_bound(R+1,R+1+n,rnum*i)-R; if(rpos>n||R[rpos]!=rnum*i) return; tr.push_back(rpos); } for(int i=1;i<=b;i++) { int cpos=lower_bound(C+1,C+1+m,cnum*i)-C; if(cpos>m||C[cpos]!=cnum*i) return; tc.push_back(cpos); } for(int i=0;i<a;i++) { for(int j=0;j<b;j++) { if(sum[tr[i]][tc[j]]!=(i+1)*(j+1)*avg) return ; } } for(int i=0;i<a;i++) tmp.push_back(tr[i]); for(int i=0;i<b;i++) tmp.push_back(tc[i]+n-1); if(tmp<ans) ans=tmp; } int main() { //FAST_IO; //freopen("input.txt","r",stdin); int t; cin>>t; while(t--) { //mem(sum,0); //mem(R,0); //mem(C,0); ans.clear(); ans.push_back(INF); cin>>n>>m>>k; for(int i=0;i<=n;i++) { for(int j=0;j<=m;j++) sum[i][j]=0; } for(int i=0;i<=n;i++) R[i]=0; for(int i=0;i<=m;i++) C[i]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>s[i][j]; int num=0; if(s[i][j]=='0') num=1; sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+num; //R[i]+=num;//不行，R数组是前面行的前缀和，不是当行的 //C[j]+=num; } } for(int i=1;i<=n;i++) R[i]=sum[i][m]; for(int i=1;i<=m;i++) C[i]=sum[n][i]; tot=sum[n][m]; if(tot==0) { for(int i=1;i<=k;i++) { if(i!=1) cout<<" "; cout<<i; } cout<<endl; continue; } for(int a=0;a<=k;a++) { int b=k-a; if(tot%((a+1)*(b+1))==0&&a<n&&b<m) ch(a,b); } if(ans[0]==INF) { cout<<"Impossible"<<endl; } else { for(int i=0;i<k;i++) { if(i!=0) cout<<" "; cout<<ans[i]; } cout<<endl; } } return 0; }
