省选模拟52

A. 图

  实际上是个构造题。

  正解给的构造方法是首先找出任意一棵生成树,对于非生成树上的边,假如这些边构成了一个二分图,那么可以对这两个二分图分别染色,最后讨论一下四种颜色。

  否则,说明剩余的边中一定存在奇环,那么由于生成树的存在说明剩余的边一定是联通的,找到任意一个奇环并输出即可。

B. 数列

  对于subtask1,直接对于每个数询问即可。

  对于subtask23,由于数的大小很小,考虑压位,搞一个100进制就可以一次确定3个数了。

  对于subtask4,首先将16个数两两分组,对于每一组询问系数为$1,10^49$,这样可以确定一个数的后49位。

  对于前8位我们只需要知道另一个数的后8位,所以只要再对每组中的第一个数分组,每4个询问一次就可以确定一个的后8位,然后解出一组中的解,然后递推出所有解。

C. 走路

  一道并不难的原题。

  最优解必然是在回来的路上吃,考虑一个简单的dp,$f[i][j]$表示回来时走到了$i$一共吃了$j$的最小花费,转移显然。

  发现当第二维较大的时候是走不回来的,所以状态数实际上只是调和级数,卡一下上界直接跑就行了。

 

上一篇:centos利用cloudflare的bpf-tools实现ddos防护


下一篇:玩法