AGC013 简要题解

[AGC013A] Sorted Arrays

直接模拟即可，让每个序列尽量长。

随便找一条边，然后两个顶点向两边拓展无法继续位置，顺序输出即可。

比较有趣熬

首先考虑一条直线，蚂蚁们在上面走，假设蚂蚁相遇并不回头，那么最后所有蚂蚁的位置和真实情况蚂蚁的位置相同，只是位置上的蚂蚁不一样。相遇可以理解为另一只蚂蚁接力跑，蚂蚁的位置顺序是不会变的，所以排个序依次分配即可。

放到圆上，依然可以直接走找到最终位置，但顺序不是很好搞了。

假设圆很大，并且蚂蚁们集中在下部，那么可以按照直线的做，如果有一只蚂蚁逆时针跨过了 0 这个点，可以发现所有蚂蚁对应的最终位置减少了 1 (mod L 意义下)，如果顺时针跨过，那么就是增加 1，所以我们可以找到 1 号蚂蚁最终对应第几大位置。

一开始读错题了，注意黑白球的数量是不给出的（给出还不是随便做）。

不给出就有可能计重，如果让横坐标表示时间，纵坐标表示黑色球的个数。

容易发现颜色序列可以表示为一条折线，我们要对这些折线计数，那么把所有的折线向下平移直到触摸到底部，这样仍然是合法的，这提醒我们对每种方案在第一次用尽黑色球时计数，然后 dp 方程就不难了。

有些题还是建议自己想，因为有些题解可能在用嘴拉屎（包括我

一看到二次的，我没有想到用组合意义，但更方便的是直接维护一次和二次

设 (f_i) 表示放了前 i 个格子的方案数。

有 (f_i = sum_{j=0}^{i}(i-j)^2f_j)

分别维护 (sum_{j=0}^if_j(i-j)^2)， (sum_{j=0}^i2f_j(i-j))，(sum_{j=0}^if_j)，这里保证了 j 均不是分界线。

当 i + 1 和 i + 2 是分界线时，有矩阵

[egin{bmatrix} 1 & 0 & 0\ 1 & 1 & 0\ 1 & 2 & 1 end{bmatrix} ]

当 i + 1 和 i + 2 不是分界线时，有矩阵

[egin{bmatrix} 1 & 0 & 1\ 1 & 1 & 1\ 1 & 2 & 2 end{bmatrix} ]

开心的做就行了！

假设我们已经选好了用第一个元素或第二个元素，如何判断？

将 Y 数组排序，然后直接比较即可。

或者我们有另一个简单的判断，也就是对于 Y 数组中排名为 k 的数，在选出的数中应该至少有 k 个小于它的。

因此，我们可以把 Y 数组排序，第 i 个位置上的初始值为 -i，那么选出来一个数，首先二分到第一个大于等于它的数 t，将 t 到 n + 1 这个后缀加 1，最后检查数组最小值是否大于等于 0 即可。

首先全部选择第一个元素，我们发现很有可能并不满足条件，那么考虑调整后答案的变化。

对于 pair (x, y) (x > y)，换用 y 后，我们发现就是将 ([y, x)) 这些位置上的值 + 1。

对于询问，我们可以拆成两个，也就是选第一个和选第二个元素的答案取个 max，这样我们考虑一次算出所有的答案。

现在我们的问题转化为了，给定一个数组，要求某些位置至少要覆盖若干次，求最少用几条线段覆盖。

考虑一个暴力做法，枚举询问的那次覆盖了 ([x,n+1])，那么剩下的做线段覆盖即可，如果当前位置需要被覆盖，那么找到最右的包含它的端点。或者你可以反过来做也是没问题的。

基于线段覆盖这种贪心，我们尝试使用新做法。

首先倒着做从右到左的线段覆盖贪心，但是我们覆盖到 (x_i ge -1) 就继续下一个位置，这是因为以后可能一次覆盖掉这些 -1。

然后做从左到右的线段覆盖贪心，这样就可以得知覆盖 ([x, n + 1]) 所需的最少线段了。

正确性存疑，等待 @AzusaCat 神仙把所有 AGC 切完了教育我。