【Gym 100015A】Another Rock-Paper-Scissors Problem---饶文津

题

题意

Sonny出石头剪刀布的猜拳策略是 先出R，然后每连续两段都是打败前一段的出拳， 现在问你第n回合打败他要出什么。

分析

他的策略

R P S

PSR

SRP

PSRSRPRPS

SRPRPSPSR

… …

打败他的策略是

P S R

SRP

RPS

SRPRPSPSR

RPRPSRSRP

… …

一套策略

1 1 1

3

3

9

9

… …

第几轮

1 2 3

4-6

7-9

10-18

19-27

… …

如果n是介于3的某个次方的（1,2]倍，那就是n要打败 n减去这个次方 对应的拳，故+1（对应的是P就变成S，S就变成R，R就变成P）

如果是（2,3]倍，那就+2（P变成R，R变成S，S变成P）。

而我们要知道 n减去这个次方 对应的拳，就用递归去求了。

可以用数组储存3的次方，数据范围n<=10^12，log310^12=25.15...，所以只要求到3的25次方即可。

代码#include<stdio.h> long long n,t[26]={1}; char s[4]="RPS"; int main(){ for(int i=1;i<=25;i++) t[i]=t[i-1]*3; while(scanf("%I64d",&n)&&n){ int i=25,a=0; while(n>3){ while(n<=t[i])i--; while(n>t[i]){ n-=t[i]; a++;//推的次数 } } printf("%cn",s[(n+a)%3]); //n为1 2 3，对应PSR //a为推的次数 //（n+a）mod 3为对应的拳 // 0对应R，1对应P，2对应S } return 0; }

也可以用数学函数，我刚开始就是这样做，但是因为没有round，有误差，就WA了

#include <stdio.h> #include <cmath> #define ll long long ll n,t,a; char s[4]="RPS"; int main() { while(~scanf("%I64d",&n)&&n) { a=0; t=(ll)round(pow(3,floor(log(n)/log(3)))); //t为小于等于n的最大的3的次方，用round四舍五入取整防止误差 if(n==t)t/=3; //我们要求的是小于n的最大的3的次方，故t等于n时，t取再小一点的3的次方 while(n>t&&t>1) { n-=t; t=(ll)round(pow(3,floor(log(n)/log(3)))); if(n==t)t/=3; a++; } printf("%c",s[(n+a)%3]); } return 0; } ---来自腾讯云社区的---饶文津