这几天把SLPC2011的题目做一下
这里是题目连接：
A.Another Rock-Paper-Scissors Problem
题目大意；给出Sonny在每一局出石头剪刀布的规则（具体规则将不太清楚，自己看题目吧），问你在第N局出什么才能赢过Sonny？
题目分析：根据题意，我们可以发现连续的几局可分成若干块（每一块的局数显然与3的幂次有关，是个人都看得出，我就不再解释原因），每一块出什么都是由上一块决定的。这就提醒我们可以使用递归来解决这一题。设f(N)表示第N局Sunny出的东西（我们用0表示R，1表示P，2表示S），则f(N)=(f(N-delta)+1)mod 3，其中delta表示小于n的最大的3的幂次方，即delta=max{3^i|3^i<N,i∈N }，这个递归的边界条件就是f(N)=N-1, N<=3。这样在O(log3N)的时间内就解决了这一题。
View Code #includetypedef long long LL;LL p[30];LL n;int get(LL n){ int i,ret; LL del; if (n<=3) return n; for (i=0;i<30;i++) if (p[i]>=n) break; del=p[i-1]; ret=(get(n-del)+1)%4; if (!ret) ret++; return ret;}int main(){ int i,ans; freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); p[0]=1; for (i=1;i<30;i++) p[i]=p[i-1]*3; while (scanf("%I64d",&n)!=EOF&&n>0) { ans=(get(n)+1)%4; if (!ans) ans++; if (ans==1) printf("R\n"); else if (ans==2) printf("P\n"); else printf("S\n"); } fclose(stdin); fclose(stdout); return 0;}
B.Ball Painting
待续
C.City Driving
待续
D.Drunken Walk
待续
E.Empty Triangles
待续
F.Fighting for Triangles
待续
G.Guessing Game
待续
H.Hidden Code
待续
I.Identity Checker
待续