HDU 4662——MU Puzzle

這個題目的來源是人工智能領域MU猜想。比賽的時候也參考了相關資料，可是最後差一點沒有把規律推出來。

注意到以下幾個性質。第一，MI怎麼變換M永遠只能在第一位。第二，因為變換時只能在I和U之間變換，因此，除了第一個是M以外，後面如果有字符串不是U、I以內的話永遠不可能變換得到。第三，U可以看成是3個I，無論是I先變換成U再操作還是轉化成一定數量的I，最後再准換成一定數量的U即可，因此將所有的字母用I作為一般等價物進行交換即可。

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

int main()
{
	int testcase;
	cin>>testcase;
	while(testcase--)
	{
		string p="MI";
		int counti=1,countu=0,counti2=0,countu2=0,cm=0,pos=0;
		string tar;
		cin>>tar;
		for(int i=0;i<tar.length();i++)
		{
			
			if(tar[i]=='M')
			{
				cm++;
			}
				
			if(tar[i]=='I')
			{
				counti2++;
			}
				
			if(tar[i]=='U')
			{
				countu2++;
			}
				
		}
		
		if( cm==1 && tar[0]=='M'&& (((countu2*3+counti2)%2==0 && (countu2*3+counti2)%3!=0)||(countu2*3+counti2)==1))
		{
			pos=1;
		}
		else
		{
			pos=0;
		}
		
	
		if(pos==0)
		{
			cout<<"No"<<endl;
		}
		else if(pos==1)
			cout<<"Yes"<<endl;
		
		
	}
	
	return 0;
}