Revethere's Blog

骰子游戏-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$$

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

异或平方和

题面

定义 $b_{i,j}$ 为 $a_i$ 的二进制的第 $j$ 位的值 . $f_{i,j,k}$ 为 $a_i \oplus a_j$ 的第 $k$ 位的值 .

$$ans = \sum_{i = 1} ^ n \sum_{j = 1} ^ n(a_i \oplus a_j) ^ 2$$

$$= \sum_{i = 1} ^ n \sum_{j = 1} ^ n(\sum_{k = 1} ^ {L}(b_{i,k} \oplus b_{j,k})2 ^ k) ^ 2$$

$$= \sum_{i = 1} ^ n\sum_{j = 1} ^ n\sum_{k = 1} ^ L \sum_{l = 1}^L f_{i,j,k}f_{i,j,l}2 ^ {k + l}$$

$$= \sum_{k = 1}^{L} \sum_{l = 1}^L 2^{k + l} (\sum_{i = 1}^n \sum_{j = 1}^n[f_{i,j,k} = 1 \And f_{i,j,l} = 1])$$

设 $dp_{i,j,0 / 1,0 / 1}$ 表示第 $i$ 位和第 $j$ 位的数的数量 .

复杂度 $O(n \log^2 \lvert V \rvert)$ .