题意
分析
考场做法同题解一样。
std代码。
#include<bits/stdc++.h>
using namespace std;
template <typename T> void chmin(T&x,const T &y)
{
if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
if(x<y)x=y;
}
typedef long long s64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef pair<int,int> pii;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define rep0(i,l,r) for(int i=l;i<r;++i)
#define gc (c=getchar())
int read()
{
char c;
while(gc<'-');
if(c=='-')
{
int x=gc-'0';
while(gc>='0')x=x*10+c-'0';
return -x;
}
int x=c-'0';
while(gc>='0')x=x*10+c-'0';
return x;
}
#undef gc
int n,need_a[3];
const char s[]="RPS";
string write(int n,int x)
{
if(!n)
{
string ans;
ans.push_back(s[x]);
return ans;
}
string a=write(n-1,x),b=write(n-1,(x+1)%3);
return a<b?a+b:b+a;
}
bool check(int x)
{
int a[3]={},a0[3];
a[x]=1;
rep(tmp,1,n)
{
rep(i,0,2)a0[i]=a[i];
rep(i,0,2)a[(i+1)%3]+=a0[i];
}
//cerr<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
rep(i,0,2)
if(a[i]!=need_a[i])return 0;
cout<<write(n,x)<<endl;
return 1;
}
int main()
{
freopen("rps.in","r",stdin);freopen("rps.out","w",stdout);
rep(i,0,2)need_a[i]=read();
n=0;
while((1<<n)!=need_a[0]+need_a[1]+need_a[2])++n;
int i=0;
for(;i<=2;++i)
if(check(i))break;
if(i>2)puts("IMPOSSIBLE");
}
我的代码。排序的时候我用的递推处理，跑得比std快。
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<complex>
#pragma GCC optimize ("O0")
using namespace std;
template<class T> inline T read(T&x)
{
T data=0;
int w=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
data=10*data+ch-'0',ch=getchar();
return x=data*w;
}
typedef long long ll;
const int INF=0x7fffffff;
const int MAXN=1<<20|7;
int a[2][MAXN],len[2];
int cur;
int main()
{
freopen("rps.in","r",stdin);
freopen("rps.out","w",stdout);
int R,P,S;
read(R);read(P);read(S);
int n;
for(int i=1;i<=20;++i)
if(R+P+S==(1<<i))
n=i;
// cerr<<"n="<<n<<endl;
for(int i=1;i<=3;++i)
{
cur=0;
len[cur]=0;
a[cur][++len[cur]]=i;
for(int j=1;j<=n;++j)
{
cur^=1;
len[cur]=0;
for(int k=1;k<=len[cur^1];++k)
{
if(a[cur^1][k]==1)
{
a[cur][++len[cur]]=1;
a[cur][++len[cur]]=2;
}
else if(a[cur^1][k]==2)
{
a[cur][++len[cur]]=2;
a[cur][++len[cur]]=3;
}
else
{
a[cur][++len[cur]]=1;
a[cur][++len[cur]]=3;
}
}
}
int r=0,p=0,s=0;
for(int j=1;j<=len[cur];++j)
{
if(a[cur][j]==1)
++p;
else if(a[cur][j]==2)
++r;
else
++s;
}
if(R==r&&P==p&&S==s)
{
for(int l=1;l<=n;++l) // the log of the sum of swap len
{
int d=(1<<l); // the sum of swap len
for(int j=1;j<len[cur];j+=d)
{
int x=j,y=j+(d>>1);
while(a[cur][x]==a[cur][y]&&x<j+(d<<1))
++x,++y;
if(x<j+(d<<1))
{
// cerr<<"x="<<x<<" y="<<y<<endl;
// cerr<<"cmp"<<a[cur][x]<<" "<<a[cur][y]<<endl;
if(a[cur][x]<a[cur][y])
continue;
// cerr<<"swap fr "<<j<<" to "<<(j+(d>>1))<<endl;
for(int k=j;k<j+(d>>1);++k)
swap(a[cur][k],a[cur][k+(d>>1)]);
}
}
}
for(int j=1;j<=len[cur];++j)
{
if(a[cur][j]==1)
putchar('P');
else if(a[cur][j]==2)
putchar('R');
else
putchar('S');
}
puts("");
return 0;
}
}
puts("IMPOSSIBLE");
// fclose(stdin);
// fclose(stdout);
return 0;
}