好好难难
T1
似乎是四分图染色。
然而并没有那么麻烦。
我们考虑原图(G)的一个边集(T)为其的一个生成树。
那么剩余边集设为(H=G-T)。
树必然可以二分图染色。
那么如果(H)也可以二分图染色的话。
我们将染色的四种情况一一对应为四种颜色即可。
否则那么(H)中必然存在奇环。
而删去奇环后(T)中的边一个未删除。
可以认为是联通的情况。
这样问题就可以(O(m))地解决了。
T2
前三个测试点读懂题就会做。
考了一点压位和(STL string)的技巧。
最后一个考虑两个两个做。
肯定有相交的部分。
用剩余的两次，一次做八个把剩余的重叠部分给做出来。
用一点高精度减法。
T3
原题。
从后向前考虑即可。
我们发现如果转移的时候价值已经为(j)了。
那么再往前必须要走的步数还有(i)步，也就是说至少还需要的代价是(ij)。
我们考虑这种状态如果能够合法的转移到最终状态。
那么一定有(ijleq m)，也就是说只需要转移([0,frac{m}{i}])这一部分。
那么复杂度就是(mln m)了。