正文

sgu 126 Boxes

IP云
IP云V管理员/4 阅读
09/21
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

开始用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 ;
}