Ucup 做题记录

厉害，首先容易想到我们一定会去构造这样的一条链，前一个向后一个点连两条边，一条是1，一条是0，这样的话就可以使用 $\log$ 的代价给出连续段时的解。

于是乎我们想到将 $[l,r]$ 拆分成很多个不交子区间的并，对于每个子区间来做上述操作。同时注意到标号和线段树标号的相似之处，可以考虑使用递归构造的方式节省时间。

一种trick,当我们去做这种消去相邻两个东西的题时可以考虑把偶数位的东西取反看看。

比如这个题，如果偶数位的东西是0或1就取反，发现题目就转化成了我们消去相邻两个不同的字符。

注意到如果没有2的存在，那么答案就是0和1的数量差，那么2就可以使01数量差尽可能小，判一下就行了。

先考虑给你一个集合怎么求答案，即 $n=m$ 的情况，你所要做的就是去判断最小的数是不是GCD，如果是就删掉，如此反复。

这种题的套路已经深入骨髓了，拆贡献或者是容斥。不妨考虑去算每个数会被多少个集合包含，这是困难的。于是考虑反着来，去数他被那些集合删除。

这就是个简单的组合计数了。

厉害的构造题，因为有比较无脑的DP解法所以体现不出贪心的思维量。

结论：如果有偶度数点那么一定有解，否则无解。证明，用DP可以证。

计算 $\max_{i,j} C_i+C_j+f(i,j)$。看这个裸的问题不好做，回题再看看性质。

如果没有 $f(i,j)$ 的话就直接把最大的两个加起来即可。但是注意到题目上有值的 $f(i,j)$ 只有 $n$ 个，故枚举这些点对更新答案即可。

对于每相邻两个黑点计算答案。如果没有边界限制的话就直接贪心即可，有限制就先贪心后调整即可。

签到题居然拼尽全力无法战胜？是我傻了，这要是放CF B我就做出来了。

开头得是一个 >,结尾至少三个 >。至少得有一个 -。然后先把结尾连续段造出来，利用结尾把中间的 > 补起来即可。

很逆天，猜了个结论直接就过了，提供一种和题解不一样的证明思路。

将两个数看做是二进制下集合，于是发现运算就和集合取交取并取反以及挖掉一部分等价，故相邻两个数最多产生8的贡献。

那个map存一下就结束了。