Codeforces-172 出题感想

第一次参加 CF 的出题，感觉蛮好的……

虽然我打了一圈酱油啊！啥都没做啊！

Solution

2A --- xiaodao

你还想要有多水？

2B --- roosephu

普通青年：枚举分母。

文艺青年：连分数展开。

二逼青年： Fraction(x,y).limit_denominator(n)

2C/1A --- xiaodao

普通青年：暴力半平面交

二逼青年：暴力推公式

文艺青年：跳掉不做

要我的话还是半平面交吧，虽然这样也要推一些公式 T_T

2D/1B --- roosephu

这个题是我从耀爷那里蒯来的，结果没想到成为最水的题了……

一个结论就是最大值/次大值对只有 O(n) 个，用单调队列处理出来就好了。

感谢大叔提供了几个好数据～

有谁看得出这题是我出的么……其实我还黑了人的，只不过黑得很不明显罢了，连某热衷于黑我的小朋友都没看出来。

2E/1C --- WJMZBMR

答案就是每个点的深度的倒数和。（根的深度为 1）

证明嘛，我还不会一个显然的证明，但是我找规律找出来是对的。

有一种理解是这样的：我们考虑每个点，这个点只有在选择某次其祖先的时候才可能被删，选中自己的可能性是 1/dep(i) ，也就是这个点对答案的贡献期望是 1/dep(i) ，又由于每个点对答案的贡献是独立的（这点怎么看？），所以直接加起来就好了。

1D --- fotile

来自 fanhq 的加强版。

对于一个序列，求 k-MSS ，我们可以用网络流来做：一条链，限制流量为 k ，跑最大费用最大流。

这不是比暴力还慢么！注意到每次增广的特殊性，一定是选择一个区间，取了其中的值，然后区间取反。线段树维护即可。当然由于维护的信息比较多。要支持取反于是要还要记录最小值，还要顺便记录答案，比较麻烦。

于是就 O(n k log n) 了……

这个题居然被水过去了，坑爹啊……算了算了还是那句话：暴力能水过去也是他的能耐嘛。

1E --- fotile

主席的加强版的弱化版。（一种蛋疼的忧桑？）

做过原题的话应该知道用折线来刻画 dp 值这方法。对原题来说令 f[i][j] 表示第 i 个数为 j 时的最小代价和，可以知道 f 是一条折线，且只包含 O(i) 条线段，于是我们维护 f[i] 所表示的折线，递推出 f[i+1] 的折线。事实上这个方法是可以推广的，不过在这个题上是用曲线来刻画。曲线不好表示是吧，于是考虑维护曲线的导数。

维护了导数，找最小值也好找了，直接求与 x 的交点即可，方程也可以维护了。由于 n 只有 6000，暴力维护即可。当然你要有能耐的话可以用平衡树维护，保证复杂度 O(n log n) ，不过略难写。

procedure

一开始是在 G+ 上，主席说要给 CF 出题赚外快，于是我就回了句 bg ，然后就被主席拉过来出题了。

YY 能力完全不够啊。幸亏最难的几个题主席都已搞好了，于是我和 xiaodao 专注水题三十年。小岛出的 2A & 1A ，我出的 2B & 1B

一开始出 2B 的想法是要给一道水题是吧，然后瞬间想到 Python.fractions.limit_denominator 。当然连分数展开是果断不可行的，于是暴力枚举分母即可。

1B 的来源是耀爷讲课时的某题，我就直接蒯了下来～Gerald 好像搞了个很复杂的方法的说，其实就是个水题嘛。

一开始 1B 想出最大值除以次大值，后来想把数据出强一点，于是写了个 cheater 发现全部骗过去了，后来才发现如果是除以的话，答案一定是相邻两个数的商……宇宙大水题啊……

出题是放在 Polygon 上。真心是个专业网站，自带版本控制，用起来非常方便。里面有 invocation 用来测试数据，gen 建议用命令行做初始化，可以用脚本来生成数据，validator 检验特严格，一个字符都不能多，checker 感觉很松的，package 可以下载这个题目的所有相关信息，题目支持部分 TeX 语法真是太好了。幸亏前一段时间用过 git ，对版本控制还是有点理解的，用起来不难。唯一需要吐槽的一点，就是你必须等网页缓冲完毕后再点击超链接，否则会直接回到首页，蛋碎的感觉……每次 commit 都会发一份邮件，所以这几天被轰炸了不少。

