Codeforces-174

结果还没出就开始写了……随便啦，免得成为坑。

Solution

A

A 有 1000 分诶，所以不是简单题了。这是个简单数据结构题，写个树状数组就好了。

B

我勒个去坑翻我了。

很容易可以知道，只要记忆化一下就好。于是我开了个 map 来搞。但是在递归的时候为了预防死递归，我还用了个 set 来保存当前的栈。于是若干次错误就在这个栈这里了……最后 +4 才过。

C

感觉是个水题啊。

首先如果没有变量的限制条件，那就是一个很暴力的 dp 了。无解的一种情况就是出现了环。假设不存在环，考虑消除这种限制条件。对于一组限制 x[c] > x[b] ，我们可以尝试令 y[c] = x[c] - x[b] - 1 ，这样 y[c] 是没有限制条件的，同时，把 a[b] 加上 a[c] 。这样意味着每次取了一次 b 就要取一次 c ，而 y[c] 就是 c 比 b 多取的。

剩下的就是背包了。

D

这个题还蛮有意思的。

先考虑两个数可以相邻的条件。(x, y) 合法，当且仅当存在 t 使得 x = yt + y(y-1)/2 。所以当 y 为奇数时，只要 x = 0 mod y 即可。当 y 为偶数时，则条件为 x = y/2 mod y 。

接下来就是 dp 了。f[i] 表示前 i 个最多保留多少个，其中第 i 个必须保留。f[i] = max(f[j]) + 1 ，j 的条件为 j 到 i 这一段能凑出一个序列。考虑 a[i - 1] ， 如果 a[i] 是奇数，自然一种很自然的想法就是前一个继续用 a[i] ，否则前一个用 a[i] / 2 。这样维护一个数就好了，是这次 CF 中最好写的题。

E

我居然没看这个题……看了后发现应该是可做的，但是我不一定写得出。

首先需要用到 WC 某费用流题《石头剪刀布》的一个结论：

ans = C(n, 3) - sum(C(w[i], 2))

其中 w[i] 表示 i 的入度（或者出度）。证明很巧妙的说。

然后考虑如何统计 w[i] 。原题是在一个 n * n 的格子上进行操作的，每次取反一个子矩形。差分一维，线段树维护即可。

situation

首先做 A 。第一反应是维护一个和就好了，啥数据结构都不用。第二反应是要写个带标记的线段树，恶心啊。最后决定写树状数组吧。坑爹的 cout 输出精度，我一开始只输出了 6 位有效数字不幸 WA1 。换成 10 位就过了。

然后看 B 。我勒个去停电是什么状况啊！向总不是和门卫打了招呼了吗！坑爹啊亲！感觉这个题也蛮水的，写啊写提交发现 MLE 了……这明显是死递归的节奏啊，怒看代码发现了 WA 点。改了再交收获 WA 5 。又发现一个 WA 点再交，还是 WA 5 。还发现一个 WA 点终于过了 5 了——变成 WA 9 了……再找终于过了 pretest 了，泪流满面。只有 592 pts 了。

看 C 。一开始以为这是宇宙大水题，写了发现过不了样例，才发现看错题了 = = 重新看了遍题目发现仍然是水题，怒过。

看 D 觉得这题蛮适合我的口味的，偏数学，代码短。总之推了一下就发现可做了。

然后就没有然后了，连 E 的题目都没看。

最后发现 A 用时 11min C 用时 17min D 用时 13min B 用时 40 min ……最佳的做题顺序是 DCAB 啊亲，又被做题顺序坑了。

幸亏没有 FST 。#14 怒踩 Egor、CLJ 也不错了。下次如果 RP 还这么好就可以红了～

others

ST 之前 7k+ 夫妇怒占前二，然后 CLJ 怒 FST * 2 。

Seter 居然也在做？我很少看见他做啊。 #20 好牛叉。他首先做的 D ，犹豫了好久不敢交……他要是交了绝对虐我。

liouzhou_101 #22 和我一样被 B 坑了 50min

wuzhengkai #31 A 居然 FST 真是 xwlj 。

lyd 的 C 莫名其妙被 Skipped 了……于是 #35

然后我就很奇怪为啥 FredaShi 为啥每题都交的比 lyd 慢。

wyl8899、squarefk 都是前三题。wyl8899 的 D FST 了。

秋锅只过了两题。B 1A 分数比我还高= =

a142857a FST * 2 真是太令人桑感了。

nonsense

最近 我/主席/xiaodao/Seter/7k+ 几个商量再出一场 CF ～

当然 idea 有限，时间也是个问题～