ThinkofBlank

题解

未归档(4) 论文(10) 题单(1)

/ 注册

全部文章 / 题解（共16篇）

牛客算法周周练2 B Music Problem 题解

转化题意：给你n个数，问你是否能选出若干个数使得数字的和为3600的倍数（至少选一个）一开始，我打的01背包，dp[i]表示和模3600为i的方案数一开始，dp[0]为1，不难发现，若dp完后，dp[0]>1的话，就表示存在和为3600，不过，我们计算下复杂度：很明显，对于此题是过不...

优化题解动态规划

2020-04-15

7 1100

黑白树题解

一道贪心题~ 首先，我们将所有点分为已被覆盖点和未被覆盖点。那么首先，因为叶子节点是必选的，所以我们先将叶子节点选中，然后，就会产生若干被覆盖点，然后，由于选了一个点后，会导致这个点到根（1号点）的路径上的若干点被覆盖，所以，如果是在同一个祖先关系的链上的话，我们发现，我们可以贪...

题解动态规划

2020-04-14

0 716

Treepath 题解

一道简单的树形dp~ 求路径长度为偶数的路径数量，我们可以转化为求路径长度模2等于0的路径数量，这样就好做了~ 我们设表示i的子树中，到i的路径长度模2等于0的路径数量同理，就是模2等于1的路径数量了~ 我们想想转移：我们用的一个儿子来...

题解动态规划

2020-04-14

1 884

NC201400 树学题解

一.题解这道题又是一道换根dp板子题，代码结构与 Accumulation Degree 这道题基本一致，唯一不同的就是转移了【不过转移的时候，因为方程的原因不需要特殊考虑叶节点】我们先套路的设表示以为根的子树中，所有点的深度和，现在，我们来想想转移。我们发现，如...

题解动态规划

2020-04-13

4 647

[Accumulation Degree]题解

换根dp板子题，首先，我们要想想如果根为1时，1的答案我们设表示以为根子树的中，若有无限流量，i点能往下流的最大流量。我们不难推出式子意义就是，我们知道一个儿子v可以向下流的最大流量是,我们最多可以向儿子v流的流量，所以我们最多向该儿子流的流量，所有儿子的这个值的和就是了特别的,若i是叶子的...

题解动态规划

2020-04-13

2 827

题解 P3423 POI2005BAN-Bank Notes

本题有两个问，第一个是求最少硬币数，第二个则是求方案(翻译竟然没写。。。)。首先，我们来解决第一问。我们可以很容易想出，这是一个dp，我们设dp[i]表示凑出面值i最少需要多少个硬币，然后打个多重背包就好了。。。于是你就T了。。。对于多重背包，我们通常使用一种手段:二进制拆分...

题解优化动态规划

2019-01-21

0 562