Difference between revisions of "Training 5: Dynamic Programming"

From EOJ Wiki
Jump to navigation Jump to search
(Created page with "=== Problem A === 题意: $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j)$ 题解: 原式=$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{i \times j}{gcd(i,j)} = \sum\l...")
 
 
(8 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
=== Problem A ===
+
== Problem A ==
  
−
题意: $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j)$
+
Solved by Xiejiadong.
  
−
题解: 原式=$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{i \times j}{gcd(i,j)} = \sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\frac{n}{k}}\sum\limits_{j=1}^{\frac{m}{k}}i \times j[gcd(i,j)=k]$ 然后莫比乌斯反演得$\sum\limits_{k=1}^{n}mu[i] \times (1+...+\frac{n}{k}) \times (1+...+\frac{m}{k})$ 然后数论分块求和
+
题意：求区间 \([L,R]\) 内满足相邻两位的差 \(\ge 2\) 的数的个数。
  
−
=== Problem B ===
+
题解：这道题目的前导 \(0\) 有点难处理。
  
−
题意: 求第$n$个不是完全平方数的正整数倍的数
+
\(f[i][j][k][m]\) 表示处理到第 \(i\) 位，第 \(i\) 位上的数为 \(j\) ，\(k=0/1\) 前 \(i\) 位是否于上限一致，\(m=0/1\) 是否有前导 \(0\) 。
  
−
题解: 考虑容斥求出$n$以内有多少是完全平方倍数，枚举平方因子$i$贡献为$mu[i] \times n/(i*i)$因此二分每趟是$O(sqrt(n))$的，复杂度绰绰有余。
+
直接转移可以得到区间 \([1,x]\) 的总数，查分并检验下限是否满足要求即可。
  
−
=== Problem C ===
+
== Problem B ==
  
−
题意: $\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\sum\limits_{k=1}^{min(i,j)}k[k | i, k | j且\sum k \le a]$
+
Solved by Xiejiadong.
  
−
题解:这道题想爆。$=\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\sum\limits_{k=1}^{min(i,j)}k[k | gcd(i,j)且\sum k \le a]$先考虑没有$\le a$的情况。$f(i)$表示$i$的因数和。$g(n)=\sum\limits_{n|d}mu[d/n] \cdot \frac{n}{d} \cdot \frac{m}{d}$表示$gcd(i,j)=n$的个数。原式=$\sum\limits_{i=1}^{n}f(i)g(i)=\sum\limits_{i=1}^{n}f(i)\sum\limits_{i|d}mu[d/i] \cdot \frac{n}{d} \frac{m}{d}=\sum\limits_{d=1}^{n}\frac{n}{d}\frac{m}{d}\sum\limits_{i|d}f(i)mu[d/i]$。为了数论分块搞这个式子我们需要$F(i)$的前缀和。记$F(i)=f*mu$。只有当$f(i) \le a$时对答案做出贡献。然后就是离线操作，每次把新符合条件的$f(i)$枚举倍数新加到维护$F(i)$前缀和的树状数组中，然后再数论分块求和。复杂度$O(sqrt{(n)}logn+nsqrt{(n)})$
+
题意：在区间 \([a,b]\) 内所有满足偶数位上均为 \(d\) ，奇数位上均不为 \(d\) ，且是 \(m\) 的倍数的数的个数。
  
 +
题解：
  
−
=== Problem D ===
+
数位 dp。
  
−
题意: 给出$a_i$求有多少$b_i \le a_i$使得任意区间$gcd \ge 2$
+
\(f[i][j][k]\) 表示处理到第 \(i\) 位，对 \(m\) 取余数的结果为 \(j\) ， \(k=0/1\) 表示前 \(i\) 位是否与上限相同的方案数。
  
−
题解:这道题当时多校补题的时候想爆。考虑容斥求出整个$gcd=k$的情况数$F(k)$，然后答案为$\sum\limits_{i=2}^{k}F(i)$。发现$G(k)=\prod\limits_{i=1}^{n}{a_i/k}$是容斥中对应$gcd>=k$的式子，且$k$包含奇数素因子为正，偶数为负，发现其和莫比乌斯函数刚好是相反关系。（个人理解莫比乌斯函数就是整除偏序上的容斥）。每一次计算都一个一个值算$G(k)$太蠢了。应该将$a_i$转换成$cnt[a_i]++$再使用前缀和，然后一段一段加，每段长度为$i$，这样相同段的$n/i$都是一样的。复杂度就是那个著名的级数$O(nlogn)$了。
+
对于每一位的情况分为与上限相同的，转移 \([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.

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.

Retrieved from "http://acm.ecnu.edu.cn/wiki/index.php?title=Training_5:_Dynamic_Programming&oldid=4728"