Difference between revisions of "Training 5: Dynamic Programming"
Xiejiadong (talk | contribs) |
|||
| (7 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
== Problem A == | == Problem A == | ||
| − | Solved by | + | Solved by Xiejiadong. |
| − | + | 题意：求区间 \([L,R]\) 内满足相邻两位的差 \(\ge 2\) 的数的个数。 | |
| + | |||
| + | 题解：这道题目的前导 \(0\) 有点难处理。 | ||
| + | |||
| + | \(f[i][j][k][m]\) 表示处理到第 \(i\) 位，第 \(i\) 位上的数为 \(j\) ，\(k=0/1\) 前 \(i\) 位是否于上限一致，\(m=0/1\) 是否有前导 \(0\) 。 | ||
| + | |||
| + | 直接转移可以得到区间 \([1,x]\) 的总数，查分并检验下限是否满足要求即可。 | ||
== Problem B == | == Problem B == | ||
| Line 9: | Line 15: | ||
Solved by Xiejiadong. | Solved by Xiejiadong. | ||
| − | + | 题意：在区间 \([a,b]\) 内所有满足偶数位上均为 \(d\) ，奇数位上均不为 \(d\) ，且是 \(m\) 的倍数的数的个数。 | |
| + | |||
| + | 题解： | ||
| + | |||
| + | 数位 dp。 | ||
| − | + | \(f[i][j][k]\) 表示处理到第 \(i\) 位，对 \(m\) 取余数的结果为 \(j\) ， \(k=0/1\) 表示前 \(i\) 位是否与上限相同的方案数。 | |
| − | + | 对于每一位的情况分为与上限相同的，转移 \([0,s[i]]\) 位；前 \(i\) 位小于上限的转移 \([0,9]\) ，依次处理余数转移即可。 | |
| − | + | 这样的话就能解决 \([1,s]\) 的个数问题了。 | |
| − | + | 对于区间 \([a,b]\) ，特判 \(a\) 的时候是否成立，作差分即可。 | |
== Problem C == | == Problem C == | ||
| Line 25: | Line 35: | ||
== Problem D == | == Problem D == | ||
| − | Solved by | + | Solved by Kilo_5723. |
| − | + | 题意：给定一个 $n$ $(1 \le n \le 16)$ 个点，有重边且每条边都不一样的无向图，求联通无重边子图的个数。 | |
| − | + | 题解：令 $S$ 是 $\{1,\dots,n\}$ 的子集，$cnt(S)$ 代表 $S$ 的子图数量，$ans(S)$ 代表 $S$ 的连通子图数量，$cnt(S)$ 可以通过枚举边计算，$ans(S)$ 可以枚举第一个点所在的极大连通块 dp 得到结果。按 $|S|$ 从小到大 dp，$ans(\{1,\dots,n\})$ 就是答案。 | |
| − | |||
| − | |||
== Problem E == | == Problem E == | ||
| Line 38: | Line 46: | ||
== Problem F == | == Problem F == | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Unsolved. | Unsolved. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Latest revision as of 12:18, 13 September 2019
Problem A
Solved by Xiejiadong.
题意：求区间 \([L,R]\) 内满足相邻两位的差 \(\ge 2\) 的数的个数。
题解：这道题目的前导 \(0\) 有点难处理。
\(f[i][j][k][m]\) 表示处理到第 \(i\) 位，第 \(i\) 位上的数为 \(j\) ，\(k=0/1\) 前 \(i\) 位是否于上限一致，\(m=0/1\) 是否有前导 \(0\) 。
直接转移可以得到区间 \([1,x]\) 的总数，查分并检验下限是否满足要求即可。
Problem B
Solved by Xiejiadong.
题意：在区间 \([a,b]\) 内所有满足偶数位上均为 \(d\) ，奇数位上均不为 \(d\) ，且是 \(m\) 的倍数的数的个数。
题解：
数位 dp。
\(f[i][j][k]\) 表示处理到第 \(i\) 位，对 \(m\) 取余数的结果为 \(j\) ， \(k=0/1\) 表示前 \(i\) 位是否与上限相同的方案数。
对于每一位的情况分为与上限相同的，转移 \([0,s[i]]\) 位；前 \(i\) 位小于上限的转移 \([0,9]\) ，依次处理余数转移即可。
这样的话就能解决 \([1,s]\) 的个数问题了。
对于区间 \([a,b]\) ，特判 \(a\) 的时候是否成立，作差分即可。
Problem C
Unsolved.
Problem D
Solved by Kilo_5723.
题意：给定一个 $n$ $(1 \le n \le 16)$ 个点，有重边且每条边都不一样的无向图，求联通无重边子图的个数。
题解：令 $S$ 是 $\{1,\dots,n\}$ 的子集，$cnt(S)$ 代表 $S$ 的子图数量，$ans(S)$ 代表 $S$ 的连通子图数量，$cnt(S)$ 可以通过枚举边计算，$ans(S)$ 可以枚举第一个点所在的极大连通块 dp 得到结果。按 $|S|$ 从小到大 dp，$ans(\{1,\dots,n\})$ 就是答案。
Problem E
Unsolved.
Problem F
Unsolved.