好好难难

T1
似乎是四分图染色。
然而并没有那么麻烦。
我们考虑原图\(G\)的一个边集\(T\)为其的一个生成树。
那么剩余边集设为\(H=G-T\)。
树必然可以二分图染色。
那么如果\(H\)也可以二分图染色的话。
我们将染色的四种情况一一对应为四种颜色即可。
否则那么\(H\)中必然存在奇环。
而删去奇环后\(T\)中的边一个未删除。
可以认为是联通的情况。
这样问题就可以\(O(m)\)地解决了。

T2
前三个测试点读懂题就会做。
考了一点压位和\(STL\ string\)的技巧。
最后一个考虑两个两个做。
肯定有相交的部分。
用剩余的两次，一次做八个把剩余的重叠部分给做出来。
用一点高精度减法。

T3
原题。
从后向前考虑即可。
我们发现如果转移的时候价值已经为\(j\)了。
那么再往前必须要走的步数还有\(i\)步，也就是说至少还需要的代价是\(ij\)。
我们考虑这种状态如果能够合法的转移到最终状态。
那么一定有\(ij\leq m\)，也就是说只需要转移\([0,\frac{m}{i}]\)这一部分。
那么复杂度就是\(mln\ m\)了。