军争
本题考察贪心和基本数据结构的运用。
首先易知墨子取的点两两互不相邻，证明略。
70 分做法
我们先不考虑环，本题便退化为一个经典链上问题。
容易发现只需令 表示前 个数选 个的最优解，立刻得到转移方程：
其最优子结构性质是易证的，这里不再赘述。
由链到环，我们发现改变的只有 和 的连通性质，他们不能被同时选中，于是枚举选哪个或者都不选的情况就好，实际操作上只需要对 和 各跑一次链上的做法就行。
90 分做法
我们仍然从链上问题开始考虑，因为我们已经知道从链到环是容易推广的。
首先先引入定义 。
这其实就是以 作为开头和结尾的 交替串。
对于每个决策阶段，我们令已经选了的为 ，没有选的为 。
可以证明，得到的「选择串」一定能被 （贪婪）匹配完。
考虑数学归纳法：
- 当 时，选择串全零，显然选择一个最大的 值翻转成 就可以了。
- 假设已经得到了取 个的一个最优方案，考虑如何取 个。
- 我们定义对每个匹配出来的 的操作：将其内部所有选择状况反转。容易证明，这种操作相当于多选了一个点，获得的收益是 。
- 再次，根据问题关于区间的最优子结构性质，容易发现每个 块内的选择都为最优（如果不进行操作，也就是增加选点个数的话），这意味着我们不可能去减少这些块内的选点个数，否则和归纳假设矛盾（用类似剪切的方法可以反证前提为假），求全局最优退化为局部最优。
- 到此，我们只能是从这么多 块选一个进行操作，这一步的局部最优当然是 ，我们直接取走价值最大的 ，直到不能取或者收益为负为止。
我们已经得到了一个贪心策略，那么如何进行维护呢？考虑我们的需求：
- 维护出所有 块。
- 维护所有 块的价值的最大值。
对于前者，我们发现每次对一个 块操作后，其都会与周围两个 块合并，形成更大的一个块，而且其价值恰好是左右两个块的价值和减去自己的价值，这种维护相邻关系和删除操作的使用情景正适合链表，于是我们采用链表来串起所有的 块并动态维护。
对于后者，我们很容易想到用优先队列维护所有现存块的价值，注意到删除的并不一定是价值最大点，不过用数组记下已被删除的点进行延迟删除就容易做到均摊 的复杂度。
如果要把这个做法推广到环上，可以模仿之前的「掐头去尾」的做法，也可以直接把链表换成环状链表——需要注意此时链表不能被取完——因为这样操作后是非法的。除此之外，使用环甚至省去了链上的一些边界讨论（在链上你需要假设两端有一个「虚拟的」）。
100 分做法
考虑如何输出方案，根据上面我们知道，只要得到最后的操作串我们就能知道最后的方案，而操作串内部的状态只由其左右端点所唯一确定，因此只需要在维护时多维护一个左右端点就可以。
100+ 分做法
考虑如何动态得到 为随意指定值的任何一点的状态。容易想到可以离线询问按序解决，但是链表并不支持随机访问，询问一次的复杂度就可能是线性的，但我们发现其实每次操作只是一个区间异或罢了，用树状数组之类的数据结构就能把单次操作的复杂度降到对数级。
100++ 分做法
这样说可能有点无聊，但是如果强制在线询问呢？——来个可持久化树状数组就可。
密码盒
本题考察图的基础和一些简单的数学。
这题没什么有意义的部分分做法，直接从步骤开始说吧。
约束和合法解
我们发现给出的每个点都是一个约束——如果把每个行列的旋钮的状态视为变量，那么有多少个点，就有多少条关于这些变量的方程，形如
其中 是点值， 是对应行列的旋钮状态。
从理论上来说，直接高斯消元是可以得到答案的，可惜复杂度是 ，T 飞了。
但我们容易发现一条非常好的性质：如果方程组有解，那么解必有无穷多个。因为对于每个解，你都可以让所有行减一，所有列加一，从而得到完全一样的状态。也就是说如果约束状态可以被达到，那么对于任何一个旋钮的任何一个状态，都有一个合法解与之对应。（我们将其称为合法取值任意性）
同时，我们把每个变量视作一个点，很容易发现这是一张行点连列点，列点连行点，各自内部无边的二分图模型。这意味着行点与行点、列点与列点之间一定是偶数条边，简单计算可以证明，他们之间的约束只能是差为一个定值，类似的，行点与列点之间的约束只能是和为一个定值。这个二分图性质我们暂且用不到，但是把约束关系搬到图上的这个思路是很有意义的，我们来仔细考量一下。
这张图可能由若干连通块组成，不同连通块之间的取值是完全独立的，因此我们只需要考量单个连通块内部的约束情况。由于所谓合法取值任意性，我们任意定死其中一个点的值，假若以它为根延展出该连通块的一颗生成树，这些点的值同样也只能是由该生成树唯一确定的了。
但是这个连通块并不必须是一棵树，这意味着在这颗生成树上存在着一些非树边，到这里结论就非常显然了——连通块是否有合法解，当且仅当这些这些非树边上的约束关系都恰好被生成树确定的点值满足，这是由合法取值任意性所决定的。
于是，如果我们仅仅只是需要判断合法解，直接 BFS 或 DFS 所有连通块判断是否满足条件即可。
最小解
为了方便，下面假定所有连通块的生成树根被定的值为 。假设被算出的约束值是 ，那么对于单个连通块，其（目前的）代价就是：
当然我们可以任意指定这个生成树根的值，假设为 ，我们很可以知道一个连通块的自由度只有 ，所以生成树根的值唯一指定了其它所有点的取值，在这里我们需要用到二分图的性质，对于和根同类的点，差是定值，于是可以得到其取值关于树根取值的函数：
类似的，对于和根异类的点：
代价总和可以写成 的函数：
这就是我们要求最小化的函数了。
这个东西看起来不好化简，但是考虑到 与 无关，我们定义 ，其中 表示它在生成树中的深度，这个 是可以预处理的，而且我们发现由于绝对值内部可以取相反数，所以有：
这样代价函数就简单了，它实际上可以写成
这个函数的最小化就只是一道中学数学题了，实现它的方法有很多，这里我们不多赘述。