Siyuan 的博客

「Codeforces 1189D1」Add on a Tree

题目链接：Codeforces 1189D1

你有一个棵 $n$ 个点的树，初始所有的边上的数字都是 $0$。对于每次操作，你可以选择两个不同的叶子节点 $u,v$ 和一个任意实数 $x$ 并把 $u - v$ 这条简单路径上的边加上 $x$。

我们令 $w_{i}$ 表示最终第 $i$ 条边上的实数，是否对于所有的 $w_{i} \in \mathbf{R}, 1 \le i < n$，都存在有限的操作使得所有的边都满足条件？如果可行则输出 YES 否则输出 NO。

注意叶子节点的定义为度数为 $1$ 的点。

数据范围：$2 \le n \le 10 ^ {5}$。

「Luogu 4173」残缺的字符串

题目链接：Luogu 4173

很久很久以前，在你刚刚学习字符串匹配的时候，有两个仅包含小写字母的字符串 $A$ 和 $B$，其中 $A$ 串长度为 $m$，$B$ 串长度为 $n$。可当你现在再次碰到这两个串时，这两个串已经老化了，每个串都有不同程度的残缺。

你想对这两个串重新进行匹配，其中 $A$ 为模板串，那么现在问题来了，请回答，对于 $B$ 的每一个位置 $i$，从这个位置开始连续 $m$ 个字符形成的子串是否可能与 $A$ 串完全匹配？

数据范围：$1 \le m \le n \le 3 \times 10 ^ {5}$。

「Codeforces 1199E」Matching vs Independent Set

题目链接：Codeforces 1199E

给定一个由 $3 \cdot n$ 个点、$m$ 条边组成的图。你需要找到一组大小为 $n$ 的边的匹配，或者找到一组大小为 $n$ 的独立集。

一组边的匹配表示不存在两条边拥有一个共同的点。

一组独立集表示不存在两个点被同一条边相连。

如果能找到一组边的匹配，输出 Matching 和方案；如果能找到一组独立集，输出 IndSet 和方案；否则输出 Impossible。

本题有 $T$ 组数据。

数据范围：$1 \le \sum n \le 10 ^ {5}$，$0 \le \sum m \le 5 \times 10 ^ {5}$。

「Codeforces 1199F」Rectangle Painting 1

题目链接：Codeforces 1199F

有一个大小为 $n \times n$ 的网格图。其中一些格子是黑色的，其余格子都是白色的。你每次操作可以任意选择一个大小为 $h \times w$ 的矩形并把它全部染成白色，花费为 $\max(h, w)$。现在你想把所有格子都染成白色，请求出最小花费。

数据范围：$1 \le n \le 50$。

「WC 2011」最大 XOR 和路径

题目链接：BZOJ 2115

考虑一个包含 $n$ 个点和 $m$ 条边的无向连通图，节点编号为 $1$ 到 $n$，第 $i$ 条边的边权为非负整数 $D_{i}$。试求出一条从 $1$ 号节点到 $n$ 号节点的路径，使得路径上经过的边的全是的 $\text{XOR}$ 和最大。

路径可以重复经过某些点或边，当一条边在路径中出现了多次时，其权值在计算 $\text{XOR}$ 和时也要被计算相应多的次数。

数据范围：$1 \le n \le 5 \times 10 ^ {4}$，$1 \le m \le 10 ^ {5}$，$0 \le D_{i} \le 10 ^ {18}$。

「AHOI / HNOI 2017」礼物

题目链接：LOJ 2020

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手环，一个留给自己，一个送给她。每个手环上各有 $n$ 个装饰物，并且每个装饰物都有一定的亮度。

但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的整数 $c$（可能是负数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，但是由于上面装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。

在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 $1, 2, \dots, n$，其中 $n$ 为每个手环的装饰物个数，第一个手环的 $i$ 号位置装饰物亮度为 $x_i$，第二个手环的 $i$ 号位置装饰物亮度为 $y_i$，两个手环之间的差异值为：

$$ \sum_{i = 1} ^ {n} (x_{i} - y_{i}) ^ {2} $$

麻烦你帮他计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小，这个最小值是多少呢？

数据范围：$1 \le n \le 5 \times 10 ^4$，$1 \le a_{i} \le m \le 100$。

「2019 Multi-University Training Contest 2」Longest Subarray

