B RGB Coloring
一道简单题, 枚举即可.
C Interval Game
考虑可以进行的操作只有两种, 即左拉和右拉, 连续进行两次相同的操作是没有用的.
左拉时肯定会选择右端点尽量小的, 右拉选择左端点尽量大的, 所以排序之后贪心即可.
D Choosing Points
首先证明对于所有 \(d\), 假设让两个不能同时选的点之间连一条边, 那么结果是一张二分图.
\(d\) 是奇数可以黑白染色,\(d\) 是偶数的时候, 显然连边的两点在同一个颜色内. 那么我们可以只考虑这个颜色, 获得一个新的网格图, 这个网格图的边长较大, 这时可以让 \(d\) 相应缩小, 最终 \(d\) 会变成奇数.
考虑构造出两张二分图, 然后就可以把点分为 4 种, 即在两张图内分别属于哪一边. 点数总共 \(4n^2\), 所以至少一种满足答案.
E Walking on a Tree
首先考虑每条边有多少条路径经过它, 这样可以得到一个答案上界是 \(\sum{min(2,ti)}\). 实际上这个上界一定能被构造出来.
这种题有一种很经典的想法, 就是删去叶子, 使得图的规模变小, 那么我们就每次考虑一个叶子节点 \(x\) 和它唯一的出边 \(E\). 假设 \(E\) 的经过次数小于 2, 那么无论怎么定向都没有问题, 否则任意选择两条路径 \(x-y\),\(x-z\), 假设这两条路径都经过了 \(x-a\), 那么我们可以令这两条路径方向相反, 使得 \(x-a\) 一定被双向经过, 这两条路径就变成了 \(y-z\) 的路径. 这样重复 \(n-1\) 次就能找到最优解了, 复杂度 O(nm).
F Addition and Andition
从低位开始一位位考虑吧, 对于每一位, 求出它进行了哪些加法操作和每次操作的时间, 不难求出最后的状态.
复杂度显然不对, 考虑优化. 定义势能函数等于两倍的 \(01\) 或者 \(10\) 加法操作的数量加上三倍的 \(11\) 加法操作的数量, 考虑加法时可能遇见的情况.
假设加上 \(01\) 或者 \(10\), 那么暴力做一定没问题, 因为这样相当于用两次这种操作换来一次进位的加法, 势能函数至少减去 1.
假设加上 \(11\), 那么有两种情况. 如果之前是 \(01\) 或者 \(10\), 那么相当于 \(11\) 变成 \(01\) 或者 \(10\), 势能函数减少. 假设是 \(00\), 那么这么做不改变势能函数, 所以考虑把连续的一段 \(11\) 用链表接起来缩成一段, 这样就可以 \(O(1)\) 处理一整段, 显然段数和 \(01\) 与 \(10\) 的总量是同一个级别的.
这样暴力的做法通过简单的缩段就变成 \(O(n)\) 的了.
(我从来没学过势能函数, 只知道有这个东西, 如果是我乱用了, 呃... 你理解就好了)
来源: http://www.bubuko.com/infodetail-2637193.html