Codeforces Round 916 (Div. 3)

这场本来是想在比赛的时候写的，可惜写到一半突然有公司的电话进来了，就只好先去处理点事情了

A. Problemsolving Log

大致题意

写出 A 题需要思考 1min，写出 B 题需要思考 2min，以此类推，给出一个人每分钟在思考的题，问最终有几道题能写出来

思路

简单题，统计一下每个字母出现次数就行了

AC code

B. Preparing for the Contest

大致题意

需要构造一个长度为 n 的序列，使得其满足所有相邻两个值中，存在恰好 k 个前者大于后者的对数

思路

也是简单题，想清楚怎么构造就行。比如我的思路是把最大的 k 个值按照递增序放在后面

AC code

C. Quests

大致题意

有一堆问题，第一次写出来可以得到 $a_i$ 的分数，第二次及之后写出来可以得到 $b_i$ 的分数

每道题写出来的前提是前面的所有题至少都写出来一次

问最多写 $x$ 道题，最多可以得到多少分

思路

由于每道题必须要前面的所有题都写出来才能写，所以可以考虑枚举最终写到了哪道题，然后把剩下的所有写题的机会给那个 $b_i$ 最大的题即可

AC code

D. Three Activities

大致题意

有三种活动，且有 $n$ 天，每一天最多参加一个活动，每一个活动最多只能有一天参加。

每个活动每天都有其他伙伴一起来参加，数量都不相同。问应该挑哪三天去参加活动，能够使得一起参加的伙伴数量最多

思路

由于总共就只有三种活动，所以只需要挑选三天。对于每一个活动而言，他们只需要考虑参加伙伴最多的那三天即可

所以在每一个活动下单独排序参加的伙伴数量，选择每个活动下伙伴最多的三天，暴力找下答案即可

AC code

E2. Game with Marbles (Hard Version)

大致题意

直接看 Hard Version

Alice 和 Bob 做游戏，有 $n$ 种颜色的石头，每个人都有所有颜色的石头若干个

每轮，当前的选手需要选择一种颜色，然后当前选手丢掉一个这种颜色的石头，对方丢掉全部的

目标是让自己的石头数量之和尽可能多，问最后剩下多少个

思路

假如一种颜色的石头，Alice 有 $a$ 个，Bob 有 $b$ 个。如果是 Alice 选择，那么 Alice 会剩下 $a-1$ 个，差值是 $a-1$。如果是 Bob 选择，则是 $-(b-1)$

这样可以得到，不选择这个颜色的代价就是 $(a-1)-(-(b-1)) = (a+b-2)$，同时选择它的收益也是这个

按照代价排序，从最大的代价依次开始操作即可

AC code

F. Programming Competition

大致题意

一个公司，其上级或者间接的上级都是他老板，现在需要两两组队，但是有老板关系的不能组，问最多可以组几个队伍

思路

树上 dfs 搜索即可，每次传给当前节点，外面不属于他的员工的节点数量还有多少，有就用掉即可

AC code

G2. Light Bulbs (Hard Version)

大致题意

这题还是挺有意思的

有一排灯，其中每种颜色的灯恰好有两个，可以选择开始的时候，点亮一部分灯，之后可以无限次进行如下操作

• 点亮一盏灯，前提是和他相同颜色的另一盏灯已经点亮了
• 选择一种颜色，其两盏灯都已经点亮了，将这两盏灯中间的所有灯点亮

问开始的时候最少选择几盏灯，就可以把所有灯都点亮。同时给出可以选择的数量

思路

首先，如果存在一个 $a$ 夹在两个 $b$ 之间，那么只需要点亮 $b$ 就可以点亮 $a$，我们可以进行建图来做

但是如果这样完整建图的成本会很高，所以得考虑优化一下
例如 $1,2,3,4,1,2,3,4$ 这种，就会变成一个全连接的图，而点数量有 $2 \times 10^5$，故不太行

由于这个图并不是传统的拓扑排序，而是只要上游任意一个点满足则满足（传统拓扑是上游均满足才满足）所以可以做反向路径压缩，即“别压缩”

例如上面的例子，仅实现与最后出现的那个区间进行连接，例如上图，则仅有 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1$，
容易的得到这样建图也是可以满足要求的，因为不是传统拓扑

那么只需要在创建完成图之后，将拓扑的首个节点序列拿出来即可，这些节点是必选。因为有两个相同颜色的灯，所以是 $2^x$ 种选择

接下来考虑成环的情况，我们只需要找出最初试图进入环的那个节点（最左边的节点，因为它必然可以连接到剩下所有的节点）
看剩下环内的节点是否能够反向到达它即可。可以反向建图来做。至于最初进入环的节点，可以用并查集

AC code

Generated by RSStT. The copyright belongs to the original author.

Source