JOI 2020 Final 选做.
長いだけのネクタイ / Just Long Neckties / 只不过是长的领带
先将 $A,B$ 分别从小到大排序.
在去掉一个 $A_i$ 之后,显然最优的方案是将剩下的每个位置依次匹配.
不难发现此时 $[1,i-1]$ 内的 $B_x$ 匹配的都是 $A_x$ ,而 $[i,n]$ 内的 $B_x$ 匹配的都是 $A_{x+1}$ .
分别预处理前后缀奇怪度的 $\max$ 即可.
JJOOII 2
在原串中选出一个合法的子序列做为最后保留的部分,需要最小化这个子序列首尾距离.
预处理每个字符向后能找到的第一个相同字符,以及连续选 $k$ 次相同字符后在什么位置,枚举子序列起点即可.
スタンプラリー 3 / Collecting Stamps 3 / 集邮比赛
在任意时刻,已经到达过的点一定是在环上包含起点的某个区间.
设 $dp(i,j,v,0/1)$ 表示已经到了前 $i$ 个点和后 $j$ 个点,收益为 $v$ ,停留在第 $i$ 个点 / 第 $n-j+1$ 个点的最早时间.
オリンピックバス / Olympic Bus / 奥运公交
建出 $1$ 为源, $1$ 为汇, $n$ 为源, $n$ 为汇的最短路树.
翻转一条边的方向时,若它不在最短路树上,则只可能经过它反向后的边,或走原最短路.
若它在最短路树上,就暴力重新计算 $1\to n,n\to 1$ 的最短路.
最短路树上的边数是 $O(n)$ 的,由于点数小,边数大,每次重新计算最短路时 $O(n^2+m)$ 暴力 Dijkstra.
时间复杂度 $O(n^3+nm)$ .
火事 / Fire / 火灾
二维数点好题.
若一个位置的权值由 $a$ 变为 $b$ ,本质不同的 $a\to b$ 最多只会有 $n$ 种,因为每个位置只会被左边第一个更大的覆盖掉.
为了方便,我们统一规定若相邻两个位置权值相同,仍然认为前面的数较大,即可以完成覆盖.
单调栈求出 $L_i,R_i$ 分别表示 $i$ 左边,右边第一个比 $i$ 大的位置,那么所有的 $a\to b$ 本质都是 $S_{i}\to S_{L_i}$ 的形式.
考虑 $S_i\to S_{L_i}$ 发生的时间,不难发现对于 $j\in[i,R_i)$ 的每个 $j$ ,这个过程会在 $j-L_i$ 时刻发生.
这会使得 $p\in[i,R_i),t\ge p-L_i$ 的 $S_p(t)$ 的值加上 $S_{L_i}-S_i$ .
把 $p,t$ 看作平面上的两个维度,则每个 $i$ 的贡献是给一个直角梯形内所有点的权值加上某个数.
假定 $p$ 是沿着横的方向, $t$ 是沿着纵的方向,则询问时会询问某一行的区间和(前缀和).
可以先把直角梯形容斥成两个直角三角形.
考虑 $\sum b_i\min(a_i,c)$ 这个式子,它表示了有 $i$ 次操作,每次给 $[1,a_i]$ 加上 $b_i$ ,最后询问 $c$ 的前缀和的答案.
不难发现直角三角形对某一行前缀和的贡献也可以表示成 $\sum b_i\min (a_i,c)$ 的形式,用线段树维护前缀和即可.