首页 > 代码库 > CF:Problem 426B - Sereja and Mirroring 二分或者分治
CF:Problem 426B - Sereja and Mirroring 二分或者分治
这题解法怎么说呢,因为我是把行数逐步除以2暴力得到的答案,所以有点二分的意思,但是昨天琦神说是有点像分治的意思,反正总的来说:就是从大逐步细化找到最优答案。
但是昨晚傻B了,靠!多写了点东西,然后就错了,刚才一练习,拿昨晚的代码一看,就把6行代码删去就过了,靠!昨晚应该是脑子进水了!!!!!
昨晚的代码:
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define sca(a) scanf("%d",&a) #define sc(a,b) scanf("%d%d",&a,&b) #define pri(a) printf("%d\n",a) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define MM 4105 #define MN 105 #define INF 100004 #define eps 1e-7 using namespace std; typedef long long ll; int n,m,i,j,k,a[MN][MN]; string s,ss; int main() { sc(n,m); for(i=0; i<n; i++) for(j=0; j<m; j++) sca(a[i][j]); if(n&1) cout<<n<<endl; else { int r=n/2,flag=1,ff=1; int aa=a[0][0]; for(i=1; i<n; i++) //就是这个多判断了,因为自己给出的样列是1列,所以……靠,本来在下面的sum值那里已经处理了,然后忘了把这删了,所以就在第一列相同的时候出错了,导致昨晚没debug出来!嘛嘛呀!!!! if(aa!=a[i][0]) { ff=0; break; } if(ff) cout<<1<<endl; else { int sum=0; while(r&&flag) { for(i=0; i<n&&flag; i+=r*2) { for(j=i,k=i+r+r-1; j<k&&flag; j++,k--) { for(int p=0; p<m&&flag; p++) if(a[j][p]!=a[k][p]) flag=0; } } if(flag&&(r%2==0)) r/=2; if(flag&&(r&1)) sum++; if(sum>3) break; //cout<<"--"<<flag<<‘ ‘<<r<<endl; } if(!flag) cout<<r*2<<endl; else cout<<r<<endl; } } return 0; }
AC代码:
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define sca(a) scanf("%d",&a) #define sc(a,b) scanf("%d%d",&a,&b) #define pri(a) printf("%d\n",a) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define MM 4105 #define MN 105 #define INF 100004 #define eps 1e-7 using namespace std; typedef long long ll; int n,m,i,j,k,a[MN][MN]; string s,ss; int main() { sc(n,m); for(i=0; i<n; i++) for(j=0; j<m; j++) sca(a[i][j]); if(n&1) cout<<n<<endl; else { int r=n/2,flag=1,ff=1; int sum=0; while(r&&flag) { for(i=0; i<n&&flag; i+=r*2) { for(j=i,k=i+r+r-1; j<k&&flag; j++,k--) { for(int p=0; p<m&&flag; p++) if(a[j][p]!=a[k][p]) flag=0; } } if(flag&&(r%2==0)) r/=2; if(flag&&(r&1)) sum++; if(sum>3) break; //cout<<"--"<<flag<<‘ ‘<<r<<endl; } if(!flag) cout<<r*2<<endl; else cout<<r<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。