A
直接 \(a_i\gets a_i-i\) 做中位数就行。
B
这我都不会???
不能嗯二分答案。考虑相当于枚举三个数 \(i<j<k\) 算 \(s_i,s_j-s_i,s_k-s_j,s_n-s_k\),然后枚举 \(j\),显然 \(i,k\) 的最优决策点是单调的。直接双指针啊啊。
C
做一个高维前缀最大值 / 次大值。
D
不错的题?
考虑 \(k-\) 子序列出现过这个条件太烂,我们一般都是用全部答案减去一个 \(k-\) 好子序列都没有的情况。
全部答案的话,从 \(A\) 起点的方向考虑可以得出是 \(k^{n-m}(n-m+1)\)。
然后考虑不合法的情况。分三种:
- \(A\) 中含 \(k-\) 好子序列:显然全都合法不用管。
- \(A\) 中不含 \(k-\) 好子序列,而且有重复元素出现:此时我们需要左边和右边都没有 \(k-\) 好子序列。先考虑全局的情况。我们设 \(f_{i,j}\) 表示 \(i\) 个数,最后一个段长为 \(j\) 的方案数。转移就是 \(f_{i,j}\times (k-j)\to f_{i+1,j+1},f_{i,j}\to f_{i+1,p}(p\in [1,j])\)。前缀和维护可以 \(\mathcal O(nk)\) 计算。回到原问题,我们假设左右的最长连续不重段长度为 \(lef,rig\),那么分别做一次,初始化 \(f_{0,lef}=1\),右边是类似的。中间做一个卷积合并即可。
- \(A\) 中不含 \(k-\) 好子序列,并且没有重复元素:这个时候我们统计全局每个不含 \(k-\) 好序列中的 \(m-\) 好序列个数,最后再除去 \(k^{\underline m}\),大概理解一下,这 \(A_1\sim A_m\) 并没有什么特殊的,和其它的 \(m\) 元组出现的系数一样,都是 \(k^{\underline m}\) 所以除去就好了。计算的话,大概还是那样,不过要开一个 \(g\) 数组,一边做着和 \(f\) 形式一样的转移,一边每次加上 \(f_i\) 中 \(\ge m\) 的下标元素。
时间复杂度 \(\mathcal O(nk)\)。最后一步讨论和第一步按位置拆贡献的思想非常棒。
标签:好子,ARC100,序列,mathcal,考虑,underline From: https://www.cnblogs.com/Royaka/p/17786884.html