题目链接：HDU 6602

你有一个长度为 $n$ 的序列 $a$ 和两个整数 $C, K$ 满足序列中的所有元素 $1 \le a_{i} \le C$。

我们定义一个连续子序列 $a_{l}, a_{l + 1}, \dots, a_{r}$ 是「好的」当且仅当：

$$ \forall x \in [1, C], \sum_{i = l} ^ {r} [a_{i} = x] = 0\ \text{或}\ \sum_{i = l} ^ {r} [a_{i} = x] \ge K $$

抽象地，如果一个数字在子序列中出现过，那么它的出现次数必须不少于 $K$ 次。

他需要求出「好的」连续子序列的最长长度。

本题有多组数据。

数据范围：$1 \le n, C, K \le 10 ^ 5$，$1 \le a_{i} \le C$，$1 \le \sum n, \sum C, \sum K \le 5 \times 10 ^ 5$。

「2019 Multi-University Training Contest 2」Harmonious Army

题目链接：HDU 6598

在一个军队里有 $n$ 名士兵。每名士兵需要分配一个任务：Mage 或 Warrior。这些士兵中有 $m$ 对士兵有良好的凝聚力。如果这两名士兵都参加 Warrior 任务，军队的效率会增加 $a$；如果这两名士兵都参加 Mage 任务，军队的效率会增加 $c$；否则军队的效率会增加 $b = \frac{a}{4} + \frac{c}{3}$（保证 $4 \mid a, 3 \mid c$）。

你需要求出军队效率的最大值。

本题有多组数据。

数据范围：$1 \le n \le 500$，$0 \le m \le 10 ^ 4$，$1 \le a, b \le 4 \times 10 ^ 6$，$\sum n \le 5 \times 10 ^ 3$，$\sum m \le 5 \times 10 ^ 4$。

「2019 Multi-University Training Contest 2」Fantastic Magic Cube

题目链接：HDU 6596

你有一个正整数 $n$ 和一个六元组集合，我们定义六元组 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 的权值为 $\sum_{l_{x} \le x \le r_{x}, l_{y} \le y \le r_{y}, l_{z} \le z \le r_{z}} x \oplus y \oplus z$。

初始集合中只有一个元素 $(0, n - 1, 0, n - 1, 0, n - 1)$。接下来你要重复进行以下操作，直到集合的大小为 $n ^ 3$。

• 从集合中选择一个六元组 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 满足 $l_{x} < r_{x}$ 或 $l_{y} < r_{y}$ 或 $l_{z} < r_{z}$。

• 然后你需要从 $\{ x, y, z \}$ 中选择恰好一个元素，选择元素 $k$ 的条件是 $l_{k} < r_{k}$。

  • 如果你选择了 $x$，接下来你需要选择一个整数 $t \in [l_{x}, r_{x})$，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除，将 $(l_{x}, t, l_{y}, r_{y}, l_{z}, r_{z})$ 和 $(t +1, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。
  • 如果你选择了 $y$，接下来你需要选择一个整数 $t \in [l_{y}, r_{y})$，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除，将 $(l_{x}, r_{x}, l_{y}, t, l_{z}, r_{z})$ 和 $(l_{x}, r_{x}, t + 1, r_{y}, l_{z}, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。
  • 如果你选择了 $z$，接下来你需要选择一个整数 $t \in [l_{z}, r_{z})$，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, t)$ 和 $(l_{x}, r_{x}, l_{y}, r_{y}, t + 1, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。

请你求出可以获得的最大权值，答案对 $998244353$ 取模。

本题有多组数据。

数据范围：$1 \le n \le 10 ^ 6$，$1 \le \sum n \le 3 \times 10 ^ 6$。

「2019 Multi-University Training Contest 2」Everything Is Generated In Equal Probability

题目链接：HDU 6595

Y_UME 有一个整数 $N$ 和一串有趣的代码：

首先，他先等概率随机一个正整数 $n \in [1, N]$，再等概率随机一个长度为 $n$ 的排列。最后他会将这个排列传入函数 $\text{Calculate}$ 并得到一个返回值。请你求出这个值的期望，答案对 $998244353$ 取模。

本题有多组数据。

数据范围：$1 \le N \le 3000$，$\sum N \le 5 \times 10 ^ {4}$。