题解：P15269 「UTOI 1D」Flowerfell

ran_qwq · 2026-02-11 19:09:26 · 题解

为啥感觉这题不止蓝？

考虑 sub1，搜出来发现 k\le12 时，n\le 9,a_i\le 4 就有解。期望得分 10。

观察搜出来的答案，发现 n 关于 k 是不降的。这启示我们考虑对于一个 n 构造序列最大化 k。

结论：在正中间填一个连续的动听序列，然后两边填不在动听序列中出现的数是最优的。比如说 n=8 时，a=[1,1,3,4,3,4,1,1]，这样 k=9。

:::info[证明]

一个动听序列会对 l\le i 且 r\ge y 的区间 [l,r] 造成贡献。如果存在两个贡献区间有包含关系的话，去掉大的区间会更优。所以令 l_0=0,r_{k+1}=n+1，按 l 和 r 升序排序的话，答案等于 \sum\limits_{i=1}^k(l_i-l_{i-1})(r_{i+1}-r_i)。考虑当 k>1 时删掉一个区间 i，画坐标系发现会删掉两个小矩形合并成一个长为两小矩形长之和，宽为两小矩形宽之和的大矩形，显然更优。

然后只剩一个区间，根据均值不等式显然在正中间最优。

:::

加上恰好为 k 的限制，就找出上界 \ge k 且最小的 n 并进行微调。

考虑这么一种微调方式：将前后的一段 1 换成一段 1 一段 2。如果区间包含前段一个的 1 和后段的一个 2，就有两个以上的动听序列而无效。设前段 1 个数、前段 2 个数、后段 1 个数、后段 2 个数分别为 x,y,p,q。若 x,y,p,q 中有 0，答案为 (x+y+1)(p+q+1)；若没有，答案为 (x+y+1)(p+q+1)-xq。

令 s=\lceil\sqrt k\rceil。

如果 s(s-1)\le k，前面放 s-2 个，后面放 s-1 个。令 x=1,y=s-3,p=s-1-[s(s-1)-k],q=s(s-1)-k。如果 s(s-1)>k，两边各放 s-1 个。令 x=1,y=s-2,p=s-1-(s^2-k),q=s^2-k。

交上去发现只有 50 分，为什么呢？因为当 k=s(s-1)+1 时，p=0，构造出来的答案是 s^2 就寄了。特判一下这种情况，前面改成放 s-2 个，后面放 s 个，令 x=1,y=s-3,p=2,q=s-2 就过了。

赛时一堆暴力拼起来，写的依托，代码就不放了。