题解：P10585 「ALFR Round 2」A Sum

· · 题解

好玩的构造题！

设 c,z,s,b,x,h 分别为序列 a 中某个子串 t 中第一大的值，第二大的值，长度，贡献，第二小的值和第一小的值。

依题意得：

当 c+z\le q 时，则有 b=\frac{s^2-s}{2}。

当 x+h>q 时，则有 b=0。

根据上面的条件可知：

当存在一个正整数 i 满足 p=\frac{i^2-i}{2} 时，则有关于序列 a 的 c,z 满足 c+z\le q。（情况一）

否则，必存在一个正整数 i 满足 \frac{i^2-i}{2}<p<\frac{i^2+i}{2}。（情况二）

考虑对两种情况分别进行构造。

情况一：

我们可以构造出一个长度为 i 且满足关于该序列的 c,z 有 c+z\le q 的序列 a_1，然后再构造出一个长度为 n-i 且满足关于该序列的 x,h 有 x+h> q 的序列 a_2。将这两个数列的元素放在一起，就构造出了合法的序列 a。

因为题目保证 p\le \frac{n(n-1)}{2}，所以一定可以构造出这样的合法序列 a。

情况二：

因为有 p=\frac{i^2-i}{2}+(p-\frac{i^2-i}{2})，所以我们不妨将贡献拆成 \frac{i^2-i}{2} 和 p-\frac{i^2-i}{2} 两部分来分别构造。

显然 \frac{i^2-i}{2} 的那部分可以用类似情况一的方式构造出一个长为 i 的序列 a_1。

注意到，i> p-\frac{i^2-i}{2}。

设 k,l 均为正整数。

所以我们可以构造一个数字为 q-l，并将 a_1 在保持它仍合法的情况下，将里面的数字设为若干个 l 和若干个 l+k。注意要求合法，即不违反情况一中对 a_1 的定义。

再设 j 是当前 a_1 中元素 l 的个数。

显然的，修改后的贡献会在之前的基础上加上 j。

我们通过构造使 j=p-\frac{i^2-i}{2} 即可。

剩下的，用类似情况一的方式构造一个长为 n-i-1 的 a_2。

将这两个数列的元素和 q-l 放在一起，就构造出了合法的序列 a。

关于情况二中 i\ge p-\frac{i^2-i}{2} 的证明：

\frac{i^2+i}{2}> p i+\frac{i^2-i}{2}> p i> p-\frac{i^2-i}{2}

证毕。

然后就可以开始愉快的构造了。

其实下面已经不重要了，看着上面相信大家都能构造出来对叭。

但还是介绍一下我的方法：

首先，O(n) 跑一遍暴力求 i。

令 k=l=1，对于情况一中 a_1 的构造，令元素全部为 1 即可，而 a_2 的构造，官解是全部 10^7，我是全 q，都能过的。

代码看不看其实无所谓吧。

懒得放了，注意求 i 的时候跑不到 n+1 可能会死在 #1。

做完了。提交记录。

后话：

不知道怎么搞的，老是想到一些情况二的构造无法胜任的情况。不过按理来说能让情况二构造出锅的数据都会被情况一构造掉吧，所以大抵是 hack 不掉的。

至少现在看解法没什么问题。

至少我自以为的证伪 hack 居然都满足情况一，很神奇，欢迎 hack（