HDU 4662 MU Puzzle（找规律）

时间：2022-10-04 04:56:35

题意：问是否能把MI通过以下规则转换成给定的字符串s。

1.使M之后的任何字符串加倍（即，将Mx更改为Mxx）。 例如：MIU到MIUIU。
2.用U替换任何III。例如：MUIIIU至MUUU。
3.去掉任何UU。 例如：MUUU到MU。

分析：

1、MI的变换首先要复制I，可以复制为1,2,4,8,16,32，……（2的n次方）个。

2、由于可以用U替换任何III，所以将字符串s中所有的U变为I后，统计I的个数cnt。

3、由于可以去掉任何UU，所以转换成功必须满足cnt+6x==2的n次方。

4、通过找规律，发现当cnt为2,4,8,10,14,16,20,22,26,28,32,34,38……时满足方程，这些数的共同特点是能被2整除，不能被3整除。

5、当cnt为1时，即MI，也满足条件。

6、满足4、5的大前提是M是字符串的第一个字母，且仅有一个。

#pragma comment(linker, "/STACK:102400000, 102400000")

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define Min(a, b) ((a < b) ? a : b)

#define Max(a, b) ((a < b) ? b : a)

typedef long long ll;

typedef unsigned long long llu;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const ll LL_INF = 0x3f3f3f3f3f3f3f3f;

const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {, , -, , -, -, , };

const int dc[] = {-, , , , -, , -, };

const int MOD = 1e9 + ;

const double pi = acos(-1.0);

const double eps = 1e-;

const int MAXN = 1e6 + ;

const int MAXT =  + ;

using namespace std;

char s[MAXN];

int main(){

    int T;

    scanf("%d", &T);

    while(T--){

        scanf("%s", s);

        int len = strlen(s);

        int cnt = ;

        int m = ;//M的个数

        bool ok = true;

        for(int i = ; i < len; ++i){

            if(s[i] == 'I') ++cnt;

            else if(s[i] == 'U') cnt += ;

            else ++m;

        }

        if(s[] == 'M' && m ==  && (cnt ==  || (cnt %  ==  && cnt %  != )))

            printf("Yes\n");

        else printf("No\n");

    }

    return ;

}

相关文章