Traveling
T399742 Ting'er loves traveling 题解
Link T399742 Ting'er loves traveling Question 给出一个图,使得 \(1\) 到 \(N\) 的路径上的最大值最小 Solution 看到最大值最小想到二分,二分最大值 \(top\) 然后去 check 验证能不能从 \(1\) 走到 \(N\) Cod ......
题解 P9695【[GDCPC2023] Traveling in Cells】
显然,询问的答案即为 \(x\) 所在的极长的满足颜色均在 \(\mathbb{A}\) 内的连续段的权值和。如果我们能维护对颜色的单点修改,以及求出某个位置所在极长连续段的左右端点 \(l,r\),只需要树状数组即可求出答案。 一个朴素的想法是对每种颜色开一棵线段树,单点修改是平凡的,极长连续段左 ......
CF1869B 2D Traveling
思路 首先思考,除了 \(a\) 和 \(b\) 我们不应该到达任何非主要城市。 理由很简单,两点之间线段最短,如果我们目前要从 \(u\) 前往 \(v\) 且 \(u\) 和 \(v\) 不都是主要城市,即 \(u\) 到 \(v\) 需要花钱,那么如果再选择一个不是主要城市的 \(k\),那么 ......