sgu 126 Boxes

题意：较大的容量减较小的容量，较小的容量翻倍。问操作几回其中一个空。

开始用set判重，重复就不可行。不过状态最多有2e18种。不仅爆内存，还超时。然后找规律。发现只有比例为1:1,1:3,1:7,3:5,1:15,3:13,5:11,7:9......这样才行。也就是化简以后相加是2^k。

#pragma comment(linker,"/STACK:1024000000,1024000000")

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <iomanip>

#include <cstring>

#include <map>

#include <queue>

#include <set>

#include <cassert>

#include <list>

#define mkp make_pair

using namespace std;

const double EPS=1e-;

const int SZ=1e2+,INF=0x7FFFFFFF;

const long long mod=;

typedef long long lon;

int gcd(int x,int y)

{

    if(x==)return y;

    if(y==)return x;

    if(x<y)swap(x,y);

    int res=;

    for(;;)

    {

        int rem=x%y;

        if(rem==)return y;

        x=y;

        y=rem;

    }

}

int cnt(int x)

{

    int res=;

    for(;x;x-=x&-x,++res);

    return res;

}

int chk(int x)

{

    int num=cnt(x);

    if(num!=)return -;

    else

    {

        for(int i=;i<;++i)

        {

            if((<<i)&x)return i;

        }

    }

}

int main()

{

    std::ios::sync_with_stdio();

    //freopen("d:\\1.txt","r",stdin);

    int casenum;

    //cin>>casenum;

    //scanf("%d",&casenum);

    //for(int time=1;time<=casenum;++time)

    //for(int time=1;cin>>n;++time)

    {

        int n,m;

        cin>>n>>m;

        int d=gcd(n,m);

        //cout<<d<<endl;

        n/=d,m/=d;

        if(n==||m==)cout<<<<endl;

        else

        {

            cout<<chk(n+m)<<endl;

        }

    }

    return ;

}

超内存的：

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <iomanip>

#include <cstring>

#include <map>

#include <queue>

#include <set>

#include <cassert>

#include <list>

using namespace std;

const double EPS=1e-;

const int SZ=1e2+,INF=0x7FFFFFFF;

const long long mod=;

typedef long long lon;

int n,sum[],arr[];

bool chk(int x,int t)

{

    int res=;

    if(x/n&&arr[x]<arr[x-n])++res;

    if(x%n&&arr[x]<arr[x-])++res;

    if(x/n!=n-)

    {

        if(t)

        {

            if(arr[x]<arr[x+n])++res;

        }

        else ++res;

    }

    if(x%n!=n-)

    {

        if(t)

        {

            if(arr[x]<arr[x+])++res;

        }

        else ++res;

    }

    return t?res==sum[x]:res>=sum[x];

}

bool dfs(int x)

{

    //cout<<x<<endl;

    if(x==n*n)

    {

//        for(int i=0;i<n*n;++i)

//        {

//            cout<<arr[i]<<" ";

//        }cout<<endl;

        return ;

    }

    for(int i=;i<;++i)

    {

        arr[x]=i;

        if(x%n&&chk(x-,||((x-)/n==n-))==)continue;

        if(x/n&&chk(x-n,)==)continue;

        if(x==n*n-&&chk(x,)==)continue;

        //cout<<x<<" "<<i<<endl;

        if(dfs(x+))return ;

        //else cout<<x<<" "<<i<<" fail"<<endl;

    }

    arr[x]=;

    return ;

}

int main()

{

    std::ios::sync_with_stdio();

    //freopen("d:\\1.txt","r",stdin);

    int casenum;

    //cin>>casenum;

    //scanf("%d",&casenum);

    //for(int time=1;time<=casenum;++time)

    //for(int time=1;cin>>n;++time)

    {

        cin>>n;

        for(int i=;i<n*n;++i)

        {

            cin>>sum[i];

        }

        if(n==)

        {

            if(sum[]==)cout<<<<endl;

            else cout<<"NO SOLUTION"<<endl;

        }

        else if(dfs())

        {

            for(int i=;i<n*n;++i)

            {

                if(i%n)cout<<" ";

                cout<<arr[i];

                if(i%n==n-)cout<<endl;

            }

        }

        else

        {

            cout<<"NO SOLUTION"<<endl;

        }

    }

    return ;

}

超时的：

#pragma comment(linker,"/STACK:1024000000,1024000000")

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <iomanip>

#include <cstring>

#include <map>

#include <queue>

#include <set>

#include <cassert>

#include <list>

#define mkp make_pair

using namespace std;

const double EPS=1e-;

const int SZ=1e2+,INF=0x7FFFFFFF;

const long long mod=;

typedef long long lon;

int work(int x,int y,int x1,int y1,int s)

{

    if(x<y)swap(x,y);

    if(x1<y1)swap(x1,y1);

    //cout<<x<<" "<<y<<" "<<x1<<" "<<y1<<endl;

    if(s!=&&x==x1&&y==y1)return -;

    x-=y;

    y*=;

    x1-=y1;

    y1*=;

    if(x<y)swap(x,y);

    if(x1<y1)swap(x1,y1);

    //if(s!=1&&x==x1&&y==y1)return -1;

    x1-=y1;

    y1*=;

    if(x==||y==)return s;

    return work(x,y,x1,y1,s+);

}

int main()

{

    std::ios::sync_with_stdio();

    //freopen("d:\\1.txt","r",stdin);

    int casenum;

    //cin>>casenum;

    //scanf("%d",&casenum);

    //for(int time=1;time<=casenum;++time)

    //for(int time=1;cin>>n;++time)

    {

        int n,m;

        cin>>n>>m;

        if(n==||m==)cout<<<<endl;

        else if((n&)^(m&))cout<<-<<endl;

        else cout<<work(n,m,n,m,)<<endl;

    }

    return ;

}