「JOI 2020 Final」题解

题目地址：

LOJ3252~3256

先把a、b分开排好序。

不难想到最优的方法是直接对应匹配。

所以每一个a[i]只会和b[i]或b[i+1]匹配。

a[i]和b[i]匹配适用于挖的点在i之后。

a[i]和b[i+1]匹配使用挖的点在i+1之前。

于是顺着扫一遍，维护一个堆以找最大的a-b。

发现代价是(max-min+1-3k)，所以就是要最小化(max-min+1)

考虑记f[i]为，以i位置为第k个J时，第1个J在哪儿。

记g[i]为，第i位置为第1个I时，第k个I在哪儿。

枚(i)，满足有(f[i])的存在，再找到一个最小的(j)，使(i+1..j)中的O的个数(>=k)，(ans=min(ans,min(g[u])(uin(j,n])-f[i]+1-3k))

(f[i]、g[i])扫一遍用个栈就能预处理。

j显然是随i单调而单调的，预处理个前缀和即可找到j。

再对g进行后缀min处理即可找到(min(g))。

设(f[i][j][k][0/1])表示搞定了环上前i个和环上后j个，收集到了k个，现在在环前还是环后的最小时间，转移显然。

考虑枚举每一条将其反转，求答案。

现在要求的是1~n不经过(u,v)或者经过（v,u）的最短路。

A.不经过(u,v)的1~n最短路

考虑(u,v)若在以1为开头的最短路树，就重新跑dij，否则就是原图的答案。

B.经过(v,u)的1~n最短路

即1~v不经过(u,v)的最短路+u~n的不经过(u,v)的最短路+d

1~v的同A的做法。

u~n的即(u,v)在n为起点的反图最短路树上，就重跑dij，否则就是原来的答案。

n~1的答案同理。

注意到最短路树上只有(O(n))条边，所以最多重跑(O(n))次dij，复杂度(O(n^3))

我的想法很不清真。

考虑连续相同的缩成一段。

记f[i]表示第i段的值是否大于第i+1段的值。

注意f如果有这样的01111…0的情况，那么每次时间+1时，第1个1那一段长度+1，最后一个0那一段长度-1.

直到最后一个0那段长度变为0，需要把这一段删除，那么当前状态就会发生改变。

考虑用平衡树维护，每一段的长度是和当前时间有关的一个一次函数，和也是，那么只要维护这两个的子树和，就可以查询答案。

在每个会发生状态改变的时间打tag，因为只会涉及最近的几段，所以讨论一下即可。