A. 图
实际上是个构造题。
正解给的构造方法是首先找出任意一棵生成树,对于非生成树上的边,假如这些边构成了一个二分图,那么可以对这两个二分图分别染色,最后讨论一下四种颜色。
否则,说明剩余的边中一定存在奇环,那么由于生成树的存在说明剩余的边一定是联通的,找到任意一个奇环并输出即可。
B. 数列
对于subtask1,直接对于每个数询问即可。
对于subtask23,由于数的大小很小,考虑压位,搞一个100进制就可以一次确定3个数了。
对于subtask4,首先将16个数两两分组,对于每一组询问系数为$1,10^49$,这样可以确定一个数的后49位。
对于前8位我们只需要知道另一个数的后8位,所以只要再对每组中的第一个数分组,每4个询问一次就可以确定一个的后8位,然后解出一组中的解,然后递推出所有解。
C. 走路
一道并不难的原题。
最优解必然是在回来的路上吃,考虑一个简单的dp,$f[i][j]$表示回来时走到了$i$一共吃了$j$的最小花费,转移显然。
发现当第二维较大的时候是走不回来的,所以状态数实际上只是调和级数,卡一下上界直接跑就行了。