主席某天突然之间就住院了，一开始我也不知道是啥情况，但是似乎很严重的样子。于是他的题就被分了，我、xiaodao、Seter 一起搞。我写了 E 的 cpp 以及 java ，慢出翔了，后来还是用的 Seter 的 java 。不过我写的 D 的 java 倒是跑得蛮快的样子。时限要求为 java 的两倍还真是蛋疼。为了照顾 Java 我不得不优化常数，结果最后和 xiaodao 一商量决定把时限开为 5s ，于是就有人水过了 T_T 其实我觉得 n 开小 k 开大蛮好的嘛，CLJ 说限制 k 的和也是可以的，这样更好卡了。

在比赛的前几天，突然得到消息说 C 冲了，于是怒 YY 题目。刚好做了一个 Project Euler 的题，于是 YY 出一个题，但是被 CLJ 抢得先机用了他的题。没关系下次再用嘛。

于是这场比赛的 problem setter 真是多，xiaodao、我、CLJ、fotile、kissbuaa ，另外 Seter、7k+、pashka、Gerald 来验题，规模也算得上庞大了，于是有人怒吐一槽：

话说现在 WJMZBMR 与 Petr 正大战三百回合，有兴趣的同学可以去围观。

然后晚上本来不打算围观了的，因为没人做，但是跑回寝发现大叔在做，于是怒围观。Seter、xiaodao、CLJ 开了语音，我和 7k+ 俩人就只好打字了……好苦逼。

于是讨论组里面的人全部开了上帝视角，成了权限狗。期间由于 XLk 突然之间回话了所以和 XLk 聊了一下天，他好久不回我了 T_T

发现 div2 的题超水，3min 左右 400+ 人过了 2A ，太可怕了。然后继续有人过 2B 。我很想不通那些过了 2C 没过 2B 的人是啥心态……我更想不通居然没人用 limit_denominator 来做，我还想不同有人用 Fraction 构造分数的时候用了小数从而精度有 bug ，我最想不通一堆人说这题精度太紧了太紧了。明明 Gerald 说这题太水要把数据组数减小的……

居然有人 5min 内过了 1A ，真是太令人惊悚了。我还看到若干个纯代数流，太可怕了。由于 1A 题过难，导致 1B 被迅速秒，成为这次 CF div1 AC 人数最多的题。

wuzhengkai 和 watashi 俩人同时在 33min 过了 A ，死磕着 A 不放干啥嘛，A 明显是用来坑人的。（wzk 的人人头像越看越觉得萌 = =||）

比赛的时候一堆人问 excluding OR 是什么意思。我明明记得我原题写的是 XOR 啊，那个英文翻译改成了这个东西真是蛋疼……偏偏样例精心手构答案是 7 和 15 无论 or 还是 xor 都可以解释。不过明明题目是 XOR 样例解释是 XOR 你还有什么问题吗？

哇卡居然有人交了 E ？WA pretest 2 连样例都过不了囧爆了。讨论组里面没人认为有人可以 AK 。

然后在 1h5min 有人过了 E 的 pretest ？为了和谐 pretest 是直接上了极限数据的，人民群众喜闻乐见欢兴鼓舞拍手称好。然后 Seter 拿过去一测发现可以 A 。经仔细研究后发现这个算法是错的……于是 Seter 出数据开始卡发现稍微一卡就可以卡掉了……结果一场腥风血雨在 CLJ 和 Petr 展开……再一看这个人还只交了 E ？果 E 大神！他的 AB 是后来才写的，太强大了……

大叔 YY 了一个 1B 算法，于是交了一次发现是错的，然后再交一次，于是我求数据加入 tests ，然后又写了个 gen 来生成类似的数据，似乎卡掉了一些人的样子。

D 题居然有人写正解！UESTC_Nocturne 太强大了……不过这个题被 liouzhou_101 骗过去了还真就不甘心呢。但是时限放的太宽卡不掉真是蛋疼呢。

之后一堆人在吐槽说 div2 的题太难了太难了太难了，你想要我做什么表情？

这次 CF 成功把 tourist 拖下 3k ……只要拼了前三题的手速就不会太差，后两题基本上没人过的。

nonsense

好吧就是这样，感觉蛮好玩的呢。

骗钱向：以后有谁要出 CF 了我可以过来打酱油啊，专业酱油三十年。