HDU 4662 MU Puzzle (水題)

題意：給定字符串，下面定義幾個操作：

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");  
    }  
}