为了证明 leetcode 的 hard 题完全不 hard，想要抨击唯 leetcode 是论的思想，昨天给可靠大先辈讲子集枚举DP的时候随便找了道 leetcode 的题，今天随手写一发。
p.s. leetcode 不用 stdin / stdout 是什么傻逼 OJ （暴论）
Leetcode 600 不含连续1的非负整数
题面
给定一个正整数n，找出小于或等于n的非负整数中，其二进制表示不包含连续的1的个数。
示例 1:
输入: 5
输出: 5
解释:
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。说明: 1 <= n <= 1e9
题解
好的，看了这道题，由于我日常做法剑走偏锋，从来不按规矩正常做，所以就定义了一个恶臭 DP：
$$
f[i, 0] = f[i - 1, 0] + f[i - 1, 1]
$$
$$
f[i, 1] = f[i - 1, 0]
$$
$$
f[0, 0] = f[0, 1] = 1
$$
让我来解释一下上面这个方程: $f[i, 0]$ 表示一个长度为 $i$ 的二进制串，最高位为 $0$，按照题目说的不含连续1的数的方案数。$f[i, 1]$ 就是上面这句话除了最高位是 $1$。
注意：为了写代码方便，我代码中好像 $f[i, 0]$ 代表的是长度为 $i + 1$，因为这样第零位就是权为 $2^0$ 的那位。嘛...无所谓，怎么方便怎么来。下面的解释中都会按照长度是 $i + 1$来。
我觉得转移方程非常生动形象，无需解释，那么我们就来看一下答案统计。
由于答案是要小于等于某个数，无疑不能直接得到。但是，这并没有个关系，我们可以稍稍 hack 一下。我们用下面的两个二进制串举例，分别代表两种情况：
$$
100101000101
$$
$$
100111011011
$$
我直接说吧，他们的区别就是其中有没有连续的 1，先看上面这种没有连续的 1 的
$$
100101000101
$$
我们可以拆分为如下：
$$
\begin{aligned}
&000000000000 \sim 100000000000 - 1 = 011111111111 \\
&100000000000 \sim 100100000000 - 1 = 100011111111 \\
&100100000000 \sim 100101000000 - 1 = 100100111111 \\
&100101000000 \sim 100101000100 - 1 = 100101000011 \\
&100101000100 \sim 100101000101 \\
\end{aligned}
$$
可以发现，从上至下，方案书分别为：
$$
f[10, 0], f[8, 0], f[6, 0], f[2, 0], f[0, 0] + 1
$$
除了最后一个有$+1$，其他都是最低的1的位置$n$的$f[n, 0]$。
所以我们就能很轻松地进行答案统计：
$$
\text {ans} = 1 + \sum _ {0 \leq k < |D|} f[d[k], 0]
$$
其中，$D$表示所有数位是1的位数的集合。
再看有连续的 1 的情况：
$$
100111011011
$$
当我们想要如法炮制的时候会发现：
$$
\begin{aligned}
&000000000000 \sim 100000000000 - 1 = 011111111111 \\
&100000000000 \sim 100100000000 - 1 = 100011111111 \\
&100100000000 \sim 100110000000 - 1 = 100101111111 \\
&\color{red}{100110000000 \sim 100111000000 - 1 = 100110111111}
\end{aligned}
$$
最后一行就出现了问题。这个区间出现了重复的 1。然而！这并没有什么大不了的，这反而更加简单了，因为它直接退化了。因为我们根本不可能达到最大数 $100111011011$，相反，我们最大可以达到的只有：
$$
1001011111111
$$
因为我们是从高位往低位考察的，所以这个时候，我们只需要加上那个 $f[i, 0]$ 然后直接退出循环就行，省时省力，判断条件即为这一位和上一位是否都是 1.
下面是正常的代码：
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 35;
int d[maxn], dc;
ll a, f[maxn][2];
int main() {
cin >> a;
while (a > 0) {
d[dc ++] = a & 1;
a >>= 1;
}
f[0][1] = 1;
f[0][0] = 1;
for (int i = 1; i < dc + 2; i ++) {
f[i][1] = f[i - 1][0];
f[i][0] = f[i - 1][1] + f[i - 1][0];
}
ll ans = 0;
int last = dc - 1;
bool flag = false;
ans += f[last][0];
for (int i = dc - 2; i >= 0; i --) {
if (d[i]) {
ans += f[i][0];
if (i == last - 1) {
flag = true;
break;
}
else last = i;
}
}
if (!flag) ans ++;
cout << ans << endl;
return 0;
}下面是恶臭 leetcode 的代码：
const int maxn = 35;
class Solution {
public:
int d[maxn], dc = 0;
int f[maxn][2];
int findIntegers(int n) {
while (n > 0) {
d[dc ++] = n & 1;
n >>= 1;
}
f[0][1] = 1;
f[0][0] = 1;
for (int i = 1; i < dc + 2; i ++) {
f[i][1] = f[i - 1][0];
f[i][0] = f[i - 1][1] + f[i - 1][0];
}
int ans = 0;
int last = dc - 1;
bool flag = false;
ans += f[last][0];
for (int i = dc - 2; i >= 0; i --) {
if (d[i]) {
ans += f[i][0];
if (i == last - 1) {
flag = true;
break;
}
else last = i;
}
}
if (!flag) ans ++;
return ans;
}
};测试传送门：https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones/
