【24.5】

题目

出题人题解

anon的私货

思路：设 $a_i$ 左右插入 $x_i,y_i$ 个 0，那么对每个 $i$ 需要保证 $a_i\ge x_i+y_i$ ，即可满足题意。

证明：

1. $a_{i+1}\ge x_{i+1}+y_{i+1}\to a_{i+1}\ge x_{i+1}$
2. $x_i+a_i+y_i\ge 0\to x_i+a_i+y_i+x_{i+1}+a_{i+1}\ge 0$

以此类推。

AC代码：https://www.luogu.com.cn/paste/lha4jzd7

mutsumi的排列连通

思路：这题更考察对 corner case 的处理。先特判 $n\le 3$ 。对于 $n>4$ ，容易知道答案上界为 2 。先特判是否有删除 1 次的方案，否则容易知道 2 次（即删除某对 $a_i,b_i$ ）肯定能满足题意。

AC代码：https://www.luogu.com.cn/paste/9p926ykp

sakiko的排列构造（hard）

思路：转化为配对问题。然后，找到和 $n$ 配对的最大正整数 $l$ ，使得 $[l,n]$ 内配对，转化为子问题 $[1,l-1]$ 。不会证明正确性。

AC代码：https://www.luogu.com.cn/paste/smbpujtn

oyorin的数组操作（hard）

思路：做了很长时间，感觉思路不是很清晰。首先排除掉 n 为奇数时的末尾值，考虑答案上界，为 ${\max }_{i=2}^n(a_{i-1}-a_i)$ 。这个上界的等号是恒可以取到的（不知道为啥）。如果 n 是奇数，要提前判是否有解。从大到小枚举前缀，能取多大取多大。容易知道如果有解，那么最后不存在逆序对。枚举过程中如果出现逆序对则误解。

AC代码：https://www.luogu.com.cn/paste/m9bmg0k7

tomorin的字符串迷茫值

思路：我先想的是 kmp自动机解法，但麻烦。看题解了解了此思路：只有"mygo"，“m_ygo”，“my_go”，“myg_o”，“m_y_go”，“m_yg_o”，“my_g_o”，"m_y_g_o"这 8 种子串可以通过删除得到"mygo"子串。枚举即可。

AC代码：https://www.luogu.com.cn/paste/kakvoq53

soyorin的通知

思路：先考虑这样的一个选择序列：$p_1,p_2,\cdots ,p_k$ ，首先存在若干长度的前缀使用操作一。接下来，剩余的后缀是一定可以衔接上的，因为 $b_i\ge 1$ ，也就是说，只要对某个 $j(j\le [2,k])$ ，前边选过了一些节点，那么 $p_j$ 是一定被前边的节点选上的，而不存在任何限制。

这样的话，枚举操作一的次数，然后完全背包即可。

AC代码：https://www.luogu.com.cn/paste/skya0udb