C

一个序列
可以选择连续两个或三个元素翻转
问最少翻转两个元素几次使序列有序(可翻转桑元素任意次)

贪心

翻转三个元素可以使每个位置上的元素移到目前 +-2k 个位置
而不能直接移动的的就通过翻转两个元素来实现(成对)

D

有n个数
从中选出尽量多的数,使得两两间的乘积均不为立方数

数论

我们知道立方数的每个质因子的幂都是3的倍数
我们可以将所有质因子中的立方数除去
剩下的幂次1对应2,2对于1,就是与之相乘为立方数的数(对应处理后)
每个数都这样处理后,存在map里

最后统计,成对的两组数只能取中的一组,即最大的一组

E

初始序列为 1-N
有Q次操作,每次选择将一个序列长度变为q
(q 比长度大时则取循环)
求最后序列中 1-N 的个数

递推

首先发现若当前序列的长度比后一个长,则可以忽略

然后就变成了一个递增的序列
$d_i$ 表示当前序列长度为i的序列的个数
$d_{q_i} = \sum_{q_{i+1} \geq j > q_i} j/q_i * d_j$
$d_{j \mod q_i} = \sum_{q_{i+1} \geq j > q_i} d_j$

由于长度是不连续的,所以用map来存d
令q[0] = N,从最后一个位置开始向前递推