AcWing 339 .圆形数字

大型补档计划

设 $f[i][j]$ 表示二进制下，数字有 $i$ 位， $0$ 的个数 - $1$ 的个数 $=$ $j$ 的方案数

$f[0][0] = 1;$

填一个 $0$

$f[i + 1][j + 1] += f[i][j]$

填一个 $1$

$f[i + 1][j - 1] += f[i][j]$

考虑到负下标越界，需要加偏移量

然后数位 dp 的细节蛮多的，比如第一位如果选 0 的话得特判，因为dp包括了前导0在内加入计算，所以得额外处理一个 $g[i]$ 表示一共 $ <= i$ 位，符合条件的个数。

#include <cstdio>

#include <iostream>

using namespace std;

const int N = 31, D = 30;

int a, b, d[N];

int f[N][N << 1], g[N];

void init() {

	f[0][D] = 1;

	for (int i = 0; i + 1 < N; i++) {

		for (int j = 0; j <= D * 2; j++) {

			if (!f[i][j]) continue;

			if (j < D * 2) f[i + 1][j + 1] += f[i][j];

			if (j) f[i + 1][j - 1] += f[i][j];

		}

	}

	g[0] = g[1] = 1;

	for (int i = 2; i < N; i++) {

		g[i] = g[i - 1];

		for (int j = D + 1; j <= D * 2; j++) g[i] += f[i - 1][j];

	}

}

int solve(int x) {

    if (x == 0) return 1;

    int n;

    for (int i = N - 1; ~i; i--)

        if (x >> i & 1) { n = i; break; }

    for (int i = 0; i <= n; i++) d[i] = x >> i & 1;

    int p = 0, res = 0;

    // p：目前 0 的个数 - 1 的个数

    for (int i = n; ~i; i--) {

        // 有 i + 1 位

        if (d[i]) {

        	if (i == n) res += g[i];

            else for (int j = D - (p + 1); j <= D * 2; j++) res += f[i][j];

            p--;

        } else p++;

        if (i == 0 && p >= 0) res++;

    }

    return res;

}

int main() {

	init();

	scanf("%d%d", &a, &b);

	printf("%d\n", solve(b) - solve(a - 1));

}

巴特西

AcWing 339 .圆形数字

最新文章

热门文章