PDF《1 Rikka with Number》

1 Rikka with Number 1.

1 Solution 考虑这个过程的逆,就是辗转相减,对于一个 n,在1?n之间多次随机 m,然后进行辗 转相减,直到 n, m 互质且次数不超过

60 次即可.

2 Rikka with Tree 2.1 Solution 考虑包含 k 个点的链,可以得出任意距离不超过 k ?

1 的点的颜色不同.在大小为 k 的连 通子图中,任意两点的距离不超过 k ? 1,所以这个条件是充要的. 首先考虑 k =

3 的情况,每个点和它的邻居的颜色两两不同,答案不小于 max{degv + 1}. 因为我们可以从根往下染色,一定存在方法满足条件,所以 max{degv + 1} 足够了.这个结果 可以推广到 k 为奇数的情况,答案为 max{f(v)},其中 f(v) 为到 v 点距离不超过 k?1

2 的点的 个数. 而对于偶数,只要把这个中心改掉边的中间即可. 对于 f 值的计算,用点分治就可以.

3 Rikka with Cactus 3.1 Solution 如果图不连通,答案为 0. 首先我们求出一棵 DFS 树,每条非树边对应 DFS 树上的一条链,对于每条边,它被若干 条非树边覆盖. 如果最大的覆盖数是 0,整个图是一棵树,每条边都不能删. 如果最大的覆盖数是 1,整个图是仙人掌,所有覆盖

0 次树边,删除后会不连通,所以不能 删,其他边都能删. 如果最大的覆盖数是 2,先考虑非树边,删完之后,对应的链全部减 1.然后是覆盖次数为

1 的边,删除之后相当于覆盖它的非树边对应的链全部减 1.然后是覆盖数为

2 的边,它删掉 之后相当于覆盖它的两条非树边的对应的链的交全部减 2,其他不变.只要看删除每条边对应 的减的东西能不能把这些覆盖数为

2 的边全都减掉就行了.这些为

2 的树边如果不是从底往上 的,一定是无解的. 如果最大的覆盖数是 3,非树边和覆盖次数为

1 的边,删除之后只能减 1,肯定不合法.覆 盖数为

3 的边删除之后这三条非树边会形成两个环,所以也不合法.然后是覆盖数为

2 的边, 它删掉之后相当于覆盖它的两条非树边的对应的链的交全部减 2,其他不变.只要看删除覆盖 数为

2 的边对应的减的东西能不能把这些覆盖数为 2,

3 的边全都减掉就行了. 最大覆盖数超过了 3,那就肯定无解.

1 4 Rikka with Flow 首先列出线性规划方程组 ∑ v cu,v = ∑ v cv,u ?u ce ≤ fe ?e max ∑ ce ? we 对偶得 de + λu ? λv ≥ we min ∑ de ? fe 记每条边最后的费用为 xe,使用单纯形法解下面的方程组就能得到答案. de + λu ? λv ≥ xe ?e = (u, v) xe ≤ we ?e ∑ de ? fe ≤ p min ∑ we ? xe (1) 2