题意：给定字符串，下面定义几个操作：
1）将Mx变成Mxx，例如MII可以变为MIIII
2）将III替换成U
3）去掉连续两个U，例如MIUU可以变成MI
现在问你能不能将MI转换成给定字符串。
思路：注意到以下几个性质。第一，MI怎么变换M永远只能在第一位。第二，因为变换时只能在I和U之间变换，因此，除了第一个是M以外，后面如果有字符串不是U、I以内的话永远不可能变换得到。第三，U可以看成是3个I，无论是I先变换成U再操作还是转化成一定数量的I，最后再准换成一定数量的U即可，因此将所有的字母用I作为一般等价物进行交换即可。
最后问题就转化成这样，一开始有数字1，每次进行*2或者-6两种操作，问你能不能变换成数字K（K就是题目中的3*U的数量+I的数量）
用数学推导的方法是可行的的，不过既然数量只有10^6，只需要用一次BFS打表即可。
#include<cstdio>
#include<cstring>
#define MAXN 1000010
using namespace std;
bool hash[MAXN*3];
char str[MAXN];
int queue[MAXN];
int T;
void init()
{
memset(hash,0,sizeof(hash));
hash[1]=1;
int front=0,rear=0;
queue[rear++]=1;
while(front<rear)
{
int top=queue[front]; front++;
if(top*2<MAXN && !hash[top*2]) {hash[top*2]=1; queue[rear++]=top*2;}
if(top-6>0 && !hash[top-6]) {hash[top-6]=1; queue[rear++]=top-6;}
}
}
int main()
{
init();
scanf("%d",&T);
while(T--)
{
scanf("%s",str);
bool flag=1;
int len=strlen(str),sum=0;
if(str[0]!='M') flag=0;
if(flag)
for(int i=1;i<len;++i)
{
if(str[i]!='U' && str[i]!='I') {flag=0;break;}
if(str[i]=='U') sum+=3;
else ++sum;
}
printf("%s\n",hash[sum] && flag? "Yes":"No");
}
}