第一次出CF，第一次和ODT合作，这双份的快乐加在一起，得到的本该是双倍的快乐…

502 Bad Gateway

Emm…

Div2 A The Rank

考察加法和比较函数的使用。

复杂度: $O(n)$ 。

Div2 B The Bits

被换掉了。不是我的题。因为我原题validator(判断输入数据是否合法的东西)需要FFT，所以GG了。

这题好像就是数一下四种情况的个数分类讨论乘一乘就完了？

Div2 C/Div1 A The Phone Number

$n = 22$ 时的一个最优解:

19 20 21 22 15 16 17 18 11 12 13 14 7 8 9 10 3 4 5 6 1 2

通过Dilworth定理可以得到 $LDS$ 个数等价于最小 $LIS$ 剖分，或者直接打表/分析得到: 如果 $LIS$ 固定，那么最小化 $LDS$ 就好了。

假设已知 $LIS = L$ ，显然可以做到 $LDS = \big\lceil\frac{n}{L}\big\rceil$ 。那么枚举 $L$ 找函数 $f(L) = L + \big\lceil\frac{n}{L}\big\rceil$ 的最小值就好了。

实际上 $L = \big\lfloor \sqrt n \big\rfloor$ 总是合法的。然后构造就很轻松了，模仿 $n = 22,L = 4$ 做就好了。

复杂度: $O(n)$ 。

Div2 D/Div1 B The Wu

把字符串看成二进制数。

$Wu(s,t) = \sum_{i=0}^nw_i[s_i = t_i] = f(s \oplus t)$

$\oplus$ 表示按位异或。 $f$ 可以很轻松地预处理出来。

考虑值域分块，将数字每 $6$ 位分成一块。

$f[S_1][S_2][j]$ 表示有多少个数字满足高位为 $S_1$ ，低位满足 $f((\text{lower bits}) \oplus S2) = j$。

然后用这个数组就可以预处理出答案 $g[S][k]​$ 然后 $O(1)​$ 回答询问了。

复杂度: $O(\lvert S \rvert 2^{\frac{n}{2}}+2^{\frac{3n}{2}}+q)$ 。

Div2 E/Div1 C The Supersonic Rocket

题目实际上是在求两个点集的凸包是否同构。

标准解法: 类似于BZOJ1100，把凸包转成字符串跑KMP就好了。

逗比解法 $1$ : 因为所有点都是整数，所以旋转只可能是 $0°$, $90°$, $180°$, $270°$ 中的一个，暴力枚举判一下就好了。但这个做法是错的啊！用 $3^2 + 4^2 = 5^2$ 可以把正方形转一下。不过System Test里居然没有这个数据，大失误。

逗比解法 $2$ : 对于相等的边暴力匹配(或者直接暴力匹配?)，还是因为所有点都是整数，相等的边不会太多(当 $\lvert x \rvert ,\lvert y \rvert \le 10^8$ 时应该不到 $200$ )。

逗比解法 $3$ : …

逗比解法 $\infty$ : …

复杂度: $O(\lvert S_1 \rvert \log \lvert S_1 \rvert + \lvert S_2 \rvert \log \lvert S_2 \rvert)$ 。

Div2 F/Div 1 The Neutral Zone

先不管空间限制，考虑贡献法，一个质数 $p$ 的贡献就是:

$f(p)\bigg(\bigg\lfloor\frac{n}{p}\bigg\rfloor+\bigg\lfloor\frac{n}{p^2}\bigg\rfloor+\bigg\lfloor\frac{n}{p^3}\bigg\rfloor+...\bigg)$

(第二部分求的是 $p$ 在 $n$ 以内的数作为因子的出现次数)。

暴力求就是 $O(n)$ 的，因为只有 $O(\frac{n}{\ln n})$ 个质数而每个质数是 $O(\log_p n)$ 的。

然后考虑怎么筛质数(空间复杂度)。用埃氏筛而不用欧拉筛，这样需要记录的只有一个划去质数用的表。

用 bitset 就已经可以做到 $37.5 MB$ 。然而并不够。

核心观察: 除了 $2$ 和 $3$ 以外的质数 $p$ 都满足 $p \equiv \pm 1 \pmod 6$ 。

那么只存这些位置，就只需要 $\frac{37.5MB}{3} = 12.5 MB$ 。

需要卡常，也用这个观察卡常就好了。

复杂度: $O(n \log \log n)$。埃氏筛是复杂度瓶颈。

艹标算系列之一

据说可以分块筛。

Bonus·Div1E The Escaping Plan

给定一棵树，每个点有权值(可能为负)，求从 $1$ 号点开始走 $K$ 条首尾相接的简单路径的最大收益。每条简单路径走完以后统一计算收益(路径点权和)。要求任何时候总收益不能 $\le 0$ 。 $n \le 1000, K \le 10^6, \lvert w_i \rvert \le 10^8$ 。

核心观察: 每两步就可以跳一个环。

那么任何一个方案可以表示成: 在以点 $\alpha$ 为起点的最大收益环上条若干步，然后跳到点 $\beta$ 上。

暴力DP: $f[v][i][p]​$ 表示当前在点 $v​$ ，已经跳了 $i​$ 步，当前总收益为 $p​$ 是否可行。

根据之前的观察，$p$ 可以表示成关于 $i$ 的一次函数。要求 $\max \lbrace p = ki+b \rbrace$ ，其中 $k$ 是定值(经过点 $v$ 的最大收益环)，所以最大化 $b$ 就行了。

用SPFA或者Dijkstra跑最短路DP就可以了，每个点只会转移到斜率更大的点上。

复杂度: $O(n^2 \text{log} n)$。

抱歉这个做法是错的。并不能Dijkstra。我一开始以为我证明了每条直线的起点是无所谓的，但是其实并没有。因此直线的起点是有所谓的，是一条射线而不是直线。

