memset0 发布的文章

给定一个无向带权图,边权只有 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

首先可以发现,最后的结果一定是所有点 [1, n)n 连边。对于给定的图,其中已经有若干条从 n 连到一些其他点的边,通过这些边可以将原来的图分裂成若干个区间。对于一个区间 [l, r] ,仅存在边 l \leftrightarrow nr \leftrightarrow n,对于所有 i \in (l, r) 不存在 i \leftrightarrow n。显然对于 r - l > 1 的情况,我们一定可以在 (l, r) 的范围内找到一个点 u,使得 l \leftrightarrow uu \leftrightarrow r,从而将这个区间分裂为两个更小的区间 [l, u][u, r]

显然每做一次树上操作,一定会多一个点与 n 连边,显然这样做是最优的。考虑如何统计方案数:相当于每棵子树的根节点一定要在选择其子树前被选择;考虑对于子树根节点的选择序列,首位一定是根节点,后面部分即将两棵子树的序列归并起来的值,即 \displaystyle \frac {(\operatorname{size}(lc) + \operatorname{size}(rc))!} {\operatorname{size}(lc)! \cdot \operatorname{size}(rc)!} 。最后的答案即若干棵子树合并起来的值。

考虑修改操作,我们依然可以在树上方便的维护。对于一次修改 (a, c) ,我们可以方便地求出 (b, d),然后根据 d 分类讨论。

READ MORE

要求维护一棵树,支持:

  • 给定 x, y, w,其中 w \in \{-1, 1\},将 xy 链上所有点权加上 w
  • 给定 x, y,查询 xy 的链上点权大于 0 的点的个数
  • 给定 x,查询 x 的子树内点权大于 0 的点的个数

n \leq 100000,时限 2s 。

READ MORE

被 mwh 嘲讽:「你会 SAM 吗,你不是什么题都写 SA 的吗」 于是自己想出来了这题

考虑根号分治,对于一组查询 (l, r, k) ,我们先将其拆成 (1, r, k) - (1, l - 1, k)

length[k] > \sqrt n 考虑这样的 k 不会超过 \sqrt n 个,对于每个都在 SAM 上暴力 DFS 统计出每个形如 (1, i, k), i \in [1, n] 的答案,时间复杂度 O(n \sqrt n)

length[k] \leq \sqrt n 考虑先把所有 (1, i, k) 按照 i 从小到大排序。ij 产生贡献当且仅当 i 在 SAM 上的结束节点时 j 在 SAM 上某个节点的祖先。考虑扫描线,每次插入一个串就将其子树增加 1 ,每查询一个串就暴力遍历在 SAM 上的每个点查询,由于串的长度 \leq \sqrt n ,所以单个询问最多查询 \sqrt n 次。

如果使用线段树状物来维护子树的修改,时间复杂度是 O(n \sqrt n \log n) 的。考虑到修改只有 O(n) 次而询问有 O(n \sqrt n) 次,可以考虑使用 O(\sqrt n) 修改,O(1) 查询的分块来解决。

READ MORE

还记得去年去打这个比赛的时候是人生第一次 ACM ... 那是还是普及选手,被 mwh 和 wxw 爆踩。

时间过的好快啊,没想到转眼又是一年过去了诶 ... 仿佛去年来的时候,记忆还是那么的清晰呢 ...

那么 ... 按照惯例,来写流水账了~

READ MORE