UVA11489Integer Game博弈

题目大意：

S和T在玩游戏，S先。给出一数字串，两人轮流取出一个数字，要求每次取完之后剩下的数为3的倍数，或者没有数字留下。如果两个人足够聪明，求胜利的一方。

对于本题而言，S先手，他若想赢，只需要处理好两种情况1.总和为3的倍数2.总和不是3的倍数.

对于2.S必须拿一个非3，6，9而且使剩下的凑成3的倍数。这时T面临的情况就和S在1.开始时相同，而S若想赢，3，6，9的总和就得是偶数

11489 Integer GameTwo players, S and T, are playing a game where they make alternate moves. S plays first.In this game, they start with an integer N. In each move, a player removes one digit from theinteger and passes the resulting number to the other player. The game continues in this fashion untila player finds he/she has no digit to remove when that player is declared as the loser.With this restriction, its obvious that if the number of digits in N is odd then S wins otherwise Twins. To make the game more interesting, we apply one additional constraint. A player can remove aparticular digit if the sum of digits of the resulting number is a multiple of 3 or there are no digits left.Suppose N = 1234. S has 4 possible moves. That is, he can remove 1, 2, 3, or 4. Of these, two ofthem are valid moves.• Removal of 4 results in 123 and the sum of digits = 1 + 2 + 3 = 6; 6 is a multiple of 3.• Removal of 1 results in 234 and the sum of digits = 2 + 3 + 4 = 9; 9 is a multiple of 3.The other two moves are invalid.If both players play perfectly, who wins?InputThe first line of input is an integer T (T < 60) that determines the number of test cases. Each case isa line that contains a positive integer N. N has at most 1000 digits and does not contain any zeros.OutputFor each case, output the case number starting from 1. If S wins then output ‘S’ otherwise output ‘T’.Sample Input3433771Sample OutputCase 1: SCase 2: TCase 3: T

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,m[10],sum,sum1,cnt,temp;
char num[1005];
int main()
{
   // freopen("cin.txt","r",stdin);
    scanf("%d",&t);
    int cnt=1;
    while(t--)
    {
         printf("Case %d: ",cnt++);
         scanf("%s",num);
         memset(m,0,sizeof(m));
         sum=0,sum1=0;
         int len=strlen(num);
         if(len==1)//一开始这里写成了len=1 ->_-> 能不能用点心
         {
              printf("S\n");continue;
         }
         for(int i=0;i<len;i++)
         {
              temp=num[i]-'0';
              m[temp]++;
              sum+=(temp);
              if(temp%3==0) sum1++;
         }
         char qq='T';
         if(sum%3==0)
         {
              if(sum1%2)
              {
                   qq='S';
              }
         }
         else //if(sum1%2)
         {
              for(int i=0;i<=9;i++)
              {
                   if(m[i]&&(sum-i)%3==0&&(i%3))
                   {
                        if(sum1%2==0) qq='S';
                        break;
                   }
              }
         }
         printf("%c\n",qq);
    }
    return 0;
}