Asahi 的博客

一道练习点分治的题。 对于每一个点进行一遍 Dijkstra 是不可接受的，考虑点分治处理。 我们按照点分治的方式递归处理一个询问，假设当前递归到的分治中心是 $c$，询问的两点是 $u,v$，那么我们就要为最短路径分类。所有的最短路径可以分为三类： $\text{(A).}$ $z$ 的最短路经过 $c$。以分治中心 $c$ 为起点跑 Dijkstra，计算到 $c$ 到分治连通块内所有节点的最短路，那么此时 $d(u,v)=d(c,u)+d(c,v)$。 $\text{(B).}$ $u,v$ 在分治连通块的不同子树内且最短路不经过 $c$。这是最短路必定经过外环边，若子树个数为 $s$，外环边最多有 $s$ 条，对于每一条边，我们任取其一端点 $p$ ，计算 $p$ 到分治连通块内所有节点的最短路，那么此时有 $$ d(u,v)=\min_{i=1}^{s}\left(d(p_i,u)+d(p_i,v)\right) $$ $\text{(C).}$ $u,v$ 在分治连通块的同一子树内且最短路不经过 $c$。若最短路经过外环边，问题 $...

根据每个数被删除的轮次，我们可以得知或构造出数之间大小关系的约束。若有向边 $u\to v$ 表示 $u>v$，那么最终构成的约束图一定是 DAG，按照这幅图的拓扑序由 $n$ 向 $1$ 分配数的大小便是一组合法解。 考虑构造约束图。当前进行到第 $i$ 轮，当前还未被淘汰掉的点有 $u_1,u_2,\dots,u_k$，这里考虑进行到偶数轮，奇数轮是这种情况的对称。如果点 $u_i$ 在当前论中没被淘汰，那么一定有 $u_i>u_{i-1}$ 且 $u_i>u_{i+1}$，所以连接 $u_i\to u_{i-1}$ 和 $u_i\to u_{i+1}$。如果点 $u_i$ 在当前论中被淘汰了，若其左右没被淘汰，那么大小关系一定是确定的，不用考虑。如果有一个连通块 $u_l,u_{l+1}，\dots,u_r$，所有的点在这一轮中都是要淘汰的，那么就需要手动确定一组大小关系来满足条件，连通块内的点只能全部用 $<$ 或 $>$ 连接。若 $u_l=u_1$，那么只能有 $u_l<u_{l+1}<\dots<u_r$，否...

感觉这是一个很聪明的 DP 套 DP 啊。 首先我们考虑有一个确定的序列 $X$，其是否能与序列 $A$ 通过一样的按法按出来的 DP 怎么做？定义两个序列能通过一样的按法为两个序列是否匹配，那么我们用 $f_i$ 表示 $A$ 与 $X$ 的前 $i$ 项是否匹配，转移很简单，我们判断最后 $1/2/4$ 位是否能匹配，与之前的答案相拼即可。 下面考虑设计状态。一个数的匹配状态显然最多只和前面三个数是什么有关，所以我们定义 $F_{i,a,b,c,p_1,p_2,p_3,p_4}$ 表示倒数的三个数分别是 $a,b,c$ 且倒数的四个位置的 $f$ 值分别是 $p_1,p_2,p_3,p_4$ 的方案数。对于 $F_i$ 来说，我们枚举第 $i+1$ 个数是什么，并判断 $[i-2,i+1]$ 或 $[i,i+1]$ 或 $i+1$ 这几个区间能否匹配且前面的那一部分是否匹配来决定新的 $p_4$ 的值。这样转移我们考虑的是每一个新数的值是什么，显然这样计数是不重不漏的。 具体地，转移显然是由 $F_{i,a,b,c,p_1,p_2,p_3,p_4}$ 向 ...

