分类 题解 下的文章

给定 n 个节点的树,每个点有个权值 a_i,保证 \{a_{1 \cdots n}\} 是一个 1n 的排列,求:

\frac 1 {n(n-1)} \sum_{i=1}^n \sum_{j=1}^n \varphi(a_i \times a_j) \times \operatorname{dist}(i, j)

READ MORE

一道非常有意思的(动态)DP 题。

讲道理的我考场上是会 70 分的但是由于 T1 傻逼了太久没调出来(报警了)

假设不修改的情况下答案为 W ,叶子节点的个数为 m,我们把总共的 2^m - 1 种选法分两种情况讨论:

  • W 被选中,这样的情况一共有 2^{m-1} 种,可见只要花费 1 的代价一定可以使根节点的值发生改变,下面不再讨论;
  • W 未被选中,这样的情况一共有 2^{m - 1} - 1 种,我们可以考虑 DP 解决。枚举当前的 C,求出所有花费代价 \leq C 的方案数,显然如果我们可以求得对于 C \in [L - 1, R],差分后就可得到答案数组。

READ MORE

显然要把每个数分解质因数,我们根据质因数与 L = \sqrt{500} \approx 22 的大小分类讨论。

给每个小于 L 的数状压,由于只需要知道是否有这个质因子而不关心质因子的大小,而小于 L 的质数又只有 2,3,5,7,11,13,17,198 个,可以用一个 2^8 的数来表示。

给每个大于 L 的数开个桶,同一个桶里的数要么被 G 选要么被 W 选要么不选。桶里面放这个数小于 L 的因子状压完的值。

dp[i][S][T] 表示枚举到第 i 个桶,G 选择的质因子的表示为 S,W 选择的质因子的表示为 T 的方案数。f[i][S][T] 表示把第 i 个桶分配为只能由 G 取,g[i][S][T] 表示把第 i 个桶分配为只能由 W 取。注意处理双方都没取的情况,即 dp[i][S][T] = f[i][S][T] + g[i][S][T] - dp[i - 1][S][T]

因为总共只有 n \leq 500 个数,可以暴力的转移。实现中,第一维可以滚动掉,总时间复杂度 \mathcal O(n \times 2^{16})

READ MORE

可以发现大部分操作都是整体操作我们可以打全局 Lazy Tag。对于单点操作我们可以开 std::map 或哈希,但实测 std::mapstd::unordered_map、暴力哈希都过不去,最后只能写个哈希挂链表才卡进了 ......

需要注意几个细节:

  1. 如果需要乘以 0 的操作,那么打成 Lazy Tag 就会比较难维护,可以转化为全局赋 0 的操作。
  2. 读入的时候注意取模,虽然不注意这个你样例都过不去 ......

另外不要像我这个傻逼一样开着文件交了 N 多发 ...

READ MORE

给定一个无向带权图,边权只有 A, B 两种,对于每个点 p \in [1, n] 求出 1 \rightarrow p 所有最小生成树中的最短距离。N \leq 70, M \leq 200

READ MORE

胡一个比 Sooke 垃圾的多两只 \log 做法。

将树树剖,这样的话一条链就可以被分解为 \log n 个区间。如果对每个点开一棵线段树,相当于我们要给这条路径上每个点的线段树都修改上这 \log n 个区间。可以用标记永久化的线段树来完成修改,树上差分 + 线段树合并来完成链上加。

然鹅考场上写完暴力就只有不到 10 分钟了,这么清真的做法竟然没写,报警了 ......

READ MORE

给定麻将的权值大小 n 和默认的 13 张手牌,求期望意义下的最小胡牌巡目数。

一道有意思的 DP 套 DP。发现如果我们可以知道 i 步后还未胡牌的方案数,就可以算出期望最小胡牌巡目数。

考虑一个判断牌是否可以胡的 DP:用 f[i][j][k][0/1] 表示对于权值 1 ~ i,预留了 j(i-1)iki,是否预留了一个对子的最大面子数。注意这样做是没法处理七对子的,但我们可以稍后特判。

显然,i 是多少与 DP 的转移没有关系,考虑建出一个自动机来维护转移。在自动机的节点上同时记录一下之前的牌可以凑出几个对子(注意不是预留)。显然一个节点是胡的当且仅当存在的对子数大于 7 或预留了一个对子且面子数大于等于 4。显然这个转移中会有大量重复节点,将他们压掉之后自动机上只有 2092 个点。

最后在自动机上 DP ,用 f[i][j][k] 表示当前枚举到权值为 i 的牌,到达自动机的 j 号点,其中自摸了 k 张牌的方案数。实现时可以滚动掉一维。

总时间复杂度 \mathcal O(n^2 \times K) 。其中 K = 2092

READ MORE