首页 > 代码库 > HDU 4317 位运算

HDU 4317 位运算

【题意】:

在一个常规的NIM游戏里,你可以在每堆石子拿走任意数量的石子,问求使先手必败的情况下拿走石子数量的最小值。

【知识点】:

位运算,DP

【题解】:

一道精致的位运算的好题目,细节有不少。

具体解释在代码内。

【代码】:

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 #include <cstdlib> 6 #include <climits> 7 #include <algorithm> 8  9 #define wh while10 #define sf scanf11 #define pf printf12 #define clr(abc,z) memset(abc,z,sizeof(abc))13 #define FOR0(i, n) for(int i = 0; i < n; i++)14 #define FOR1(i, n) for(int i = 1; i <= n; i++)15 16 using namespace std;17 18 const int maxb = 1 << 11;19 const int maxn = 25;20 21 int dp[maxn][maxb], s[maxn], a[maxn], t[maxb];22 int n;23 int getbit(int x){24     int ret = 0;25     wh(x){26         ret += (x & 1); x >>= 1;27     }28     return ret;29 }30 31 int main(){32     FOR0(i, maxb) t[i] = getbit(i);33     wh(sf("%d", &n) != EOF){34         FOR0(i, n) sf("%d", &a[i]);35         if(n < 2){36             puts("impossible"); continue;37         }38         int m, ans;39         clr(s, 0);40         FOR1(i, maxn - 1){41             FOR0(j, n)42                 if(a[j] & (1 << (i - 1))) s[i - 1] |= (1 << j);43             if(s[i - 1]) m = i + 1;44         }45         clr(dp, 0x3f); ans = dp[0][0]; dp[0][0] = 0;46         //dp[i][k]从右往左第i+1位通过第i位进位得到的1的状态情况47         FOR1(i, m){48             FOR0(j, (1 << n)){49                 if(dp[i - 1][j] < ans){50                     int tmp = j & s[i - 1]; //j代表进位后得到的位状况51                                             //s[i - 1]保存原本存在的当前位置的1的状况52                     for(int k = tmp; k < (1 << n); k++){53                         if(((k & tmp) == tmp)54                            //经过右边位置进位得到的状态存在与总状态中55                        && (((s[i - 1] ^ j) & (k ^ tmp)) == (k ^ tmp))56                            //未经进位得到的状态存在于右边位置中1状态子集内57                        && (((t[(s[i - 1] ^ j) ^ (k ^ tmp)] & 1) == 0) || t[(s[i - 1] ^ j) ^ (k ^ tmp)] < n))58                            //那些右边状态不进位加1的状态不能包含所有的159                             dp[i][k] = min(dp[i][k], dp[i - 1][j] + (t[k ^ tmp] + (t[(s[i - 1] ^ j) ^ (k ^ tmp)] & 1)) * (1 << (i - 1)));60                     }61                 }62             }63         }64         FOR0(i, (1 << n)){65             if((t[i] & 1) == 0)66                 ans = min(ans, dp[m][i]);67         }68         pf("%d\n", ans);69     }70     return 0;71 }
View Code

 

HDU 4317 位运算