题意：给定一个串 MI，问你进行一下三种操作，（1）M后面的那一段复制并接在串后面 （2）‘III’ 变为'U' （3）消除'UU'
给定你一些目标串，问你是否经过变换后（不限步数）能否把从‘MI’变为目标串
解题思路：逆向推，把U变为I，所有I的个数必须是 2^k 或者 2^k - 6*x ,所以我们就枚举k ，看是否可行
解题代码：
1 // File Name: 4611.cpp 2 // Author: darkdream 3 // Created Time: 2013年08月09日 星期五 15时58分50秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 25 using namespace std; 26 char str[1000005]; 27 int main(){ 28 //freopen("/home/plac/problem/input.txt","r",stdin); 29 //freopen("/home/plac/problem/output.txt","w",stdout); 30 int t ; 31 scanf("%d",&t); 32 while(t--) 33 { 34 scanf("%s",str); 35 int len = strlen(str); 36 int ok = 1; 37 if(str[0] != 'M' ) 38 ok =0 ; 39 long long total = 0 ; 40 for(int i = 1;i < len ;i ++) 41 { 42 if(str[i] == 'M') 43 ok = 0; 44 else if(str[i] == 'U') 45 total += 3; 46 else total += 1; 47 } 48 long long k = 1; 49 int ok1 = 0 ; 50 for(int i = 1; i <= 60;i ++) 51 { 52 if( k >= total && (k - total) % 6 == 0 ) 53 { 54 ok1 = 1; 55 break; 56 } 57 k *= 2; 58 59 } 60 if(ok1 && ok ) 61 printf("Yes "); 62 else printf("No "); 63 64 } 65 return 0; 66 }