Revethere's Blog

Lunch Concert

题面

P9025 CCC2021 S3 Lunch Concert ( 圆身 Genshin )

有 $n$ 个人在一条线上 , 初始位置为 $p_i$ , 移动一个单位长度的代价为 $w_i$ . 选定一个点 $c$ , 产生的代价为 $\sum_i^n w_i \times \max{(\lvert c - p_i \rvert - d_i , 0)}$ . 最小化这个代价 .

解题思路

完全随机算法狂砍 80pts . 出题人大好人 ( 雾 .

把一个人转化为一个线段 $[p_i - d_i,p_i + d_i]$ , 若要移动则 $c < p_i - d_i$ 或 $c > p_i + d_i$ .

于是得到单峰函数 . 二 / 三分或者模拟退火就行 .

MEX vs MED

题面

CF1744F MEX vs MED ( 弄药 Arena )

给定一个序列 $a$ , 值域为 $[0,n - 1]$ , 下标范围为 $[1,n]$ . 求有多少区间 [l,r] 满足 $\operatorname{mex}(a_l,a_{l + 1}, \ldots ,a_{r - 1},a_r) \le \operatorname{med}(a_l,a_{l + 1}, \ldots ,a_{r - 1},a_r)$ ( 原题为 ( $\operatorname{mex}(a_l,a_{l + 1}, \ldots ,a_{r - 1},a_r) > \operatorname{med}(a_l,a_{l + 1}, \ldots ,a_{r - 1},a_r)$ ) .

$\operatorname{mex}(S)$ 为没有在 $S$ 中出现的最小非负整数 .

$\operatorname{med}(S)$ 为 $S$ 从小到大排序后 $S_{\left\lfloor{\frac{\lvert S \rvert + 1}{2}}\right\rfloor}$ 的值 .

解题思路

定义 $list_i$ 表示 $i$ 出现的位置 , 即 $list_{a_i} = i$ . 若区间 $[l,r]$ 的 $\operatorname{mex} = d$ , 则必有 $l \le \min_{i \le d} list_i $ 并且 $r \geq \max_{i \le d} list_i$ .

对于每个 $\operatorname{mex} = d$ 只需考虑长度为 $d \times 2$ 和 $d \times 2 - 1$ 的区间个数 , 长度为 $d \times 2 - 2$ 的区间一定在 $\operatorname{mex}$ 的值为 $d - 1$ 的时候统计过 .

复杂度 $O(n)$ .

PRE-Prefixuffix

题面

P3546 POI2012 PRE-Prefixuffix

对于两个串 $S$ , $T$ . 将 $S$ 的一个前缀移动到其末尾等于 $T$ , 则 $S$ 和 $T$ 循环相同 .

给定串 $S$ , 求最大的 $L$ ( $L \le \dfrac{n}{2}$ ) , $S$ 的 $L$ 前缀与 $S$ 的 $L$ 后缀是循环相同的 .

解题思路

一般考虑循环相同会复制串 $A$ 两边得到 $AA$ , 从中寻找串 $B$ . 不过这道题这样做复杂度爆炸 .

两个循环相同的串可以表示为 $AB$ , $BA$ . 则题目等价于把原串表示为 $ABSBA$ 的形式下最长的 $AB$ .

令 $B = a B^\prime c$ , 那么原串可写为 $A a B^\prime c S a B^\prime c A$ , 就可以分为 $A a \lvert B^\prime \rvert c S a \lvert B^\prime \rvert c A$ .

$f_i$ 表示 $A$ 取 $S_{[1 , i]}$ 时最长的 $B$ . ( $S_{[i + 1 , i + f_i]} = S_{[n - i - f_i , n - i - 1]}$ ) . 由此可知 : $f_{i + 1} \ge f_i - 2$ , 存在单调性 . 初值为 $f_{\lfloor \frac{n}{2} \rfloor}$ , 考虑从 $f_{i + 1}$ 往回计算 $f_i$ . $f_i \le f_{i + 1} + 2$ . 统计最大值即可 . 复杂度 $O(n)$ .

骰子游戏-Dice

题面

构造 $n$ 个骰子 , 每个骰子内的数互不相同 , 每个骰子随机取一个数 , 使得异或和为 $d$ 的倍数 .

解题思路

离谱的构造题 QwQ .

因为 $d$ 的范围较小 ( $0 \le d \le 60$ ) , 可以用 6 位二进制表示 , 64 进制构造 .

即 $0d$ , $1d$ , $64d$ , $65d$ , $4096d$ , $4097d$ . 值域不到上限 $3 \times 10^5$ , 能过 .

彩带裁剪-Cut

题面

给定一个长为 $n$ 的序列 , 将其分为若干区间 , 每个区间的贡献为最小的这个区间没有出现过的非负整数 $\operatorname{mex}$. 最大化 $\sum mex$ .

解题思路

显然的动态规划 .

设 $f_i$ 表示前 $i$ 个位置分开后的最大贡献 , 枚举上一个位置并计算 $\operatorname{mex}$ . 复杂度 $O(n^2)$

整体值域很小 , 因此每个区间的 $\operatorname{mex}$ 不会超过 $21$ . 并且 $dp_i$ 单调不降 , 转移时枚举最后一段的 $\operatorname{mex}$ , 求能取到该值的最右端 ( 可以预处理 ) . 复杂度 $O(nV)$

挑战NPC Hamilton

题面

给定一个 $n$ 个点 $m$ 条边的有向图 , 选出一些边 , 使得每个点的入度和出度都为 $1$ .

解题思路

拆点网络流 .

对于原图的点 $i$ , 建立边 $S \rightarrow i$ , $i + n \rightarrow T$ ( 流量为 1 ) , 对于原图的边 $u \rightarrow v$ , 建边 $u \rightarrow v + n$ .

跑 $S$ 到 $T$ 的最大流 $flow$ , 如果 $flow < n$ 则无解 , 否则将原图中所有所选的边 $u \rightarrow v$ 连成若干个环即可 .

Vlak

题面

Nina 和 Emilija 轮流写字母 , 每个人写下的字母后的总字符串必须是对方指定的字符串的前缀 . 无法写下字母是对方获胜 .

每个人都会采取最优策略 .

解题思路

字典树加一点点贪心 .

首先将 Tire 树建好 , 另外记录每条边的所属信息 ( Nina 或 Emilija ) . 树上 $Dfs$ 即可 .

$Dfs$ 具体思路 :

把当前选择写字母的人的过程转换为当前点找边 , 点的深度表示当前写字母的人 ( 0 代表 Nina , 1 代表 Emilija ) , 只搜索属于自己的边 .

Strategy 1

向下找边时 , Nina 找到一条尽属于她自己的边 , 则当前的最优解就是选这条边 . 当下一次 Emilija 进行选边是一定无边可选 . Nina 获胜 .

Strategy 2

如果 Nina 找不到属于她自己的边 , 就无法向下找边 , Emilija 获胜 .

Strategy 3

如果 Nina 找到了属于她们两人的边 , 直接 $Dfs$ 都试一下 , 只要有一条能使她必胜 , 那么这条边就是所有的最优策略 . 否则 Emilija 必胜 .

总而言之 , 如果一条边同时属于两个人 , 向下把每条边 $Dfs$ , 只要有一条边的返回值能使她必胜那么对手必输 , 反之亦然 .

Papričice

题面

有 $n$ 个节点 ( 辣椒 ) , 这些节点由 $n - 1$ 条边连起来组成一棵树 . 现在需要删除 ( 切掉 ) 2 条边 , 使得这棵树分为 3 个子树 , 每个子树内节点的数量分别为 $a , b , c$ . 求 $\min(\max{(a,b,c)} - \min{(a,b,c)})$ .

解题思路

设节点 1 为根节点 , $size_i$ 为以 $i$ 为根的子树的节点的个数 , 则只有两种可以切割的情况 :

1 . 所切下来的 2 个节点以 $u$ , $v$ 为根 , 且互不为对方的祖先 , 则这 3 棵子树内的节点数分别为 $size_u$ , $size_v$ , $n - size_u - size_v$

对于这种情况 , 枚举其 LCA 的节点 $p$ . 在 $p$ 中的子树集合找到 $2$ 个集合最接近 $\dfrac{n}{3}$ 就 $o$ 的 $k$ 了 . ヾ(≧▽≦*)o

2 . 另一种情况是第 $1$ 刀切的边是 $u$ 的子树, 第 $2$ 刀切的是 $u$ 中的一个节点 $v$ 和它的父节点的边 . 则这 $3$ 棵子树内的节点数分别为 $size_u - size_v$ , $size_v$ , $n - size_u$ .

这种情况直接枚举所有 $u$ . 在集合内找最接近 $\dfrac{size_u}{2}$ 的子树 .

复杂度 $O(n \log^2 n)$

Bajka

题面

Fabijian 有两个字符串 , $afraid$ 和 $like$ .

将 $like$ 重构得到 $s$ 使其等于 $afraid$ , 有以下 2 中操作 :

1 . ( 如果有的话 ) 向左或向右移动 1 个字符 , 将移动后的字符添加到 $s$ 的末尾 .

2 . ( 如果有的话 ) 移动到与当前字符相同的字符上 , 无添加操作 .

每次移动的代价为两个字符的距离 , 总代价为 $cost$ .

最小化 $cost$ .

解题思路

显然的 $dp$ .

设 $dp_{i,j}$ 表示当前正在 $afraid$ 的第 $i$ 个位置 , 写下一个字符 $like_j$ 所需要的最小的代价 , 转移为 :

$$dp_{i,j} = \min{dp_{k,j - 1} + c}$$

在这种情况操作 2 是极为耗费时间的 , 显然不优 , 新的转移 :

1 . $dp_{i,j}$ 尝试向 $dp_{i \pm 1,j + 1}$ 转移 , 其中 $afraid_{i \pm 1} = like_{j + 1}$ .

2 . 从 $dp_{i,j}$ 向 $dp_{k,j}$ 转移 , 其中 $afraid_j = afraid_k$ . 前缀和优化到 $O(m)$ .

复杂度 $O(nm)$ .

$\text{序列修改}$

题面

有一个序列 $a$ , 定义其频度序列 $c$ , 其中 $c_i$ 表示 $a_1$ 至 $a_i$ 中不同数的个数 .

修改 $a$ 中的元素的代价为修改前后的差的绝对值 , 记为 $cost$ .

最小化 $cost + \sum_{i = 1} ^ {n} i \times c_i$

解题思路

每个数字的只有第一次出现时会对 $c_i$ 产生贡献 , 设 $i$ , $j$ 分别为 $a_i$ , $a_j$ 分别第一次出现的位置 , $k$ 为 $a_i$ 下一次出现的位置 , $S_i$ = $\sum_{j = i}^{n} j$ .

分类讨论 :

能够产生贡献的只有 $2$ 种情况 .

1 . $i > j$ , 新增的 $cost$ 为 $\lvert a_i - a_j \rvert - S_i + S_k$ , 用 $set$ 找到 $a_i$ 前最近的 $a_j$ .

2 . $i < j \ and \ j < k$ , 新增的 $cost$ 为 $\lvert a_i - a_j \rvert + S_i - S_j$ . 再次分类讨论 :

• $a_i > a_j$ : 代价为 $(S_k + a_i)$ - $(S_j + a_j)$ .
• $a_i < a_j$ : 代价为 $(S_k - a_j)$ - $(S_j - a_j)$ .

树状数组维护 .

复杂度 $O(n \log n)$

城市天际线

题面

构造一个有 $n$ 个点 $m$ 条边的简单有向图 , 恰好有 $X$ 个 SCC ( 强连通分量 ) . $q$ 个限制每个限制要求 $2$ 个点 ( $a_u$ , $a_v$ ) 在同一 SCC .

$\text{解题思路}$

用并查集维护 ( $a_u$ , $a_v$ ) 的限制 . 设连通块按大小排序为 $s_1$ , $s_2$ . . . $s_k$ , 当 $k > X$ 时无解 . 否则将最大的 $X - k + 1$ 个 SCC 合并 , 得到最多的边 . 设大小为 $t$ 的连通块的边的范围为 $[t,t(t - 1)]$ , 大小为 $x$ , $y$ 的连通块之间的边数为 $[0,xy]$ , 判断上下界 .

排列

题面

定义 $f(n)$ 的值为满足下列长度为 $n$ 的排列 $p$ 的个数 :

$$p_1 = 1 \land \forall i < n,\lvert a_i - a_{i + 1} \rvert \le 2$$

给定 $T$ 组询问 , 回答每个询问 $f(n)$ 的值 ( $mod\ 1e9 + 7$ ) .

求所有值的异或和 .

解题思路

$p_1 = 1$ , $p_2 \in {2,3}$ . 分类讨论 :

1 . $p_2 = 2$ , 方案数为 $f(n - 1)$ .

2 . $p_2 = 3$ :

• $p_3 = 2$ , 必有 $p_4 = 4$ , 方案为 $f(n - 3)$ .
• $p_3 = 5$ , 有且仅有唯一方案 $[1,3,5,7\ .\ .\ .\ 2k + 1,2k,2k - 1\ .\ .\ .\ 4,2]$ .

有 :

$$f(n) = f(n - 1) + f(n - 3) + 1$$

换元优化一下矩阵快速幂 .