「CF1695C」Zero Path

hongzy · 2022-06-22 11:28:29 · 题解

感觉题出的很小清新，符合我的审美，所以来写一个题解。

用 bitset 过题，比赛时节约思考时间写就算了，考后补题写这个简直是亵渎。

首先我们给出结论，我们要找一条权值和为 0 的路径，只需找到权值和最小和最大的路径对应权值，记为 l,r，那么答案是 YES 当且仅当 l\leq 0 \leq r。

下面是简单的证明。

首先如果路径长度 n+m-1 是奇数，答案是 NO。

否则我们用 R 和 D 来记录一条路径。注意路径长度是 n+m-2，并且 R 的数量是固定的 n-1。那么权值最小的路径和最大的路径可以用序列 p_1,p_2 表示。因为元素集相同，很明显我们可以从 p_1 开始，通过不断交换两个相邻的 RD 来得到 p_2。我们思考一下交换 RD 意味着什么，就是先右后下和先下后右的区别。那么每次交换路径权值可能 0,+2,-2。既然最后路径权值从 l 变成了 r 并且我们限制了奇偶性，那么一定中间经历了 l,l+2,\cdots,0,\cdots,r-2,r 这样的过程。于是得证。