本文共 1224 字，大约阅读时间需要 4 分钟。

【题解】

读成输出字典序最小的连续元素不相同序列orz

题意：给定偏爱策略的人数要求输出字典序最小的序列使得：连续两位对战出新一轮的选手，每一轮不出现平局直到决出第一名。

思路：根据获胜者的偏爱决策可以推出对战的两人的偏爱决策，所以枚举最终获胜者的偏爱决策判断一下就好了。字典序问题只需递归处理+暴力 cmp ，时间复杂度 O(2^n×n)。

考虑到字典序大小P<R<S和石头剪刀布的游戏规则，在构造时：最终答案为P，推出对决两人为PR；R->RS；S->PS。由于决斗时左区间和右区间的顺序不影响最终结果，所以在构造时还要比较左右区间，保证字典序尽可能小。

【代码】

#include 
   
    using namespace std;const int maxn=1024*1024;int r,s,p,c[4];int ans[maxn+5];void dfs(int x,int l,int r) //区间[l,r]的最终结果为x{    if(l==r){        ans[l]=x;        c[x]++;        return ;    }    int f=0;    int mid=(l+r)>>1;    if(x==0) dfs(0,l,mid),dfs(1,mid+1,r); //PR    else if(x==1) dfs(1,l,mid),dfs(2,mid+1,r); //RS    else dfs(0,l,mid),dfs(2,mid+1,r); //PS    for(int i=l;i<=mid;i++){        if(ans[i]
    
     ans[mid+i-l+1]){ f=1; break; }    }    if(f){ //左区间>右区间，左右交换        for(int i=l;i<=mid;i++) swap(ans[i],ans[mid+i-l+1]);    }}int main(){    scanf("%d%d%d",&r,&p,&s);    int sum,f=0; sum=r+s+p;    for(int i=0;i<=2;i++){        memset(c,0,sizeof(c));        dfs(i,1,sum);        if(c[0]==p&&c[1]==r&&c[2]==s){            f=1; break;        }    }    if(f){        char ch[]={'P','R','S'};        for(int i=1;i<=sum;i++) printf("%c",ch[ans[i]]);        //puts("");    }    else puts("IMPOSSIBLE");    return 0;}
    
   

转载地址：http://bbben.baihongyu.com/