标签 贪心 下的文章
- 首页
- 贪心
「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$。