AB 不写了
ABC257C Robot Takahashi
按照 \(W_i\) 排个序，算一下前缀后缀 1 和 0 的个数就行了。答案大概是一个 \(\text{max}(p_i+s_{i+1})\) 的形式。
有一个小细节：排序之后 \(W_i=W_{i+1}\) 时无法在 \(i,i+1\) 之间断开，要特判。我因为这个 WA 了一发。
AC Code
ABC257D Jumping Takahashi 2
二分答案，然后暴力建图 dfs 就行了。\(O(n^2\log V)\)。注意二分的右端点不能太小也不能太大。我思考了一下感觉至少要开到 \(4\times 10^9\)，然后无脑开了 \(10^{14}\) 结果一下子爆 long long 了，又 wa 了一发2333
AC Code
ABC257E Addition and Multiplication 2
我们发现如果确定了每个数 \(i\) 要买几个，那么最优方案肯定是从 \(9\) 到 \(1\) 一个一个放下来。
因此考虑用一个长度为 \(9\) 的 vector 来表示每一个数字选了多少个，然后随便 dp 一下就行了。
时间复杂度 \(O(n\times 9^2)\)。感觉看代码更好理解：AC Code
ABC257F Teleporter Setting
考虑新建一个假的点 \(S\)，对每个 \((0,v)\) 的边连边 \((S,v)\)。
现在相当于对每个 \(i\) 要算出来如果加上边 \((S,i)\) 之后 \(1\to n\) 的最短路。
这个是经典问题，直接正反跑两遍单源最短路算出来 \(f,g\) 表示 \(1\to i,n\to i\) 的最短路，那么答案就是 \(f[n],f[S]+g,f+g[S]\) 中的最小值。本题中边权都是 \(1\)，直接 BFS 即可。复杂度 \(O(n+m)\)。
AC Code
后记
《五彩斑斓的世界》
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