所以这个Bonus problem有人会做吗？

Div1E The Tree

不是我的题。不了解。就说可以树剖或者分块。STD设置的是分块。

Div1F The Films

显然概率是:

$\frac{(mk+n-(r-l+1))^{\underline{n-(r-l+1)}}}{(mk+n)^{\underline n}} \cdot \prod_{i=1}^m (t_i +k)^{\underline c_i}$

其中 $a^{\underline b} = C_a^bb! = \frac{a!}{(a-b)!}$ ，就是下降幂。

$t_i$ 是结局 $i$ 在序列中的出现次数。

$c_i$ 是结局 $i$ 在区间 $[l,r]$ 中的出现次数。

证明:

每种颜色的某一个可以选任何一个和它结局相同的(有 $$(t_i+k)$$ 个)，然后选一个少一个，总方案就是 $\prod_{i=1}^m (t_i +k)^{\underline c_i}$ 。

然后剩下的数随便填，方案数是 $(mk+n-(r-l+1))^{\underline{n-(r-l+1)}}$ 。

总方案数是: $(mk+n)^{\underline n}$ 。

如果 $k = 0$ ，可以裸上莫队，复杂度大约 $O(n\sqrt n)$ 。更准确地说，$O(n \sqrt q)$ 或 $O(n \sqrt q\log m)$ 。

核心观察: 只有不超过 $O(\sqrt n)$ 中不同的出现次数。

证明:

最坏情况下 $1 + 2 + 3 + ... + x = \frac{x(x+1)}{2} \le n$ ，也有 $x = O(\sqrt n)$ 。

同样地，可以推出只有 $O(n^{\frac{2}{3}})$ 种 $t_i$ 和 $c_i$ 的组合。用哈希表(就是个 $O(m\sqrt n)$ 的数组)记下来，每次询问暴力就行了。

因为只有 $100$ 种 $k$ ( 记为 $K = 100$ )，暴力预处理下降幂做前面的组合数就好了。

复杂度: $O(nK+n\sqrt q+q n^{\frac{2}{3}} \log m)$ 。

实际上，如果只要维护 $\prod_{i=1}^m (t_i +k)^{\underline c_i}$ ，那么复杂度和不同的 $k$ 的个数 $K$ 没有关系。

复杂度: $O(n\sqrt q+q n^{\frac{2}{3}} \log m)$ 。

艹标算系列之二

但是因为有了 $K$ 的限制，就有一种"投机取巧"的办法: 对于每个 $k$ 跑一次莫队。调整块的大小，可以做到 $O(n\sqrt{qK})$ 。

实践中这个做法比标程还要快一些。所以卡不掉。实际上 $K$ 的限制是可以去掉的，但是为了题面的间接性、简洁性，就让这种方法通过了。我才不会说是因为标程常数太大了以至于为了Python和Java开大两倍时限太不划算了所以才让这个水过去了。

总结 & 办比赛回忆录

(倒叙预警)

怎么真的502 Bad Gateway了啊。

怎么Unrated了啊。

两道分块不是我的锅啊我也不知道啊我就出了一道啊谁知道比赛前一天临时换题啊不是我的锅啊不是我的锅啊

写点办比赛的事，如果有人想办比赛的话也许可以借鉴下。

最开始攒了几个IDEA，十分自信就交了一个Contest Proposal上去。然后还发了个博客吐槽Codeforces的审核速度。

…

审核开始， $2$ 天之内我的题大部分被否掉了。

管理员(关爱智障的眼神): “要不你办Div2 Only吧。”

我: “别啊！”

然后我在接下来的几天扔上去了十多个题吧，把攒了很长时间的家底全拿出来了。总算凑出一个Div1。

…

讲道理我自己对这次的题目质量挺不满意的，特别水。问题主要在于我说好的题管理员都说简单，我觉得简单的题管理员都说好。不是很理解外国人的审美…很多我想到的好题都没用上，反而是一些临时凑出来的点子过了。

交标程，造数据，造题面，写checker，写validator(空格、回车和换行都不忽略，读个东西就不停地 inf.readSpace() 读空格，烦死了)，写generator(还必须强行用它那个蛋疼的伪随机库，所有变量还必须取到极限数据)，写暴力，对拍…

然后管理员告诉我。

对——代——码——风——格——有——要——求！

整个人直接傻了。

“你应该一行只干一件事。”

“不要用 define 和 inline 。”

参考一下我平常的码风(这是一道LCT上维护矩阵):

简直是谋杀。

改改改

改改改

改改改

感觉没问题了。然后就进来几个人，写了一大堆形形色色的程序，告诉我:

“你要读懂这个，看看他对不对。”

“把这个暴力Hack掉。”

“把你和他的程序对拍一下。”

“我觉得这玩意就不该过样例。”

“这个明显错了，怎么就WA了3个点？”

…

然后我的D1E被Hack了。

然后Hack我的那个人的D1E被Hack了。

然后D1E就没人会做了。

然后我发现D1F有人交了暴力。

然后发现暴力跑得比我快。

调了调参。

跟他们argue了半天，到底要不要把暴力莫队放过去。

最后发现卡不掉。

然后比赛就开始了。鸡冻。

最后是Q&A段子集锦。

很好，我觉得你应该尝试Hack一下别人，看别人有没有注意到。

悲伤的故事。

如你所愿。

我可能猜到你要干什么了。

另一个截然相反的令人悲伤的故事。兄弟，您应该和那位吃晚饭的同学沟通一下。

给给？

纯属搞笑，如有冒犯，联系删除(我猜这里面没有中国人吧)

扫描二维码即可在手机上查看这篇文章，或者转发二维码来分享这篇文章: