Codeforces Round #200 (Div. 1 + Div. 2)

2024-09-06 15:17:36

A. Magnets

模拟。

B. Simple Molecules

设12、13、23边的条数，列出三个等式，解即可。

C. Rational Resistance

题目每次扩展的电阻之一是1Ω的，所以假设当前的电阻为\(\frac{a}{b}\)会变成\(\frac{a+b}{b}\)或\(\frac{a}{a+b}\)，其实就是求gcd的过程。

D. Alternating Current

若出现连续两个相同的符号，其实线的方向是不变的，最后就是转化成括号匹配。

E. Read Time

二分时间\(t\)，\(p_1\)应该由\(h_1\)来覆盖，此时分两种情况：
1. \(h_1<=p_1\)，\(h_1\)覆盖区间\([h_1, h_1+t]\)。
2. 否则，\(h_1\)此时有两种覆盖\(p_1\)的方法：先覆盖\(p_1\)，然后马上往回走；先往后覆盖，然后返回\(p_1\)。在这两种方法找覆盖区间最大的。

F. Water Tree

对于操作1，利用dfs序转化成区间覆盖问题，覆盖的值为最大操作id。
对于操作2，点\(v\)影响它的所有祖先，dfs序下这些祖先的区间都包含点\(v\)，那么就相当于祖先查询区间最大的操作id。
整个问题就变成区间修改+单点查询和单点修改+区间查询问题。
更简单的做法：用一个set维护所有empty链，对于操作1来说，直接暴力删除区间内的链;操作2则直接将点\(v\)插入，表示\(v\)到根的empty链。

G. Pumping Stations

本题的关键在于构出最小割树，在这前提下，根作为序列第一个值，每次贪心地取和序列最后一个点流最大的点，构出序列。

最新文章

热门文章