2022-08-07

When You Know That There's No Tomorrow - NOI 2022

省流：100+95+15+10+100+40+0=360 Ag。

CF1163F Indecisive Taxi Fee 题解

在改边权之后，可以将所有路径分为经过修改的边和不经过修改的边两种。经过修改的边的所有路径的最小值是容易计算的。具体来说，设修改的边为 $(u,v)$ ，修改后的权值为 $w$ ，则预先从 $1$ 和 $n$ 分别跑一遍最短路，假设求出的数组分别为 $d_1$ 和 $d_n$ ，然后答案就是 $\min\{d_{1,u}+w+d_{n,v},d_{1,v}+w+d_{n,u}\}$ 。

因此只需要考虑不经过修改的边如何做，转化为删 1 条边。

洛谷 P3352 [ZJOI2016] 线段树题解

对于一个数 $i$ ，考虑它左边第一个比 $a_i$ 大的数的位置 $L$ 和右边第一个比 $a_i$ 大的数的位置 $R$ ，显然在操作过程中，这两个位置都会逐渐向 $i$ 紧缩。但是我们无法得知紧缩的过程中这两个位置的值是多少，因此并不能计算出答案。