D - MU Puzzle（数学题）

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

题意：判断给定的字符串能否由MI通过3种规则转换而来。

题解：通过对3种规则的联系，发现全部U可以转换为I，即每个U换3个I。

思路：把全部的U换成I，看I的个数是否为2的幂，由规则2可以知 I 的个数可以减6再判断是不是2的幂。

坑点：1.要判断M是不只有是一个

           2.要判断M是不是在第一位

           3.要注意MI这种要单独判断，且 I 的数量减6之后不能把I=1的情况算进去，要单独考虑

技巧：判断2的幂的简单写法：

bool isPowerOf2(int n){

         if(n <= 0) return false;

         else return (n & (n-1)) == 0;

}

贴代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
bool isPowerOf2(int n){
    if(n <= 0){
        return false;
    }
    return(n & (n-1)) == 0;
}
int a[1000005];
char s[1000005];
int main()
{

    int n;
    cin>>n;
    while(n--){
        cin>>s;
        int len = strlen(s);
        int m = 0,u = 0,i = 0;
        if(s[0] != 'M') {cout<<"No"<<endl;continue;}
        for(int k = 0;k < len;k++){
            if(s[k] == 'M') m++;
            else if(s[k] == 'U') u++;
            else if(s[k] == 'I') i++;
        }
        if(m > 1) {cout<<"No"<<endl;continue;}
        if(u==0 && i==1) {cout<<"Yes"<<endl;continue;}
        i += u*3;
        bool flag = true;
        while(i > 1){
            if(isPowerOf2(i)) {cout<<"Yes"<<endl;flag = false;break;}
            else i-=6;
        }
        if(flag) cout<<"No"<<endl;
    }
    return 0;
}