HT-NOIP-001
T1
场上看着就像是有单调性,并且样例几乎没法隐藏正解,所以直接瞪样例 10min 切掉。补一下证明:对于层数为 \(n\),抽 \(m\) 层最大值为 \(i\) 方案数是 \(\binom{i}{m}-\binom{i-1}{m}=\binom{i-1}{m-1}\),因此期望就是 \(\sum_{i=1}^n i\binom{i-1}{m-1}/\binom{n}{m}=m\sum_{i-1}^n\binom{i}{m}/\binom{n}{m}=m\binom{n+1}{m+1}/\binom{n}{m}=\frac{m}{m+1}n\)。显然有 \(\frac{m}{m+1}\) 在 \(\mathbb{N}\) 上单调递增,所以得小的 \(m\) 配大的 \(n\) 才行。
T2
场上依然是通过直觉注意到最优解似乎是 \(n\) 和 \(n+1\) 并且总是能做到,试了一下确实如此,代码甚至可以比较暴力地模拟,然后就这么写了,大概 30min 写完。值得注意的是这题作为 SPJ 没有下发 checker,然后 checker 写挂了,然后就挂没了。对于上面的结论,其实是容易的,因为两个中位数里小的那一个一定 \(\le n\),大的一定 \(\ge n+1\),然后就证完了。
T3
先考虑性质,所有数减掉均值之后每轮都是正数给负数,“给”操作不能交叉。所以说其实就是正数之和。然后再考虑正解,显然这个和前缀和很相关,于是瞪出来了前缀和绝对值的最大值,跑完样例就知道对了。事实上可以这样想,对于绝对值大于 \(1\) 的数,可以直接拆成绝对值为 \(1\),对于一段 \(1\) 一段 \(-1\) 代价就是两段长的 \(\min\),剩下的就剩下了。这样就是不断用 \(1\) 和 \(-1\) “匹配”.找最大的一段,换句话说,就是前缀和最大绝对值。40min 切掉。
T4
性质依然是容易的,直接套一下 whk 结论或者怎么证一下都好,之后正解这个图看起来好神秘啊,没啥好的性质,大概 30min 想到了整个函数一定是凸的,所以可以套 \(n\) 层三分做到大概 \(O(\log^{16}V)\) 的东西,毛估了一下 \(\log V\) 在 \(10\sim15\) 左右,盲猜是要让 \(n\) 折半,但是没啥好的方向,直接等一下大样例发现分母分别是 \(1,2,3,7\),那还说啥了,直接猜分母不超过 \(n\),之后变成整数,直接爬山就完事了,因为这里数据范围贼小,所以没有必要允许随机性,直接一格一格爬就是 \(O(n^4V)\) 到 \(O(n^5V)\) 了。结论的证明其实是根据不取到上下界的所有数必然构成一个团这个正解结论就推出来了。
总结
虽然说瞪的结论都对了,但是以后最好是要稍微理性一点写一写或者至少想一想有没有道理再写代码,不然有可能会浪费大量调试时间。另外,checker 这类东西要先 check checker 写的对不对,比方说试几组 corner 之类的确保 checker 没问题之后可以先用一些 corner 测代码,没问题直接写 datamaker 去用最大数据拍,防一些怪错误,毕竟 checker 都写了也不差那些了(