codeforces 2020年12月月赛算法比赛

零、背景

这周日在 codeforces 上参加了某高校 12 月份的校赛，涉及到不少算法，分享给大家。

比赛源代码：https://github.com/tiankonguse/ACM/tree/master/codeforces/gym/306556

A. 暴打出题人

题意：给一个数组 n 个数字，挑选若干个数字的和可以组成一个数字。
问区间目标 [1,M] 的数字是否都可以通过挑选一些数字求和得到。

如果不能，可以加入任意一个数字，如果还不能，可以再加入任意一个数字。
问最少加入多少个数字才能满足目标。

思路：首次看到这道题，会完全没思路。

不过从小到大开始分析的时候，就会发现这道题很简单。

如果数组中没有数字 1 ，那么肯定需要添加一个数字 1。因为其他任何数字都不可能求和得到 1。
如果数组中有 1 且有 k 个 1 ，那么我们通过这 k 个 1，可以分别得到数字 [1,k]。

如果此时数组中再有一个数字 2，通过数字 1 和 2，我们还可以组合得到 k+1 和 k+2 这两个数字和，最终可以得到 [1, k+2]。
这个操作抽象一下就是，如果前 i 个数字可以组成区间 [1, a]，第 i+1 个数字是 b 且 b <= a+1， 那么考虑第 i+1 个数字后，就可以组成区间 [1, a+b] 了。

如果我们可以组成区间 [1,a] ，但是不存在小于等于 a+1 的数字了，那么我们无论如何也不能组成 a+1 这个数字。
所以需要加入 a+1 这个数字。
加入之后，就可以按照上面的策略，得到新的区间 [1, 2*a+1] 了。

复杂度：假设数组一个数字都没有，区间每次都是倍增的，所以复杂度是O(log(n))。

B. beam search

题意：给一个多叉有向树，从根节点遍历，每次只能遍历权重最大的 k 类儿子，求遍历的权重和。
类儿子定义：权重相等的儿子算一类儿子。

思路：每个节点的儿子排个序，按照定义 dfs 或 bfs 递归 k 类儿子即可。

C. 不会吧不会吧，不会真有人只会用 __gcd() 吧

题意：给一个 gcd 算法，问 cnt 的值是多少。

typedef long long ll;
ll cnt;
ll gcd(ll x, ll y) {
    if (y == 0) return x;
    if (x < y) return gcd(y, x);
    ++cnt;
    return gcd(x - y, y);
}
void func(ll x, ll y) {
    cnt = 0;
    ll d = gcd(x, y);
    printf("gcd(%lld, %lld) = %lld, cnt = %lld", x, y, d, cnt);
    puts("");
}

思路：分析 gcd 算法，可以发现当 x 大于 y 的时候， x 会不断的减 y。
所以当 x 大于 y 的时候，减的次数就是 x/y 次。
接着需要递归的计算 gcd(y, x%y) 的次数。

复杂度：gcd 的复杂度可以通过最坏情况来估算。
假设每次 x/y 都是 1，那么 x1=y0, x1=x0-y0。
公式展开可以发现是斐波那契数列，即复杂度近似于 O(log(n))。

D. 数座位

题意：输入 n 个素数，求大于 x 且 小于 y 的能够整除其中一个素数的整数个数。

思路：裸的容斥原理题。

模板地址：https://github.com/tiankonguse/ACM/blob/master/tmpleate-2020/code/rongchi.cc

E. 散樱乱武

题意：输入一个无向图，有多个可选的入口和可选的出口，问最短路。

思路：加一个超级入口与超级出口，然后正常的求最短路即可。

F. 斐波那契数列之前缀和套娃

题意：斐波那契数列定义为 F(n)=F(n-1)+F(n-2)。
一级前缀和定义为S(n) = S(n-1) + F(n)。
二级前缀和定义为SS(n) = SS(n-1) + S(n)。
输入一个整数，求二级前缀和。

思路：输入的数字非常大，很容易需要使用矩阵幂来优化这道题。

写出前10个数字的关系，就可以看出状态矩阵的关系。

0 1 1 2  3  5  8 13
0 1 2 4  7 12 20 33
0 1 3 7 14 26 36 69 

最基本的状态就是题意的状态，即A(n)=A(n-1)+B(n)。
几何意义是当前上一个位置代表前缀和，加上当前位置的值，就是当前位置的前缀和。

我按照原始题意构造了6*6的状态矩阵，结果超时了。

0 1 0 0 0 0 含义： F(n-1)
1 1 0 0 0 0 含义： F(n) = F(n-1)+F(n-2)
0 0 0 1 0 0 含义： S(n-1)
1 1 0 1 0 0 含义： S(n) = S(n-1) + F(n)
0 0 0 0 0 1 含义： SS(n-1)
1 1 0 1 0 1 含义： SS(n) = SS(n-1) + S(n)

学弟思路灵活一些，优化为4*4的状态矩阵，通过了。
大概思路是消除了 S 的前缀和。

学长思路更灵活，直接构造了2*2的状态矩阵，也通过了。
大概思路是使用消除 S 前缀和的方法，把 SS 的前缀和也消除了，直接得到一个 F 相关的公式。

我再一看题，数字取模 100。
这么小的数字，完全很快就出现周期了。
所以我打表后，输入 100 发现不是周期，随手又输入 900， 发现 900 就是周期，便水过去了。

G. 不讲武德

题意：n 个数字编号 1 到 n，每个数字 i 的值是 i * C(n, i)。
求所有数字值得和。

思路：将所有的组合数写下来，用矩阵标示，可以发现可以上下组合起来，组成一个完整的组合数。

C(n,1) C(n,2) C(n,3) ... C(n,n)
       C(n,2) C(n,3) ... C(n,n)
              C(n,3) ... C(n,n)
                     ... C(n,n)
                         C(n,n)

由于C(n,i)等价与C(n,n-i)，可以上下组合为C(n,0) + C(n,1) C(n,2) C(n,3) ... C(n,n)。
完整的组合和固定为2^n，大概有n/2个。
如果 n 为奇数的话，中间的恰好只有一半，即和为2^(n-1)。
两个合并，就是(n+1)*2^(n-1)。

H. 耗子尾汁

题意：给一个棋盘，以及马的 k 中走法，问最少多少步可以到达指定坐标。

思路：bfs 即可，走过的标记一下不要走了。

I. 狼抓兔子

题意：统计输入文件的字符核数。

思路：循环加一即可。

J. 区间染色

题意：给 n 个数字，每个数字有一个颜色。
每次最长可以将连续 k 个数字染成相同的颜色。
问最少通过多少次染色可以将 n 个数字染成相同的颜色。

思路：颜色只有 100 个，枚举颜色即可。

思考题：颜色非常大，不能枚举，该如何做呢？

最后

这次比赛的题后来放水了，不放水的话，我就不能 AK 了。
比如 F 题无限前缀套娃，我 6*6 的状态矩阵竟然被卡超时，这个很变态。
最后一题，如果不能枚举，那就没有思路了。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code