p1140
就一道非常普通的二分,但是非常蛋疼的是验证mid left的过程一直错(就是写一个k次循环然后根据可行与否返回0或1的函数),不知道为什么,嗯哈希搞完了,有点纠结是把之前不熟的东西再搞一遍还是直接搞图论?但是还是先把1140ac比较重要
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
//#include<cmath>
using namespace std;
inline int read(){
int bj=;char ch=getchar();
while(ch<''||ch>''){
if(ch=='-')bj=-;
ch=getchar();
}
int ret=;
while(ch>=''&&ch<=''){ret=ret*+ch-'';ch=getchar();}
return ret*bj;
}
int n,m,k,map[][]={},a[]={};
bool vis[]={};
void init(){
n=read();m=read();k=read();
for(int i=;i<=n;i++){
for(int j=;j<=*m;j++){
char ch;
cin>>ch;
map[i][j]=ch-'';
}
}
}
void orbit(int idx){
a[]=;
for(int i=;i<=n;i++)a[++a[]]=map[i][idx];
for(int i=n;i;i--)a[++a[]]=map[i][idx+m];
}
int L(int x,int R) {
int pos=x-R,lim=*n;
pos+=lim;
if(pos%lim==)return lim;
return pos%lim;
}
int R(int x,int R) {
int pos=x+R,lim=*n;
if(pos%lim==)return lim;
return pos%lim;
}
void cover(int x,int r) {
for(int i=;i<=r;i++)vis[L(x,i)]=vis[R(x,i)]=;
}
bool check(int r) {
memset(vis,,sizeof(vis));
int st=(n+)/,ans=;
cover(st,r);
int pos=R(st,r+);
while(pos!=st){
//if(r==2)cout<<pos<<"<----\n";
if(vis[pos]){
pos=R(pos,);
continue;
}
bool fl=;
for(int j=r;j;j--){
if(a[R(pos,j)]==){
fl=;
ans++;
cover(R(pos,j),r);
break;
}
}
if(fl)continue;
if(a[pos]==){
fl=;
ans++;
cover(pos,r);
}
if(fl)continue;
for(int j=;j<=r;j++){
if(a[L(pos,j)]==){
fl=;
ans++;
cover(L(pos,j),r);
break;
}
}
if(fl)continue;
return ;
}
return ans<=k;
}
void Binary_Search(){
int l=,r=*n+,ans=;
while(l<=r){
int mid=(l+r)>>;
if(check(mid)){
ans=mid;
r=mid-;
}
else l=mid+;
}
printf("%d\n",ans);
}
void work(){
for(int i=;i<=m;i++){
orbit(i);
Binary_Search();
}
}
int main(){
init();
work();
return ;
}