[codeforces 1380B] Universal Solution 剪刀石头布(将所有情况聚集的构造)

Educational Codeforces Round 91 (Rated for Div. 2)   参与排名人数6879   不熬夜打比赛的感觉真好

[codeforces 1380B]   Universal Solution   剪刀石头布(将所有情况聚集的构造)

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

在线测评地址https://codeforces.com/contest/1380/problem/B

题目难懂，但靠此图，很快弄懂题意

题目大意：剪刀石头布的游戏，对手出拳序列已在输入数据中给出，要求编程者给出自己的出拳字母序列。对手从位置1与编程者位置1进行比较，编程者赢，此时结果加1,编程者输或平局，结果什么也不干，对手从位置2与编程者位置2进行比较，依次类推，此时所有结果记为win(1).对手从位置2与编程者位置1进行比较，编程者赢，此时结果加1,编程者输或平局，结果什么也不干，对手从位置3与编程者位置4进行比较，依次类推，此时所有结果记为win(2).

......对手从位置n与编程者位置1进行比较，编程者赢，此时结果加1,编程者输或平局，结果什么也不干，对手从位置1与编程者位置2进行比较，依次类推，此时所有结果记为win(n).

要求win(1)+win(2)+......+win(n)和值最大，输出此时编程者给出的出拳字母序列。

样例说明如下：

RSPRSP位置123
s   RSP
c   RSPif bot will start from pos=1, then (s1,c1) is draw, (s2,c2) is draw and (s3,c3) is draw, so win(1)=0;
(s1,c1)对应(R,R)，此时平局。
(s2,c2)对应(S,S)，此时平局。
(s3,c3)对应(P,P)，此时平局。if bot will start from pos=2, then (s2,c1) is win, (s3,c2) is win and (s1,c3) is win, so win(2)=3;
(s2,c1)对应(S,R)，此时编程者赢。
(s3,c2)对应(P,S)，此时编程者赢。
(s1,c3)对应(R,P)，此时编程者赢。if bot will start from pos=3, then (s3,c1) is lose, (s1,c2) is lose and (s2,c3) is lose, so win(3)=0; 
(s3,c1)对应(P,R)，此时编程者输。
(s1,c2)对应(R,S)，此时编程者输。
(s2,c3)对应(S,P)，此时编程者输。仔细观察将win(1),win(2),win(3)的计算过程放在一起，可以看到:
c1会面对s1,s2,s3.要求c1尽可能的赢下s1,s2,s3的最多数量。核心在于统计s1,s2,s3中雷同字母数量。
c2会面对s1,s2,s3.要求c2尽可能的赢下s1,s2,s3的最多数量。核心在于统计s1,s2,s3中雷同字母数量。
c3会面对s1,s2,s3.要求c3尽可能的赢下s1,s2,s3的最多数量。核心在于统计s1,s2,s3中雷同字母数量。
故c1,c2,c3对应的字母雷同。故以下三种输出都是答案
RRR
SSS
PPP

样例数据重新构造如下：

Input:
3
RRRR
RSP
S
Output:
PPPP
RRR
R

AC代码如下：

#include <stdio.h>
#include <string.h>
#define maxn 200010
char s[maxn];
int main(){int t,n,i,R,S,P,mx;char c;scanf("%d",&t);while(t--){R=S=P=0;scanf("%s",s);n=strlen(s);for(i=0;i<n;i++)if(s[i]=='R')R++;else if(s[i]=='S')S++;else if(s[i]=='P')P++;if(R>S)c='R',mx=R;//R,S中最大else c='S',mx=S;if(mx<P)c='P',mx=P;//找R,S,P中最大if(c=='R')c='P';//设置编程者对应字母else if(c=='S')c='R';else if(c=='P')c='S';for(i=0;i<n;i++)printf("%c",c);printf("\n");}return 0;
}