HDU 4662 MU Puzzle 简单找规律

没有任何变换（III变U和删UU操作）之前，I 的个数一定是2^x个（也就是2的整数次幂）

若仅考虑III变U，那么设U的个数为k，I 的个数变为2^x-3*k

再加上删除UU操作，假设我们删除了2*n个U，设实际U的个数为cntU, 则k=cntU+2*n

设 I 的实际个数为cntI，cntI = 2^x - 3*(cntU+2*n), n有解的情况为：

( 2^x - 3*cntU - cntI ) % 6 == 0

只要找到一个x满足这个条件即可，不过要注意( 2^x - 3*cntU - cntI )>=0，因为 -6%6 = 0，之前没有判断这里，WA的很惨……

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #define LL long long int
 5 
 6 using namespace std;
 7 
 8 const int MAXN = 1000010;
 9 
10 LL cnt[30];
11 char str[MAXN];
12 LL bit[60];
13 
14 bool check()
15 {
16     LL I = cnt[ 'I' - 'A' ];
17     LL U = cnt[ 'U' - 'A' ];
18 
19     for ( int i = 0; i < 60; ++i )
20     {
21         if ( bit[i] - 3 * U - I >= 0 )
22         {
23             if ( ( bit[i] - 3 * U - I ) % 6 == 0 )
24                 return true;
25         }
26     }
27     return false;
28 }
29 
30 void init()
31 {
32     bit[0] = 1;
33     for ( int i = 1; i < 60; ++i )
34         bit[i] = ( bit[i - 1] << 1 );
35     return;
36 }
37 
38 int main()
39 {
40     init();
41     int T;
42     scanf( "%d", &T );
43     while ( T-- )
44     {
45         scanf( "%s", str );
46         int len = strlen(str);
47         memset( cnt, 0, sizeof(cnt) );
48         for ( int i = 0; i < len; ++i )
49             ++cnt[ str[i] - 'A' ];
50         if ( str[0] != 'M' || cnt[ 'M' - 'A' ] != 1 )
51         {
52             puts("No");
53             continue;
54         }
55         if ( check() ) puts("Yes");
56         else puts("No");
57     }
58     return 0;
59 }