codeforces 202011 月赛

零、背景

上周日，上午我没吃早饭参加了 10:30 ～ 12:00 的 leetcode 周赛，下午又没吃午饭参加了 12:00 ～ 17:00 codeforces 的 202011 月赛。
晚上 19:00 的牛客练习赛实在是做不动了，遂放弃。

这次 codeforces 的月赛相当残暴，出了 13 道题。
平常 acm 赛制都是 3 个人一起 5 个小时做 13 道题的。
这个人赛做 13 道题，时间变得特别紧凑。

下面就来看看这 13 道题吧。

一、A. Games on c++

题意：给 10 个求三个数字最大值的代码，问哪些代码是正确的。

思路：

1）调用系统的最大值函数，正确。
2）调用系统的最小值函数，错误。
3）调用系统的最大值函数，先求后两个数字的最大值，然后再与第一个数求最大值，正确。
4）自己实现最大值函数，最大值通过第一个参数返回，正确。
5）自己实现最小值函数，错误。
6）函数不是引用，永远返回第一个数字的值，错误。
7）实现的最小值函数，错误。
8）实现的最大值函数，正确。
9）函数不是引用，永远返回第一个数字的值，错误。
10）自己实现最大值函数，正确。

当然，一种简单的方法是使用 lamba 表达式包装 10 个函数，使用3 个数据来测试是否符合预期，符合预期了就满足要求。

源代码：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/A.cc

二、B. Games on sequences

题意：给两个数组，数字互不相同。
分别在两个数组取一个数字，形成一对数字。 求一对数字异或后，值依旧在这两个数组内方案数的奇偶性。

思路：暴力的复杂度是O(n^2)，会超时。
我本想使用字典树来优化，后来发现极端情况下字典树依旧会超时。

赛后发现这道题想复杂了。
题目是求组数的奇偶性的，那完全可以分析数组来找规律。

假设 a在 A 序列，b和c在 B 序列 ，存在a^b=c, 则肯定存在a^c=b。
由此可以得到，每次可以得到两组答案，最终得到的答案也是偶数个。

源代码：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/B.cc

三、C. Games on graph

题意：给一个图，问是否可以通过操作联通图上的两点，使得图的权值等于目标权值。

操作总结下就是可以选一个点加一，另一个点减一。
由此可以得到所有权值之和不变。

如果目标权值之和与输出的相等，那么肯定可以到达目标，否则不可到达。

源代码：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/C.cc

四、D. Games on Palindrome

题意：通过最小交换相邻字母的次数，使得字符串变成回文串。

没思路，不会做。

五、E. 串串

题意：给一些字符，问可以构造的定长字符串中，不同的回文子串数量最少的字符串个数。

题目有点绕。

1、构造一个定长字符串。
2、构造的字符串会存在若干回文子串，最少的回文子串个数假设为 K。
3、问可以构造出回文子串为 K 的字符串有多少个。

分别枚举计算前 5 个可以发现规律。

长度为 1 时，任意组合得到的回文子串都是 1 个。共有 62 种情况。
长度为 2 时，任意组合得到的回文子串都是 2 个。共有 62 * 62 种情况。
长度为 3 时，任意组合得到的回文子串都是 3 个。共有 62 * 62 * 62 种情况。
长度为 4 时，可以组合出回文子串的最少是 3 个，此时是染色问题，左右不相等即可，即重复的abcabcabc...。

源代码:
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/E.cc

六、F. 排队

题意：给一个图，问可以拆分为多少个独立的链路，来覆盖所有的顶点，并使链路的长度和最小。

思路：据说是欧拉路径问题。

七、G. 吃吃吃

题意：小 A上学期间每周的七天吃不同的炒菜，周几吃什么菜都固定。
但是过节日的时候会破例换一个菜吃。
上学时间有上学期和下学期。
问指定日期范围内，小 A每个菜都吃了多少次。

思路：模拟题，一天天判断即可。

源代码：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/G.cc

八、H. 走楼梯

题意：走楼梯问题，每次最多可以走 k 阶楼梯，k 不大于 10。
问走 n 阶楼梯的方案数，n 最大是 10^9。

思路：经典的动态规划问题。
但是 n 比较大，需要使用矩阵幂来优化。

为什么可以使用矩阵幂优化呢？
因为矩阵相乘满足结合律。

比如状态转移方程简化为 f(2) = f(1) * k。
那么 f(n) = f(1) * k^ (n-1)。
这样，本来是 O(n) 的复杂度，转化为 O(log(n))的复杂度了。

源代码：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/H.cc

九、I. 玩泥巴

题意：给一个数组，问是否可以挑选一个集合，使得集合里的任意个元素异或不为 0。

思路：据说是线性基问题，都没听过这个词。

十、J. 后缀自动机

题意：给若干个不同的字符串。
每个字符串可以使用自己的某个前缀代替，但是前缀不能重复。
问所有前缀长度之和的最小值。

思路：一开始以为排序或者字典树贪心即可。
后来发现又反例，比如ea erb era，最优前缀是ea e er。

标准的做法是枚举下一个前缀选择哪个字母，所有里面选择最优值。
例如还是上面那个反例，枚举e分配给ea前缀或者er前缀，哪个更优。

源代码周末会提供。

十一、K. 校门外的树

题意：一排树，只能从一端开始砍树。
砍树可能增加金钱，也可能降低金钱。
允许金钱为负，问最大金钱是多少？

思路：最大前缀和，扫描一遍即可。

源代码：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/K.cc

十二、M. 抓不住爱情的我，总是眼睁睁看它溜走

题意：求公式f(n) = f(n-1) + 2 *f(n-2)

思路：n 比较小，循环暴力求即可。

源代码：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/M.cc

十三、最后

这次比赛大部分题其实都不难，但是作为个人赛，题目太多了，五个小时根本做不完。
平常团队赛三个人也是做这么多题，现在一个人，算是考察基本功的时候到了，全程敲代码。

加油，算法人。

《完》

-EOF-

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