T1 「JOI 2021 Final」有趣的家庭菜园 4

显然我们先求\(A\)数组的差分

那么显然最后就是要让一段前缀的差分\(>0\)，剩下的\(<0\)

不难发现一个操作是让至多一个差分\(+1\)，至多一个差分\(-1\)

于是枚举波峰算两侧所需次数的\(max\)即可

code

T2 「JOI 2021 Final」雪球

显然每个雪球的覆盖雪的范围是一段包含自己但不会超过他上一个/下一个点的区间

直接记录前缀最大/小值就能二分出区间的左右端点了

显然可以\(O(nlogn)\)但是懒人就是要\(O(nlog^2n)\)

code

T3 「JOI 2021 Final」集体照

注意到关键的条件就是所有人的身高构成排列

于是最后的状态里

必然存在\(T\)个区间\([l_1,r_1],[l_2,r_2]....[l_T,r_T]\)

满足\(l_i=r_{i-1}+1\)

且\([l_i,r_i]\)里填的数恰好是\(r_i\)到\(l_i\)依次递减

考虑一种最终的状态\(b[1..n]\)的贡献

假设原来的\(i\)在\(p_i\)位置

那么次数就是\(\sum_{i=1}^{n} \sum_{j=i+1}^{n} (p_{b[i]}>p_{b[j]})\)

于是设\(f[i]\)表示以\(i\)为某个区间结尾的最小代价

转移就枚举最后一个区间的长度，用树状数组转移即可

code

T4「JOI 2021 Final」机器人

不难发现如果我们想要通过一条边只有两种选择

\(1\)、把他的颜色换成一种新的颜色

\(2\)、把所有和他颜色相同的换成一种新的颜色

于是建边为两者的最小值dijkstra即可

发现有一种特殊情况

就是我们连续走过两条边，在上面分别用\(1\)和\(2\)操作，如果两次操作的边颜色相同，不难发现这样算会多算一次第一条边的贡献

于是我们对于每条边拆出一个点，\((u,v,c,p)\)就拆出\((v,c)\)这个点

抄张图

设\((u,0)\)为原图中的\(u\)这个点

把\((u,0)->(v,c)\)连费用为\(0\)的边

\((v,c)\)向所有\(v\)能通过颜色\(c\)到的点连上那条边只有\(2\)操作的权值

不难发现\((u,0)->(v,0)->(w,0)\)先\(1\)再\(2\)且颜色相同就变成了

\((u,0)->(v,c)->(w,0)\)

答案就算对了，并且不会增加新的转移方式

code

「JOI 2021 Final」地牢 3

不难想到一个贪心策略