HDU 4662 MU Puzzle

MU Puzzle

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 299 Accepted Submission(s): 157

Problem Description

Suppose there are the symbols M, I, and U which can be combined to produce strings of symbols called "words". We start with one word MI, and transform it to get a new word. In each step, we can use one of the following transformation rules:

1. Double any string after the M (that is, change Mx, to Mxx). For example: MIU to MIUIU.

2. Replace any III with a U. For example: MUIIIU to MUUU.

3. Remove any UU. For example: MUUU to MU.

Using these three rules is it possible to change MI into a given string in a finite number of steps?

Input

First line, number of strings, n. Following n lines, each line contains a nonempty string which consists only of letters 'M', 'I' and 'U'.
Total length of all strings <= 10⁶.

Output

n lines, each line is 'Yes' or 'No'.

Sample Input

2

MI

MU

Sample Output

Yes

No

Source

2013 Multi-University Training Contest 6

多校第六场也结束了，我们队每场都只能过一两道题，感觉前途渺茫啊……

第六场的1008，这场比赛我唯一AC的一道题，也是我们队唯一AC的一道题

给一个字符串，问它能否由MI按照题干中给的规则转换过来

我的做法是，由规则逆向思考，先所给串中所有的U全部换成3个I，然后统计I的个数。

由第一条规则和第三条规则易知I的个数一定能写成（2^x-6*y）的形式，否则不能由MI转化过来

因此只要判断I的个数和比刚好比它大的两个2^x的差能否被六整除即可。（注意这里一定要判断2个2^x，因为2^x对六的模可能是2或4，交替出现）

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 
 5 using namespace std;
 6 
 7 int len;
 8 int two[50];
 9 char s[1000100];
10 
11 void initial()
12 {
13     two[0]=1;
14     for(int i=1;i<=30;i++)
15         two[i]=two[i-1]*2;
16 }
17 
18 int main()
19 {
20     int t;
21 
22     initial();
23 
24     scanf("%d",&t);
25     getchar();
26 
27     while(t--)
28     {
29         gets(s);
30         if(s[0]!='M')
31         {
32             cout<<"No"<<endl;
33             continue;
34         }
35         int len,ans=0;
36         bool flag=true;
37         len=strlen(s);
38         for(int i=1;i<len&&flag;i++)
39             if(s[i]=='I')
40                 ans++;
41             else if(s[i]=='U')
42                 ans+=3;
43             else if(s[i]=='M')
44             {
45                 cout<<"No"<<endl;
46                 flag=false;
47             }
48         if(!flag)
49             continue;
50         int i;
51         for(i=0;i<=30;i++)
52             if(two[i]>=ans)
53                 break;
54         if((two[i]-ans)%6==0||(two[i+1]-ans)%6==0)
55             cout<<"Yes"<<endl;
56         else
57             cout<<"No"<<endl;
58     }
59 
60     return 0;
61 }

[C++]