二进制枚举
用二进制枚举的方法解决的题目。
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒两斗。他边走边唱：
- 无事街上走，提壶去打酒。
- 逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店 5 次，遇到花 10 次，已知最后一次遇到的是花，他正好把酒喝光了。请你计算李白遇到店和花的次序，有多少种可能的方案。
二进制枚举是一种写起来非常简洁的解法。我们已知遇店 5 次，遇花 10次，并且最后一次遇到花，正好把酒喝光。那么我们可以把店作为二进制中的 1，把花作为二进制中的 0，因为已经确定最后一次遇到的是花，所以我们需要判断枚举的结果是否刚好有 5 个 1 和 9 个 0。那么我们就枚举出 14 位二进制的所有可能并加以判断即可，判断思路为判断二进制是否有 9 个 0，5 个 1，并且最终酒刚好剩 1 斗。
int ans = 0;
for (int i = 0; i < (1<<14); ++i) {
int tot_1 = 0;
int tot_0 = 0;
int num = 2;
for (int j = 0; j < 14; ++j) {
if (i&(1 << j)) { // 这里判断二进制 i 从右数第 j + 1 位是否为 1
tot_1++;
num = num * 2;
} else {
tot_0++;
num = num - 1;
}
}
if (tot_1 == 5 && tot_0 == 9 && num == 1) {
++ans; // 记录合法方案数
}
}