MU Puzzle

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1997 Accepted Submission(s): 787

Problem Description

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⁶.

Output

n lines, each line is 'Yes' or 'No'.

Sample Input

2
MI
MU

Sample Output

Yes
No

Source

2013 Multi-University Training Contest 6

代码写得好丑，都要丑哭了T T

U->3I, cnt/2 % 3 == 1 || cnt/2%3 == 2即可。

//2017-08-03

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = ;

char str[N];

int main()

{

    int T;

    scanf("%d", &T);

    while (T--)

    {

        scanf("%s", str);

        int cnt = ;

        bool fg = ;

        if (str[] == 'M')

        {

            for (int j = ; j < strlen(str); j++)

            {

                if (str[j] == 'I')

                    cnt++;

                else if (str[j] == 'U')

                    cnt += ;

                else if(str[j] == 'M')fg = ;

            }

        }else{

            printf("No\n");

            continue;

        }

        if(fg == ){

            printf("No\n");

            continue;

        }

        if (cnt <= )

        {

            if (cnt ==  || cnt == )

                fg = ;

            else

                fg = ;

        }

        else

        {

            if (cnt %  == )

                fg = ;

            else

            {

                cnt /= ;

                if (cnt %  ==  || cnt %  == )

                    fg = ;

                else

                    fg = ;

            }

        }

        if (fg)

            printf("Yes\n");

        else

            printf("No\n");

    }

    return ;

}

巴特西

HDU4662(SummerTrainingDay03-B)