数位DP

简介

常见技巧

按位考虑

参考题目

P3048 [USACO12FEB]Cow IDs S

https://www.luogu.com.cn/problem/P3048

题目描述

Being a secret computer geek, Farmer John labels all of his cows with binary numbers. However, he is a bit superstitious, and only labels cows with binary numbers that have exactly K "1" bits (1 <= K <= 10). The leading bit of each label is always a "1" bit, of course. FJ assigns labels in increasing numeric order, starting from the smallest possible valid label -- a K-bit number consisting of all "1" bits. Unfortunately, he loses track of his labeling and needs your help: please determine the Nth label he should assign (1 <= N <= 10^7).

FJ给他的奶牛用二进制进行编号，每个编号恰好包含K 个"1" (1 <= K <= 10)，且必须是1开头。FJ按升序编号，第一个编号是由K个"1"组成。

请问第N(1 <= N <= 10^7)个编号是什么。

输入格式

* Line 1: Two space-separated integers, N and K.

输出格式

样例 #1

样例输入 #1

7 3 

样例输出 #1

10110 

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, l;
ll C(int n, int m)
{
	ll re = 1;
	for (int i = 0; i < m; i++)
	{
		re = re * (n - i) / (i + 1);
	}
	return re;
}
int main()
{
	scanf("%d%d", &n, &m);
	while (C(l, m) < n)
	{
		l++;
	}
	for (int i = l - 1; i >= 0; i--)
	{
		if (n > C(i, m))
		{
			n -= C(i, m);
			m--;
			printf("1");
		}
		else
		{
			printf("0");
		}
	}
	printf("\n");
	return 0;
}

题解

101000
1 0
1? C(1, 0)
1?? C(2, 0)
1??? C(3, 0) + C(3, 1)
1???? C(4, 0) + C(4, 1)
100??? C(3, 0) + C(3, 1) + C(3, 2)
10100? C(1, 0) + C(1, 1)

P3048 [USACO12FEB]Cow IDs S

00111
01011
01101
01110
10011
10101
10110
11001
11010
11100

C(4, 3) = 4
C(5, 3) = 10

P6218 [USACO06NOV] Round Numbers S

https://www.luogu.com.cn/problem/P6218

题目描述

如果一个正整数的二进制表示中，$0$ 的数目不小于 $1$ 的数目，那么它就被称为「圆数」。

例如，$9$ 的二进制表示为 $1001$，其中有 $2$ 个 $0$ 与 $2$ 个 $1$。因此，$9$ 是一个「圆数」。

请你计算，区间 $[l,r]$ 中有多少个「圆数」。

输入格式

一行，两个整数 $l,r$。

输出格式

一行，一个整数，表示区间 $[l,r]$ 中「圆数」的个数。

样例 #1

样例输入 #1

2 12

样例输出 #1

6

提示

【数据范围】

对于 $100\%$ 的数据，$1\le l,r\le 2\times 10^9$。

---

【样例说明】

区间 $[2,12]$ 中共有 $6$ 个「圆数」，分别为 $2,4,8,9,10,12$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int l, r;
int c[33][33];
int S(int n, int m) // n个位置，选 <= m 个
{
	int re = 0;
	for (int i = 0; i <= m; i++)
	{
		re += c[n][i];
	}
	return re;
}
int F(int n) // < n
{
	int re = 0;
	for (int i = 1; n >> i; i++)
	{
		re += S(i-1, i/2-1);
	}
	bool v = false;
	int cnt = 0;
	for (int i = 31; i >= 0; i--)
	{
		if (n >> i & 1)
		{
			if (v)
			{
				re += S(i, (i - cnt + 1) >> 1);
			}
			cnt++;
			v = true;
		}
		else
		{
			if (v)
			{
				cnt--;
			}
		}
	}
	return re;
}
bool R(int x)
{
	int cnt = 0;
	for (int i = 0; x >> i; i++)
	{
		if (x >> i & 1)
		{
			cnt++;
		}
		else
		{
			cnt--;
		}
	}
	return cnt <= 0;
}
int G(int n)
{
	int re = 0;
	for (int i = 1; i < n; i++)
	{
		if (R(i))
		{
			re++;
		}
	}
	return re;
}
int main()
{
	for (int i = 0; i < 33; i++)
	{
		c[i][0] = 1;
		for (int j = 1; j <= i; j++)
		{
			c[i][j] = c[i-1][j-1] + c[i-1][j];
		}
	}
	scanf("%d%d", &l, &r);
	printf("%d\n", F(r + 1) - F(l));
	return 0;
}

题解

answer of [1, r] - answer of [1, l-1]
answer of [1, r+1) - answer of [1, l)

how many round numbers < 0b101010

P1246 编码

https://www.luogu.com.cn/problem/P1246

题目描述

编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数宇。

字母表中共有26个字母{a，b，…，z}，这些特殊的单词长度不超过6且字母按升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置。

例如：

a→1 b→2 z→26 ab→27 ac→28

你的任务就是对于所给的单词，求出它的编码。

输入格式

仅一行，被编码的单词。

输出格式

仅一行，对应的编码。如果单词不在字母表中，输出0。

样例 #1

样例输入 #1

ab

样例输出 #1

27

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, c[27][27];
char s[27];
int gao()
{
	int z = 0;
	for (int i = 0; i < n; i++)
	{
		z += c[26][i];
	}
	for (int i = 0; i < n; i++)
	{
		int p = i > 0 ? s[i - 1] + 1 : 'a';
		if (p > s[i])
		{
			return 0;
		}
		for (int j = p; j < s[i]; j++)
		{
			z += c['z' - j][n - i - 1];
		}
	}
	return z;
}
int main()
{
	for (int i = 0; i <= 26; i++)
	{
		c[i][0] = 1;
		for (int j = 1; j <= i; j++)
		{
			c[i][j] = c[i-1][j-1] + c[i-1][j];
		}
	}
	scanf("%s", s);
	n = strlen(s);
	printf("%d\n", gao());
	return 0;
}

题解

把空串看做0，相当于输入一个字符串S，问有多少个字符串比S小
比他小字符串T分为两大类情况
T的长度 小于 S的长度
T的长度 等于 S的长度 且 T字典序小于S

spoj TRIMOD2

spoj UNHAPPY