Codeforces Round 911 (Div. 2)

· · 个人记录

由于 F 题 2800 的评分，没时间补完了，先放上前 5 题。

感觉这次 E << D，赛时没做 E 有点亏。

A

如果存在连续 3 个空位置，那么答案显然最多是 2。

其余情况统计空位数量即可。

B

假设只剩下 a，被消耗掉的是 b,c。
略微思考可发现，主要在于如何让 b,c 数量相等。
而不管怎么操作，b,c 数量差的奇偶不变，所以根据奇偶判断就行。
数量不用担心，只用看奇偶。

C

树形 dp 基础题。
设 dp_i 为 i 到其子树叶子节点的最小操作次数。

后面懒得写了。

D

欧拉函数求两两 gcd 之和 + 分块算法
为了方便，如果两数相同，编号靠前的小。

排个序然后枚举 b 的位置，计算 b=i 时，对于所有可能 a 的 gcd 之和（参照如何计算两两 gcd 之和，可以容斥），另外计算出多少种 c 时可行的。

然后没了，赛时计算两两 gcd 之和是抄的网上板子（按 CF 规则不违规），最后一刻提交，变量名 data 撞标准库 CE 了，赛后加 namespace 过了。

E

为数不多的独立解出的 Div.2 E，可惜是赛后。

考虑原题加边带来的影响。

原图能沿着什么路径走，现在仍然能且只能按照什么路径走。

为什么这么说呢？

现在的图，每一个点向所有原来途中自己能到达的点连了边。

虽然现在的图不允许路径重复经过点，却可以跳跃到达按照原图路径能到达的点（假设原图中允许重复经过点）

本质上问题转化成，给你一张图 G（就是原始图），可以重复经过点，要求找出最长路径，同时满足权值和最小。

这个问题 tarjan 缩点+拓扑排序 dp 就能解决。

F

待完成。