Difference between revisions of "Training 5: Dynamic Programming"

From EOJ Wiki
Jump to navigation Jump to search
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
== Problem A ==
 
== Problem A ==
  
Unsolved.
+
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 ==
  
Unsolved.
+
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 17: Line 39:
 
题意:给定一个 $n$ $(1 \le n \le 16)$ 个点,有重边且每条边都不一样的无向图,求联通无重边子图的个数。
 
题意:给定一个 $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\})$ 就是答案。
+
题解:令 $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 ==

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.