Difference between revisions of "Training 5: Dynamic Programming"
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...") |
|||
(6 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
− | + | == Problem A == | |
− | + | Unsolved. | |
− | + | == Problem B == | |
− | + | Unsolved. | |
− | + | == 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. |
Revision as of 10:33, 12 September 2019
Problem A
Unsolved.
Problem B
Unsolved.
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.