题解 P3005 【[USACO10DEC]槽的游戏The Trough Game】
brealid
·
·
题解
什么是 C++ 的精髓？
- 是面向对象
- 是指针
- 是完善的各种库函数
那么我们今天的主角是：库函数 __builtin_popcount
读题 · 方法
初读题，看见 n\le20，你想起了什么？
我想起的是状态压缩。
这题的 n\le20 还让你想到了什么？
（所以从数据范围上可以容易猜出算法）
### Part 1 状态压缩
题目所给的形式很好进行状态压缩。
然后，为防各种换行的奇怪问题，我没有使用 ``getchar()``，而选用了这种读入方式：
```cpp
char str[20 + 7];
for (int i = 1; i <= m; i++) {
scanf("%s", str);
cnt[i] = read<int>();
for (int j = 0; j < n; j++)
if (str[j] & 1) type[i] |= (1 << j);
}
```
熟悉位运算的同学应该很容易看懂。
不熟悉的……右转百度搜索“状压DP”
### Part 2 模板函数 ``__builtin_popcount``
这个函数的作用，是计算出 ``__builtin_popcount(x)`` 中 ``x`` 在二进制下 ``1`` 的位数。
基层实现：将一个 ``unsigned int(32 bit)`` 拆成 4 个 ``8 bit`` 然后 $O(1)$ 查表（这个表大小为 $2^8$）
在本题中，``__builtin_popcount`` 有什么妙用？
#### Part 2.1 奇奇怪怪的位运算
首先假设现在状态枚举到了 $i$ （$i$ 经过二进制压缩），正在检验第 $j$ 条限制条件，该限制条件表示对于状态为 $type[j]$ 的情况，其中有 $cnt[j]$ 个槽装了草。
那么，有一个很妙的东西就出现了。
若 ``__builtin_popcount(i & type[j]) == cnt[j]`` 则该条限制条件得到满足。
这个东西很难用语言解释，意会即可。
## 代码
```
// 已省去不必要的代码
#include <需要的文件>
// read : 快读函数
// read<int> : 读入一个 int 型整数
#define bitCount(x) __builtin_popcount(x)
int n, m;
char str[27];
int type[107], cnt[107];
bool fail, succeeded = false;
int success_status;
int main()
{
n = read<int>();
m = read<int>();
for (int i = 1; i <= m; i++) {
scanf("%s", str);
cnt[i] = read<int>();
for (int j = 0; j < n; j++)
if (str[j] & 1) type[i] |= (1 << j);
}
for (int i = 0; i < (1 << n); i++) {
fail = false;
for (int j = 1; j <= m; j++) {
if (bitCount(i & type[j]) != cnt[j]) {
fail = true;
break;
}
}
if (!fail) {
if (succeeded) {
puts("NOT UNIQUE");
return 0;
}
succeeded = true;
success_status = i;
}
}
if (!succeeded) puts("IMPOSSIBLE");
else for (int i = 0; i < n; i++)
putchar((success_status & (1 << i)) ? '1' : '0');
putchar(10);
return 0;
}
```
最后说一句，实际上这个算法的复杂度 $\Theta(2^nm)≈10^8$ 是不太对的，正解可能更优秀。但是题目的特性注定这道题目不会跑满复杂度。
（尤指 $1\dots m$ 的枚举检验）
还有，``__builtin_popcount`` 的复杂度是 $O(1)$，但常数较大，大约为 $4$ 。
不过这个值还是比其他 STL 的常数要小得多了。