MU Puzzle
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 134 Accepted Submission(s): 71
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 6.
Output
n lines, each line is 'Yes' or 'No'.
Sample Input
2 MI MU
Sample Output
Yes No
Source
Recommend
zhuyuanchen520
全场最水的题目。
一开始时MI。
其实可以全部转化成I的个数。
一个U相当于3个I，减少两个U，相当于减少6个I。
第一个操作相当于可以把I的个数翻倍。
所以1个I，2个I，4个I，8,16,32，。。。。这些2^n个I都是可以实现的。
而且可以减掉6个I，8-6=2,16-6=10,10-6=4，等等都可以。
10个I可以，20个I也可以。
这样数I的个数，比赛时候暴力预处理下所以可以的情况，就像晒素数一样。
其实可以发现规律的，除了一个I之外，奇数个I和个数被6整除的都不行，可以根据整除性分析下。
贴上代码，里面有一个init函数式预处理的，虽然没有用上
1 /* 2 * Author: kuangbin 3 * Created Time: 2013/8/8 11:54:08 4 * File Name: 1008.cpp 5 */ 6 #include7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 using namespace std;19 char str[1000010];20 const int MAXN = 3000010;21 bool dp[MAXN];22 bool vis[MAXN];23 void init()24 {25 memset(dp,false,sizeof(dp));26 memset(vis,false,sizeof(vis));27 dp[1] = true;28 queue q;29 q.push(1);30 vis[1] = true;31 while(!q.empty())32 {33 int tmp = q.front();34 dp[tmp] = true;35 q.pop();36 if(tmp == 0){dp[0] = true;vis[0] = true;continue;}37 if(tmp >= 6 && !vis[tmp-6])38 {39 q.push(tmp-6);40 vis[tmp-6] = true;41 }42 tmp *= 2;43 while(tmp < MAXN)44 {45 if(vis[tmp])break;46 dp[tmp] = true;47 if(tmp >= 6 && !vis[tmp-6])48 {49 q.push(tmp-6);50 vis[tmp-6] = true;51 }52 tmp *= 2;53 }54 }55 }56 57 58 int main()59 {60 int T;61 init();62 scanf("%d",&T);63 while(T--)64 {65 bool flag = true;66 scanf("%s",str);67 int len = strlen(str);68 if(str[0]!='M')69 {70 printf("No\n");71 continue;72 }73 int cnt = 0;74 for(int i = 1;i < len;i++)75 {76 if(str[i]=='M')77 {78 flag = false;79 break;80 }81 if(str[i] =='I')cnt++;82 else cnt+= 3;83 }84 if(!flag)85 {86 printf("No\n");87 continue;88 }89 if(cnt == 1)90 {91 printf("Yes\n");92 continue;93 }94 if(cnt%2 == 1 || cnt%6 == 0)printf("No\n");95 else printf("Yes\n");96 }97 return 0;98 }