某岛

… : "…アッカリ~ン . .. . " .. .
May 8, 2020

Codeforces Round #639

喜闻乐见的连续两场 unrated … 导致第二天直接开了一场压力测试。

A. Hilbert’s Hotel

按照题意求余统计有没有重复即可,作为 A 题来说未免有点太水了。

B. Monopole Magnets

读题压力巨大,这里 possible 是必须要存在一种让 N 极移动过去的方案,所以每个连通块需要恰好有一个 N,然后只需要检查掉不合法的情况就好。

C. Quantifier Question

考察一些情况,有环的话显然无解。否则,对于 xi < xj,一定是一个 A 一个 E,如果 i < j,那么 A xi E xj,如果 j < i,那么 A xj E xi 就好。
所以先检查是否能够拓扑排序,然后贪心的优先设置 A 即可。

D. Résumé Review

显然先对函数做一下差分,发现是一个二次函数,对称轴在 0.5,所以在正整数范围内单调递减,于是可以贪心。
考虑到 k 很大,可以二分 threhold,里层可以再套个二分或者解二次函数。
这样最后 k 可能还没有全部用上,出来之后还需要补正一下。

E. Train Tracks

数据结构题。
这个切铁路的动作和 link-cut tree 里的 access 完全一致。
所以第一问可以 link-cut tree,然后就要想想第二问怎么写比较简单了,最好也能用 link-cut tree。

F. Piet’s Palette

套路题。
构造出矩阵表示出题目中的几个操作。
然后可以高斯消元即可。