炼石计划 10 月 01 日 NOIP 模拟赛 #7【补题】 - 比赛 - 梦熊联盟 (mna.wang)
复盘
T1 一眼不会。先打了前 \(30\) 的爆搜。虽然这个爆搜假了但是最后也没管它。
后面的暴力分挺多。先往后做。
T2 \(2^{2n}\) 的暴力可以过 \(20\)。\(n=16\) 的特殊性质可以 \(3^n\) 枚举子集过。想冲一冲正解但是被 \(k - i \subseteq j \subseteq k\) 卡住了。放弃。
T3。有极其容易的 \(55\) 分。打了。感觉这样的神秘图论题一定做不出来就放弃了。谁知道这是个披着最短路外壳的 ds 题。
T4。又有极其容易的 \(50\) 分，直接不给我思考的机会了。打完后会 T1。
发现每次操作实际上就是在图上选择一个环然后删掉（这么简单的结论我竟然想了这么久）。最多有 \(\mathcal O(m)\) 个环，有向图找环也是 \(\mathcal O(m)\) 的，总复杂度 \(\mathcal O(m^2)\)，而且远远小于这个值。实现的好一点或许能过。
写。加了一些玄学方法后输出与大样例完全一致。于是卡常。最后 0.6s 过的大样例。
预计 \([60,100]+40+55+50=[205,245]\)，实际 T1 AC，T3 \(50\)。原因是 T3 的数据错了。所以说没挂分。
总结
好的：
-
没有挂分；
-
卡常能力很强；
-
时间分配较恰当。
题解
A. 公司的供应链
注意到我们只需要每次在图中找到一个环然后删掉，直到找不到，这样剩下的图就是答案。
最多有 \(\mathcal O(m)\) 个环，有向图找环也是 \(\mathcal O(m)\) 的，总复杂度 \(\mathcal O(m^2)\)。考虑优化。
注意到一条边被访问多次是没有意义的。一条边访问后，直接将这条边删掉即可。复杂度 \(\mathcal O(m)\)。
C. 舰队的远征
快进到求：
\[\min_{1 \le i,j \le n} a_i + b_j + (i - j)^2 \]显然 \((i-j)^2 = i^2+j^2-2ij\)。令 \(c_i = a_i + i^2,d_i = b_i + i^2\)，则上式等于：
\[\min_{1 \le i,j \le n} c_i+d_j-2ij \]不妨枚举 \(i\)。此时我们希望快速求出：
\[\min_{1 \le j \le n}d_j - 2ij \]我们对于每个 \(j\)，建一条直线 \(y = -2xj+d_j\)（即 \(y = kx + b\)，其中 \(k =-2j,b=d_j\)）。那么上面的过程相当于在这 \(n\) 条直线中，选择一条当 \(x = i\) 时最高的函数。李超线段树即可。
标签：le,min,复杂度,50,2ij,10.17,mathcal,模拟 From： https://www.cnblogs.com/2huk/p/18472762