题意

分析

考场做法同题解一样。

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;
}

test20181006 石头剪刀布

原文：https://www.cnblogs.com/autoint/p/9747366.html