## 最长上升子序列 #序列dp 最开始我想到的是动态维护最长上升子序列，但是每次新加一个元素可能导致原来的嘴馋上升子序列中的所有元素都失效，所以做不了。 然后我又想到动态维护 dp 数组，每次解禁 $k_i$ 就考虑 $k_i$ 前面的哪些状态可以转移到 $dp_{k_i}$，然后 $k_i$ 又能转移到后面的哪些地方去，但是维护动态的前缀的信息我根本不会，也不知道如何往后转移。 当我看到排列时随机生成的时候，我猜测 LIS 序列的长度期望是 $\sqrt n$ 的，但是我的代码一直是基于原序列而不是 LIS 序列的，所以我认为这个条件是用不上的。 接着我就想到从值域进行处理，对值进行排序然后其次考虑下标的单调，但是本题是排列，值域和 $n$ 是一样的所以也无法解决这个问题。 最后我想到了反着进行操作，即最开始全部都是解冻的，然后倒着操作每次冻结一个元素，如果当前影响到了 LIS 序列那么就重构 LIS 序列，否则不动。但是我觉得如果每次都冻结 LIS 序列上的元素，那么这个算法就会被卡掉。 此时我就跑去写第二题了，后来这道题目就交了一个每次进行操作就重新跑 LIS 的 $\mathcal O(n^2\log_2 n)$ 暴力程序。 后来赛后才恍然大悟，期望长度 $\sqrt n$ 的 LIS 就意味着每次进行冻结操作大约只有 $\cfrac{1}{\sqrt n}$ 的概率冻结到 LIS 序列中的元素，所以最终重构次数大约是 $\sqrt n$ 次，而每次重构的时间复杂度是 $\mathcal O(n\log_2 n)$ 的，本题的 $n$ 又是 $\le 50000$ 的，因此我之前想的 LIS 序列被冻结就重构的算法的时间复杂度是正确的。 ## 消除序列 #线段树 #平衡树 最初我想的是枚举左边界，不断往右边拓展。如果两个元素 $(a,b)$ 在我们需要删除的子数组的最前面的话，那么就需要把它们一起减掉 $\min(a,b)$。但是当 $b>a$ 时，$a$ 会留下一定值，然后往后走 $a$ 就删不掉了，因此 $a\le b$ 是必须的，于是我们就把 $a$ 和 $b$ 同时减去 $a$，$a$ 没了，$b$ 剩下 $b-a$，这个 $b-a$ 又会变成下一步的 $a$，和下一步的 $b$ 继续删除。 因此就得到了暴力算法：枚举左边界 $i$，然后往右扫 $j\in[i,n)$，初始化“上一个元素的剩余”$lst=a_i$，每次让 $lst=a_{j+1}-lst$，当 $lst=0$ 时就代表这一段删空了，就可以记录答案了。需要注意的是，如果 $a_{j+1}<lst$，即上述的 $a>b$，那么就需要 `break`，因为此时把 $a_{j+1}$ 删成了负数。 然后我就考虑如何优化这个操作。显然 $lst$ 会影响我们的答案，因此把它当作状态。设 $dp_{i,j}$ 表示为以 $i$ 结尾的子数组中，最后一个元素的剩余为 $j$ 的子数组数。初始状态 $dp_{i,a_i}=0$。 转移时，加入一个新元素的话，逻辑和最上面的暴力时一样的。如果 $a_{i+1}\ge j$，那么就可以从 $dp_{i,j}$ 转移到 $dp_{(i+1,a_{i+1}-j)}$，然后累加就行了。最后答案就是 $\sum\limits_{i=1}^n dp_{i,0}$。 但是 dp 状态的第二维和值域有关系，而值域有 $10^9$，所以第二位用 map 存。时间复杂度 $\mathcal O(玄学)$，不过推测应该是最坏 $\mathcal O(n^2\log_2 n)$。 交上去跑大样例跑得飞快，空间也没用多少。结果最后因为开了 map MLE 了。即使我后来加上滚动数组优化，我的算法仍然会 TLE。 看来我需要优化算法。我的状态有很多是冗余的，因为它们最后达不到 $0$，无法被统计到最终的答案中；但是抛弃它们是不行的，因为它们也有可能会参与到最终答案的统计中。转移是无法被优化的，因为已经是 $\mathcal O(1)$ 的了。 所以最后我开始找规律。如果一个子数组 $[l,r]$ 满足条件，那么首先需要满足 $a_{l+1}\ge a_l$，然后 $a_{l+1}$ 被减掉之后需要满足 $a_{l+2}\ge a_{l+1}-a_l$。以此类推，就可以得到对于 $[l,r]$ 的任意前缀 $[l,m]$ 满足 $a_m-a_{m-1}+a_{m-2}-a_{m-3}\cdots\ge 0$。最后还需要保证可以删成 $0$，也就是删到最后的 $a_{r-1}=a_{r-1}-a_{r-2}+a_{r-3}-\cdots =a_r$，也就是奇数下标的和等于偶数下标的和。 所以我们就动态维护所有的左边界的合法性，即维护 $a_r-a_{r-1}+a_{r-2}\cdots$，如果右侧新加入了一个元素就是对其进行取反再加上 $a_{r+1}$。这肯定不可能对于维护的每一个元素都进行操作，但是作用的对象时全局，所以用一个辅助变量。查询时相当于做一个差分，查询相减正好等于 $0$ 的满足条件的左端点。 需要注意的是，这道题目虽然合法是没有单调性的，但是一定不合法是有单调性的。如果一个地方中途断了（即减成了负数），那么继续往后是无意义的。所以这里用 set 维护的时候也是需要进行 erase 操作的，每次移除会减成负数的元素，这些元素到后面也是无意义的。这样就可以用 $\mathcal O(n\log_2 n)$ 的时间复杂度解决这个问题。 ## 本质不同 01 串 #序列dp 由于我去写 T4 了，导致本题连骗分代码都没有写。不过这道题目确实思维太巧妙了，我赛时如果没有写 T4 写这道题应该也是不可能想到的。 ## 树上价值 #费用流 #贪心 最开始觉得是树形 dp。 首先价值都是正的，因此不可能出现一个节点既没有被选择价值又没有被禁用的情况。如果 dp 第二维是 0/1 的话，不足以支持题目要求：子树内距离小于等于 $k$ 的都无法被选择。 所以考虑把禁用距离的 $k$ 加入状态。设 $dp_{i,j}$ 表示为对于 $i$ 的子树内，距离 $i$ 小于等于 $j$ 的节点无法被选择，所获得的最大总价值。这个 $j$ 的限制可能来源于 $i$，也可能来源于 $i$ 的祖先，但是这不要紧。 转移时，只需要对于每一种可能的 $k$ 进行遍历，儿子的 $k$ 限制在父亲这里可以是小于等于 $k-1$ 的任意值，这样父亲的限制不会影响到儿子的限制，因为儿子的限制域比父亲深。 这样子做的时间复杂度最坏是 $\mathcal O(n^2\log_2 n)$ 的，但是我们同样可以用 map 的套路优化成 $\mathcal O(玄学)$。需要注意的是一个节点可能有多个限制，所以对于同一个节点中的多个限制要按照 $k$ 从大到小的顺序做后缀和记录。 我 WA 的原因是因为对于父亲的 $k$ 状态，到儿子那里是 $k-1$ 状态，但是如果儿子没有 $k-1$ 状态就很麻烦，因为我默认的本节点的所有状态都是和本节点的 $k$ 有关的。其实这可以通过一些特殊手段解决的，但是我没有解决成功，所以就炸了。 本题的正解是网络流建模+模拟费用流，但是我今天在补 T1 和 T2，所以只能后面再去了解。 ## 总结 分数：$50+45+0+10=105$ 我应该额外思考均摊的复杂度，注意到题目中的 **随机生成** 的数据，还有 T2 不要因为出题人给的大样例太小在 map 的 dp 中迷失了自我，它的复杂度是有问题的，应该额外探寻满足条件的子数组的规律，T4 也应该更加理性地调试，其实我中途半个小时都在调的错误是没加 long long，应该更加专注地调试，利用好每一分钟。