美满电脑

文章
3
资源
0
加入时间
2年10月17天

[构造 分治] UOJ#143. 【UER #5】万圣节的数列

构造题。好像找到了manchery搬的题的原题 首先,长度为1,2的等差序列是不可避免的。我们需要尽量减少长的等差序列。 最好就是长度大于等于3的一个都没有。怎么做到呢? 考虑3个数 i<j<k, aj−ai<ak−aji<j<k,\ a_j-a_i<a_k-a_j ,ii 和 jj 的奇偶性相同。 所以我们把奇偶分成两边,这样就不存在跨过中线的等差子序列。 这样就有了一个解法:我们递归求