这是本文档旧的修订版!
今日仅有chy和lbn两个人参赛
C题,lbn出思路后,告诉chy,让chy写代码,但是没有沟通清楚边界的情况,相同也算“下降”,因为可以维护长度为2的后缀,导致多wa了一发。
H题chy的做法大致正确,但是第一发写错变量wa了,然后lbn尝试两发漏了一些边界,最后chy改对变量成功ac。
J题,chy想出了基于点的最短路思路,lbn写完提交后wa,发现dijkstra提交后还是wa,然后发现中途可能爆LL提交还是wa。随后发现做法错了,环的情况可以hack做法,改成基于边的做法后,chy提交ac。 题,chy单独出思路,写完一发ac。
F题,lbn单独出思路,但是写完wa。数组没开过又wa了一发,另一个原因是multiset删除一个元素,直接用erase,以至于wa了好几发。最后chy过了K题之后,纠正了multiset的问题,lbn修改后ac。
K题,chy单独出思路,倍增数组写反了,但是还是过到30个点。发现bug后成功ac。
今日三人均参赛
前期签到题,J题,chy提交后发现写错一个变量,多wa一发。
I题,lbn写完二分后,发现TLE(实际上check函数可以优化到O(1),写法为最坏情况是值域),然后chy写了个贪心过了。
K题,思路比较显然,lbn和chy都一眼,然后chy负责写字符串,最后找到bug在4发提交后ac,(中途甚至还交错一版代码)。
D题,chy在线段树求区间众数的模板上小修改了下,然后提交。(但是线段树写假了,down(mid)标记下传,最后修改后成功ac)。
B题,chy和lbn讨论许久,显示基于生成函数的思路,一步步化简,发现分母为分拆数的生成函数,然后去翻阅材料,找到五边形数。不过题目模数是1e9+7,无法使用ntt,猜测大概率需要用dp或者其他思路来模拟多项式。lbn帮chy算了下组合数求和的公式,于是此时只有双指针O(T N)的做法,依旧没法ac这道题目。chy发现了⇐ n的最多只有 esqrt n个位置的值非0,基于这个性质队伍进一步思考,尝试求解Tsqrt n的做法。在五边形数的基础上,需要扣除掉多算的一部分,这一步chy单独想明白了,就是在之前lbn求完的那个组合数再求一次前缀和。然后开始写代码,发现第三个样例过不去,随后发现chy的推导过程中系数搞反了,然后修改正负号后,成功ac。
H题,数据库大模拟题,碰巧ybh读研的任务就是数据库相关,前几天刚好写这一类,于是ybh写完后提交,发现RE,数组没开够再提交一发TLE,然后改成字符串引用后,还是TLE,最后改成字符串哈希后AC。
最终本场排名来到第一名。