标签 贪心 下的文章

「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 1」Operation

题目链接：HDU 6579

给定一个长度为 $n$ 的序列 $a$，接下来有 $m$ 个操作，操作分为如下 $2$ 种：

• 0 l r：选择 $a_l, a_{l +1}, \dots, a_{r}$ 中的一些数，使得他们的异或和最大，输出最大的异或和。
• 1 x：将 $x$ 加入到序列的最后，并且将 $n$ 更新为 $n + 1$。

操作强制在线，我们设 $lastans$ 表示上一次操作 $0$ 的答案，初始值为 $0$。

对于所有操作 $0$，令 $l = (l\ \text{xor}\ lastans) \bmod n +1$，$r = (r\ \text{xor}\ lastans)\bmod n +1$，如果 $l > r$ 则交换两数。

对于所有操作 $1$，令 $x = x\ \text{xor}\ lastans$。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 10$，$1 \le n, m \le 5 \times 10 ^ 5$，$\sum n, \sum m \le 10 ^ 6$，$0 \le a_i, x < 2 ^ {30}$。

「Codeforces 1186F」Vus the Cossack and a Graph

题目链接：Codeforces 1186F

Vus 有一张包含 $n$ 个点和 $m$ 条边的图。设 $d_i$ 表示第 $i$ 个点的度数。他需要保留 $\left\lceil\frac{n + m}{2}\right\rceil$ 条边，设 $f_i$ 表示新图中第 $i$ 个点的度数。他需要对于所有的 $i$ 保证 $\left\lceil\frac{d_i}{2}\right\rceil \le f_i$。

请你帮 Vus 保留一些边使这张图满足条件。

数据范围：$1 \le n \le 10 ^ 6$，$0 \le m \le 10 ^ 6$。

「Codeforces 1185F」Two Pizzas

题目链接：Codeforces 1185F

有 $n$ 个人想要买两个比萨。众所周知，比萨共有 $9$ 种成分，用 $1$ 到 $9$ 的整数表示。每个人都有若干喜欢的成分（至多有 $9$ 种）；商店里一共有 $m$ 个比萨，每个比萨都有若干成分组成和一个价格 $c_i$。

你需要选择 $2$ 个比萨，使这些人中满足的人数最多。如果一个人是满足的当且仅当对于任何一个他喜欢的成分，至少出现在其中一个比萨中。如果有多种方案，输出价格最小的方案。

数据范围：$1 \le n \le 10 ^ 5$，$2 \le m \le 10 ^ 5$，$1 \le c_i \le 10 ^ 9$。

「Codeforces 1148E」Earth Wind and Fire

题目链接：Codeforces 1148E

数轴上有 $n$ 块石头。最初，第 $i$ 个石头位于坐标 $s_i$ 的位置。同一个地方可能有不止一块石头。

你可以进行如下操作任意次（可以为 $0$ 次）：

• 拿出下标为 $i, j$ 且满足 $s_i \le s_j$ 的两块石头，选择一个整数 $d$ 满足 $0 \le 2 \cdot d \le s_j - s_i$ 并将第 $i$ 块石头放到坐标为 $(s_i + d)$ 的地方，将第 $j$ 块石头放到坐标为 $(s_j - d)$ 的地方。换言之，将两块石头相互靠近。

你想通过移动，将石头的坐标变为 $t_1, t_2, \dots, t_n$，注意石头的顺序是无关紧要的。

判断是否存在一种移动石头的方法。如果可以，输出 YES 并构造一种方法；否则输出 NO。你不需要最小化移动次数。

数据范围：$1 \le n \le 3 \times 10 ^ 5$，$1 \le s_i, t_i \le 10 ^ 9$。

「Codeforces 1156C」Match Points

题目链接：Codeforces 1156C

在一条数轴上有 $n$ 个点 $x_1, x_2, \dots, x_n$，两个点 $i, j$ 可以匹配当且仅当两者都满足：

• 两个点 $i, j$ 都没有和别的点匹配。
• $\lvert x_i - x_j \rvert \ge z​$。

请求出最多可以匹配多少对点。

数据范围：$2 \le n \le 2 \times 10 ^ 5​$，$1 \le x_i, z \le 10 ^ 9​$

「Codeforces 1150D」Three Religions

题目链接：Codeforces 1150D

在中东考古研究期间，你发现了三种古代宗教的遗迹：第一宗教、第二宗教和第三宗教。你收集到了每一种宗教的演变信息，你现在想知道三种宗教是否可以和平共处。

宇宙之词是一个长度为 $n$ 的只包含小写字母的单词。在任何时候，每一种宗教都可以用一个由小写字母组成的单词来描述。

如果描述这三种宗教的单词是宇宙之词的不相交子序列，那么他们的信徒就可以和平共处。形式化地，我们能够对宇宙之词的若干位置给定一个标号 $1, 2, 3$，那么标号为 $i$ 的位置构成的单词就是第 $i$ 种宗教的描述。

然而，宗教是在不断发展的。最初，每个宗教的描述都是空的；在发展过程中，宗教进行了 $q$ 次变化。每次变化中，要么将一个字符附加到某个宗教的描述的末尾，要么从某个宗教的描述的末尾删除一个字符。每次变化后，你都需要判断宗教是否可以和平共处。

数据范围：$1 \le n \le 10 ^ 5$，$1 \le q \le 1000$，$\lvert \text{宗教的描述} \rvert \le 250$。

「Codeforces 1152C」Neko does Maths

题目链接：Codeforces 1152C

Neko 有两个整数 $a$ 和 $b$，他的目标是找到一个非负整数 $k$ 使得 $\operatorname{lcm}(a + k, b + k)$ 尽可能小。如果有 $k$ 有多组解，他会选择最小的一个。

数据范围：$1 \le a, b \le 10 ^ 9$。

「Codeforces 1153D」Serval and Rooted Tree

题目链接：Codeforces 1153D

Serval 在一棵有根树上玩数字游戏。这棵有根树有 $n$ 个节点，节点 $1$ 是根节点，节点 $i$ 的父亲节点用 $f_i$ 表示。所有非叶子节点上有一个操作 $\max$ 或 $\min$，这意味着这个节点上的值为其所有儿子节点的最大值或最小值。

假设这棵树上有 $k$ 个叶子节点，Serval 会把 $1, 2, \dots, k$ 写在这 $k$ 个节点上（每个数字恰好使用 $1$ 次），并且他想要最大化根节点的值。作为他的好朋友，请你帮他求出根节点的最大值。

数据范围：$2 \le n \le 3 \times 10 ^ 5​$，$1 \le f_i \le i - 1​$。

「十二省联考 2019」异或粽子

题目链接：LOJ 3048

小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。

小粽面前有 $n$ 种互不相同的粽子馅儿，小粽将它们摆放为了一排，并从左至右编号为 $1$ 到 $n$。第 $i$ 种馅儿具有一个非负整数的属性值 $a_i$。每种馅儿的数量都足够多，即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 $k$ 个粽子。

小粽的做法是：选两个整数数 $l,r$，满足 $1\le l\le r\le n$，将编号在 $[l,r]$ 范围内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子的属性值的异或和。

小粽想品尝不同口味的粽子，因此它不希望用同样的馅儿的集合做出一个以上的粽子。

小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧！

数据范围：$1 \le n \le 5 \times 10 ^ 5$，$1 \le k \le \min\left\{\frac{n(n - 1)}{2}, 2 \times 10 ^ 5\right\}$，$0 \le a_i \le 2 ^ {32} - 1$。