首页 > 代码库 > 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;
}