从洛谷迁移而来。

Codeforces Round 851 (Div. 2)

B

分讨一下 ， 为奇数则构造一半的上取整和下取整， 为偶数直接构造两个一半

C

为偶数无解

为奇数时有解，构造方案大概是初始第一项顶满第二项刚好，然后一个加 一个减 ，满足循环

D

很妙的DP题

我们想办法把贡献拆到点上，发现对于任何一组最终移动到一起的点，其中必定存在一个分界线使得其左边的点都向右移动右边的点都向左移动，那么我们就可以看作是这两个点造成的贡献

然后考虑两个点在什么情况下能造成贡献：

• 两个点中间不能有其他点
• 两个点不能被吸到两边

第一个好办，第二个可以二分最远不能选的点，剩下的点都是随便选

时间复杂度

E

一场出两道DP就不太厚道了

我们把求最大的保留个数转成最小的删除个数

定义 为前 个的最小删除个数

那么

然后时间复杂度平方显然gg，考虑优化

观察一下下面的转移柿子，用一下前缀和优化，然后不难发现实质是求

离散化一下 然后写一个权值线段树维护一下就对了

最终时间复杂度

F

先求是否有解

首先考虑把 转化成 ，于是就变成了指定前缀，要求满足两前缀 结果为

于是我们考虑变成图上问题：在每一对 之间建边 ，然后每个连通块每一位分别跑黑白染色（ 对应位为 那么两端颜色相同，否则不同），染色无解则问题无解

然后考虑最小化

我们考虑最终要最小化的东西可表示为

容易发现儿子个数为奇数的 就会消失，而我们一旦动了连通块中的一位那么所有的都得动，那么如果连通块中有奇数个这样的点那就可以把这一位变为

这样贪完之后就是最小值

时间复杂度 ， 是值域