1893

纪念一下第一次补完 div1 的所有题 这个 1E 相较于其他的 1E 并不算太难。本题解部分参考官方题解。 先观察到一条边是好的当且仅当它的值和一个端点的值相同。 原因很简单，要求两端点值不同，若边权跟点权也不同，那么三个值分别只能为 \(1,2,3\)，又因为 \(1 \oplus 2 \opl ......

思路 首先可以知道答案的下界就是序列 \(a\) 原来的 LIS，现在需要做的就是尽可能地保持答案不增加。 可以肯定的是，将序列 \(b\) 从大到小地插入序列 \(a\) 是不劣的，并且如果在 \(a_i\) 前插入的都是 \(\ge a_i\) 的不会使答案增加，可以感性理解，如果原来的 LIS ......

分析 第一眼：博弈论。 第二眼：呃……贪心？ 实际：DP。 首先想这个游戏大抵存在必胜策略，否则不会让我们求。 思考先手必胜条件，就是如何让这个数组最后只剩下一个数。 设数列之和为\(sum\)。 发现每次操作给两个数减的数字是一样的。那么对于每次操作，\(\Delta sum\)都为两者之间更少的 ......