Codeforces-167

玩脱了，目测要是用大号或者小号的话都会跌吧，幸亏用小小号 lol

Solution

A

水题，记个 max 就可以了。

我会说我看题看了 6min ？

B

对于相同横坐标的可以用很多种排法，这个用阶乘计算。然后除去 2 的满足 A[i] = B[i] 的 i 的数量次方就可以了。

如何除呢？约分就可以了。

C

构造。可以证明，任意一个满足要求的图都可以找到一种方法。考虑一个点，只要这个点周围和它在同一个集合的点的数目不超过和它在不同集合的点的数目，那么这个点就是满足要求的，即邻域中与它在同一个集合的点的个数一定不超过 1 ，因为这个点度数不超过 3 。

所以调整一下，每次选择一个超过的点，换到对面集合里去即可。由于每换一次，矛盾数会减少，所以这个调整总是可以结束的。

我就不吐槽这个题是 原题 或者 原题 了。

D

dp 。显然这个连通块一定是凸的，我们令 f[L, i, j, s] 表示前 L 列，第 L 列的范围为 [i, j] ，且边界状态为 s 的方案数。什么是边界状态呢？考虑上边界，一定是先上再下的，下边界一定是先下再上的，我们就把这个定义为边界状态。

转移的话，如果暴力枚举上一列的范围，复杂度会很高，于是记个前缀和就可以了。

一堆人蒯源代码 T_T……我还是不吐槽这是 原题 或者 原题 了。

E

不坑不科学。

situation

刚被 TC 打击到，现在又要被 CF 打击了。

看了好久 A 的题目才看到有张图。然后随手写个程序就是过不了样例，最后 YY 了好久才过样例 sad

然后看完 B 后想了一个错误算法……因为我想错题了，于是怒 WA #3 。最后是 44min 才过了 B 。

看了 CDE 觉得 C 题似乎考过的样子，但是当时靠着数据水骗了过去，现在不行了。于是就没写 C 了。

D 题看一眼觉得是 dp ，但是很难写的样子。E 没啥想法。我决定还是写 D 吧。

写啊写写啊写一个函数忘记返回值为 64 位贡献一次 WA #11 然后改了后就过了。

后面也没心思写题了，觉得也写不出啥了。但是后来发现如果有想法了，那么 C 还是可写的，代码量真的很少啊亲～

最后就挂了嘛，毫无疑问地挂了嘛。#64 哭了。

others

有人猜得到我第一句话应该是——

强烈谴责 XLk 的虐场行为！

D xiaodao 直接把 Petr 的 java 代码交了上去， XLk 还算良心，还改成了 C++ 代码 = =||

然后 XLk 在 1:58 的时候交了 C 过了。然后就 #12 了。

文学巨匠靠着 D 的手速混到了 #33 也还不错了。

hza 靠着每个题速度都不差混到了 #49 。

我就是太慢加上贡献了两次 WA 导致被虐残了 T_T

scottai 似乎是倒着做题的 = =|| 然后就挂了。

edly 居然 C 没过。

nonsense

XLk 的大号被小号超了！看来如果我再不做大号就要被 XLk 虐飞了（现在已经被虐出翔了） T_T 。