【1800】【5.22-5.24】

【细节参考了题解】

题意：序列拆分为最少的若干条不降序列。

思路：简单版可以 $n^2$ dp。定义 $booldp(i,j)$ 表示是否存在方案使得两个序列最终位置为 $i,j$ 。自己定义的时候定义得很麻烦。

还有贪心的思路，类似二分求lis，维护一个序列 $ls$ ，表示当前第 $i$ 个序列的末尾值是多少，并降序排序（方便新增加序列）。贪心的找到第一个序列，然后放下当前增量的字符。

AC代码（dp）：https://codeforces.com/contest/1296/submission/262129471

AC代码（贪心）：https://codeforces.com/contest/1296/submission/262130727

思路：容易想到二进制拆分，划分为 $log$ 个长度为 $log$ 的 lis 。这样显然不满足限制。考虑如何重复利用使得 lis 交集更大，可以先构造一个 lis ，如果要继续增加 $2^k$ 个lis，那么利用原 lis 的一个后缀即可。注意插入的位置。

AC代码：https://codeforces.com/contest/1922/submission/262134310

思路：首先考虑到，一次操作可以拆分为若干子操作：$u=u+2^k(u\&2^k=2^k)$ 。这样的话就相当于把 u 的二进制 1 向高位移动，1 的数量不会增多。判断是否可以配对即可。也可以前缀和。

AC代码：https://codeforces.com/contest/1491/submission/262154328

【看了洛谷的 tag 】

思路：区间 dp 。难点在于博弈决策。只考虑长度为偶数的局面，即 a 面对的局面。先考虑 a 是否有策略能赢，否则考虑是否有策略能平手，否则就输了。

AC代码：https://codeforces.com/contest/1728/submission/262276717

思路：这道题思路也是比较典。考虑置换环，如果一个环上有编号相邻的节点，那么余下这一对即可；否则，都拆为孤立点，然后随便连上两个点即可。

AC代码：https://codeforces.com/contest/1768/submission/262351844

思路：好长时间憋出来的。首先偶数好考虑。如何考虑奇数？开始找性质，假设 $a_1=1$ ，发现 $a_n$ 和 $n$ 大概是同阶的。先考虑 $=\sqrt{n^2}$ ，发现构造不出来。最后打表发现某种方法可以构造出 $=\sqrt{4\times n^2}$ 。遂过。

AC代码：https://codeforces.com/contest/1758/submission/262357393

思路：这题我是拆位转化为 01 序列求解的，查询次数 $2\times n-1$ 但特别麻烦。

利用到性质就非常好写了。划重点： $(x\&y)+(x|y)=x+y$ 。这样的话就好构造了，查询次数 $2\times n$ ，方法见题解。

AC代码（拆位）：https://codeforces.com/contest/1556/submission/262366785

AC代码（性质）：https://codeforces.com/contest/1556/submission/262370912