做题记录——2.20-2.26

2022.2.24

哈↑哈↓。

我是小丑。

CF1638D Big Brush

哈哈，不会 constructive algorithms。

考虑倒着操作，那么一定会存在一个完整的 2*2 方块。

把这个方块拿掉，原位置可以是任意颜色，再 check 一下有没有其他完整方块。

CF1438C Engineer Artem

如果考场上遇到这题，我可能真的 2-sat 莽过去了。

按照行列奇偶性搞就行了。

CF1366D Two Divisors

大力猜想搞两个质因数出来就行了。

CF1349B Orac and Medians

判断是否有区间中位数 \(\geq k\)。

CF1375F Integer Game

考虑当前状态形成等差数列，并且最大值不能操作时，先手必胜。

那么对于初始的 \(a,a+x,a+x+y\)，可以构造 \(2y+x\)。

CF484E Sign on Fence

毛估估一发，把大于 \(x\) 的看成 \(1\)，小于 \(x\) 的看成 \(0\)。

整体二分套个线段树，维护一下区间最长 len 就行了。

2022.2.25

CF468C Hack it!

考虑 \(f(x+10^{18}) = f(x)+1\)。

设 \(\sum\limits_{i=0}^{10^{18}} f(i) = p\)，那么 \(\sum\limits_{i=j}^{10^{18}+j} f(i) = p+j\)。

于是就可以构造了。

CF1325F Ehab's Last Theorem

搞出一棵 dfs 树，如果有满足条件的环就选。

如果没有满足条件的环，选择一个点至多会 ban 掉它的 \(\sqrt n - 2\) 个祖先。直接染色即可。