感觉这个题的状态定义挺有 LIS 的套路的。感觉这个题可以用最长上升子序列的那种方法去定义状态去做，但是我用了另一种转化方式。 相对于普通的 LIS 计数，我们不仅需要考虑 LIS 的长度，还需要让护卫的编号（以下定义为“关键数字”）在原序列中单调递增地出现。如何根据这两个限制来定义状态呢？ 有一种求 LIS 的方式：定义一个集合 $S$，初始时 $S=\varnothing$，对于每一个 $a_i$，如果 $S$ 中存在最小的 $x$ 使得 $x>a_i$，那么删去 $x$ 加入 $a_i$，否则直接加入 $a_i$，最终 $|S|$ 即为 LIS。 我们可以根据这种方式设计 dp 状态。定义 $dp_{S,T}$ 表示当前已经考虑了 $S$ 中的数，在集合中的数有 $T$，的方案数。这样定义状态数时我们可以用 $|T|$ 限制 LIS 的长度。在转移的时候，我们统计一下 $S$ 中出现了几个关键数字，在加入新的数字的时候判断一下是否是关键数字，如果是的话只能加入第一个没出现的，这样就能考虑到关键数字顺序的限制。 下面分析时间复杂度。由于 $T\subseteq...

一道简单的树形 dp 题。 思路由于题目让我们求在树的子图中最长的蜈蚣图的长度，所以容易想到要用树形 dp 解决。我们定义一个蜈蚣图的身体为其中间的链，腿为和中间链连接的两个点。对于一个身体上的点来说，腿与其有两种连接方式，一种是选取两个子节点作为腿，一种是选取一个子节点和父节点作为腿。设当前考虑的节点为 $u$，如果选择了 $fa_u$，那么蜈蚣的身体就不能再向 $fa_u$ 及其祖先转移。所以我们定义 $f_{u,0}$ 表示以 $u$ 为蜈蚣的身体上端点而且不选 $fa_u$ 最为腿的最大长度，而 $f_{u,1}$ 则是选 $fa_u$ 最为腿的最大长度。然而我们发现身体端点不一定所有身体节点的祖先，所以我们定义 $g_u$ 表示以 $u$ 为身体中点的最大长度。 下面我们考虑如何转移。 若 $v$ 是 $u$ 的儿子，我们定义最大的 $f_{v,0}$ 叫 $w_0$，次大的 $f_{v,0}$ 叫 $w_1$，其儿子个数为 $n_u$。那么有以下几种转移。 $$ f_{u,0}=\max(f_{u,0},w_0+1),n_u\geq3 $$ $$ f_{u,...

其实只进行一次连发的 $f_i$ 不用去 dp，直接二分一下就行，这样会运行得更快。 思路我们容易注意到，每进行完一次连发之后，两个炮都要重新进入一轮冷却，相当于我们面对的是一个血量更少的敌人，这构成了一个新的子问题。我们只需要考虑在打掉怪物多少血量的时候连发，可以让总时间最小。这显然是一个 dp 问题，定义 $f_i$ 表示只能连发一次并且打掉 $i$ 的血量所需要的最小时间，$g_i$ 表示连发多次并且打掉 $i$ 的血量所需要的最小时间。容易得到 dp 方程如下 ： $$ g_i = \min_{j < i}\lbrace g_j + f _{i - j}\rbrace $$ 对于 $f_i$ 我们二分枚举所需时间，这样更方便一些。 但是有一种情况，一个炮冷却时间特别长，所以连发不如单个打划算。我们在二分的时候把这种情况考虑一下就行。 代码1234567891011121314151617181920212223242526272829#define int long longconst int inf = 0x3f3f3f3f3f3f3f3fll;int ...

看到字符串匹配，我们就要往 AC 自动机上去想。我们根据 AC 自动机的性质，我们很容易得知在第 $i$ 位结尾的匹配有多少个，所以我们可以很轻松地得到一个文本串的前缀的匹配数。 因此，我们考虑：假设第 $i$ 个位置的匹配数是 $suc_i$，那么我们能不能把区间 $[l, r]$ 的匹配数转化成 $suc_r - suc_l$ 这样的形式？大体可行，但是有一些情况我们需要处理。 我们询问的区间是 $[l, r]$，有一个匹配成功的字符串 $[x, y]$，如果 $1 \leq x < l \leq y \leq r $ 那么 $[x, y]$ 显然是被多算的。我们要排除这种影响。 定义 $sl_i$ 表示在第 $i$ 位结尾的所有匹配中的起始点（这个值可以用 fail 树随便维护一下），如果 $sl_i < l$，那么存在多算的匹配。如果我们找到 $[l, r]$ 中最大的使得 $sl_i < l$ 的 $i$，记作 $m$，那么在第 $[m + 1, r]$ 位之间结尾的匹配一定不会多算，所以直接加上 $suc_r - suc_m$。$m$ 我们可以离线二...

这绝对是一个非常好的题，中午去吃一顿饭的功夫就想出来这个小巧思。 思路首先我们考虑按位或的性质。 假设有一个 0/1 数组。由性质得，如果一个区间只要存在 1，那么这个区间的贡献就是 1。定义 $f_i$ 表示以 $i$ 结尾的所有区间的贡献和，所以 $f_i$ 显然就是间 $[1,i]$ 中最后一个 1 出现的位置，答案就是 $\sum f_i$。回到原题，我们会很容易想到把每一个数拆位来计算贡献，对于每一位，从头到尾跑一遍。注意其实 $a_i$ 和 $f_i$ 其实没必要存下来，就可以省下来空间。时间复杂度 $O(n \log V)$，会拿到 30pts 的好成绩。 代码如下： 12345678910111213141516using namespace READ;int lst[70];ull ans;void solve() { int n; init(n); for (int i = 1; i <= n; i++) { ull x = read(); // Brute Force ...

思路一种 vector<int>, vector<int> 的 map 做法，代码稍长一些但是特别好想。 先考虑 $k = 1$ 时的做法，后面 $k$ 增大时在原基础上改动一点就可以了。 看到左右括号，我们容易想到遇到左括号加 $1$，右括号减 $1$，记第到 $i$ 个位置的前缀和为 $sum_i$。显然，区间 $[l,r]$ 若是合法的，必须满足以下条件： 左括号和右括号的数量相等。 在任何位置，前面的右括号个数不能超过左括号。 用数学的形式表达，就是： $sum_r - sum_{l-1} = 0$。 对于 $[l, r]$ 之间的任意一点 $i$，满足 $sum_i - sum_{l - 1} \geq 0$。 移项，得： $sum_r = sum_{l-1}$。 对于 $[l, r]$ 之间的任意一点 $i$，满足 $sum_i \geq sum_{l - 1}$。 我们分开考虑每个条件。 若假设 $l$ 为当前计算区间的左端点，那么若存在一点 $i$ 满足 $sum_i < sum_{l - 1...

思路首先我们根据贪心的策略，很容易想出来一定要把最上边的那一行和最左边的那一列全部连起来，剩下的点连向左边或者上边就可以了。$O(n ^ 2)$ 的暴力做法就是枚举每个点是连向左边还是上边，直接加上每个点的贡献就可以了。 对于 $O(n \log n)$ 的做法，我们就不能挨个考虑每个点连接的方向了。我们进而分析每个点连接的方向和数组 $a, b, c, d$ 的关系。 显然，我们选择连上面而不是左边时，满足： $$ a_{i - 1} + b_j < c_i + d_{j - 1} $$ 移项，得 $$ a_{i - 1} - c_i < d_{j - 1} - b_j $$ 即 $$ d_{j - 1} - b_j > a_{i - 1} - c_i $$ 而对于每一行来说，$a_{i - 1} - c_i$ 是固定不变的。所以我们可以预处理好 $d_{j - 1} - b_j$ 的值，记作 $diff$，每次在 $diff$ 上二分 $a_{i - 1} - c_i$ 的值，这个值右边的所有数就是连向上面的，左边的所有数就是连向左边的，进而我们可以求出连向...