Codeforces Round #514 (Div. 2)题解

A

喵，直接模拟。

B

枚举所有盖章时的，合法的，左上角的位置。能盖的话就盖一下。最后check一下图案是否相等即可

C

• 一轮一轮的扔。
• 如果\(len \geq 4\), 扔掉\(1,3,5,7....\)的位置。
• \(len=3\), 扔\(2,1,3\)
• \(len=2\), 扔\(1,2\)
• \(len=1\), 扔\(1\)

为什么这样构造呢？因为\(x,x+1\)肯定是互质的，所以我们先扔掉所有奇数。这样我们才可以在\((len+1)/2\)轮后使得所有数字的\(gcd\)，乘\(2\)。

D

• 二分半径\(r\)
• 那么，圆心一定在直线\(y=r\)上啦。
• 对于每个点，圆心合法的位置是一个区间，判断区间交是否为空即可。
• 为什么可以二分？因为\(r\)越大，每个\(r\)对应的合法区间就越长吖。

E

比赛的时候70分钟都没A掉。打得烂！

• 我们先考虑一条链。对于每个点，维护它最远能往上跳多远，那么每个点都会对应着一个区间\([l,r]\),现在我们需要选择最少的区间使得整个链都被覆盖。这是很经典的贪心问题啦！
• 这个题，无非是把链的问题放在了树上。考虑节点\(u\),我们用\(dp[u]\)表示覆盖\(u\)的子树，最少需要几条路径，\(low[u]\)表示，\(u\)的子树中，最高能跳到哪一层。

转移：

dp[u] = max{dp[v]}; low[u] = min{low[v]};if (low[u] > dep[u]) dp[u] ++, low[u]=up[u];