直播预告
直播时间：3月23日（周六）下午4点半开始
直播地址： B站ACGO官方账号
直播内容：赛事复盘（欢迎观看大型翻车现场）
主讲人：小鱼老师
官方题解｜挑战赛#2
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T1 - 不能整除
题目解析
我们可以拿题面中 n=3n = 3n=3 且 k=5k = 5k=5 去思考，这里的答案是 777。
让我们展开这个序列 1,2,3‾,4,5,6‾,7,8,9‾,10,11,12‾...1,2,\underline{3},4,5,\underline{6},7,8,\underline{9},10,11,\underline{12} ...1,2,3 ,4,5,6 ,7,8,9 ,10,11,12 ...，其中标下划线的数，为 333 的倍数。
我们在算个数的时候，是要忽略 333 的倍数的。
那么我们发现每次经过 n−1n - 1n−1 个数，才会出现一个 nnn 的倍数。
那么我们看一下要经过几次 n−1n - 1n−1 会数到我们想到的数，还是以上面的数举例子。
* 第1轮：1，2，3‾1，2，\underline{3}1，2，3
* 第2轮：4，5，6‾4，5，\underline{6}4，5，6
* 第3轮：7，8，9‾7，8，\underline{9}7，8，9
我们观察，想要数到第 555 个，要数 333 轮，777 在第三轮出现，这个轮次可以直接求得为：⌈kn−1⌉\lceil \frac{k}{n-1} \rceil⌈n−1k ⌉，那么前两轮中每次我们都会少数 111 个。
最终的答案为 k + 轮次 - 1。
AC代码
也可以写成下面这种形式
复杂度
由于我们已经推算出，计算的公式了，所以对于任何情况都是 O(1)O(1)O(1)。
T2 - 来自领导的烦恼
特邀出题人MACW题解：原链接
题目解析
本题可以使用动态规划或递归的方式来实现，本质上是一道01背包的变型题。假设一共有nnn名员工，每一位员工的技能水平用a[i]a[i]a[i]表示。要使得两个部门的员工技能总和之差最小，意思就是尽可能地将一个部门的技能之和”凑“到∑i=1na[i]×12\sum\limits_{i=1}^{n}a[i] \times \frac{1}{2}i=1∑n a[i]×21 ，也就是所有员工技能总和的一半。套用背包问题的模板，每一位员工就是每一件“物品”，背包的容量就是“所有员工技能总和的二分之一”。
AC代码
参考代码在01背包的基础上进行了内存优化，将二维dp数组转换成了一维dp数组。其中：
1. arr[i] 表示第i个员工的技能水平。
2. sum 表示所有员工技能水平之和。
时间复杂度分析
本题通过两个for循环来填写dp表格，外层循环遍历每一个员工，内层循环遍历所有员工的技能水平之和。外层循环执行 nnn 次，内层循环执行 ∑i=1na[i]\sum\limits_{i=1}^{n}a[i]i=1∑n a[i] 次。因此，本道题目的时间复杂度为 Θ(n×∑i=1na[i])\Theta(n\times \sum\limits_{i=1}^{n}a[i])Θ(n×i=1∑n a[i])，为 O(n2)O(n^2)O(n2)。
T3 - 星光交错的律动
特邀出题人MACW题解：原链接
题目解析
这道题可能跟博弈论有一点关系，没有学习过博弈论做起来应该问题也不大。思考一个问题，先手必胜的前提是什么？
* 先手必胜的前提是，在任何一种局面下，先手都有至少一种操作可以使后手处于必败的局面。
* 若先手进行任何操作后，后手都可以选择必胜的操作，则先手无法必胜。
* 如果当前玩家无法进行任何操作，那么对手获胜。
整体的思路就是通过递归不断搜索每一种决策情况，判断是否存在必胜的策略。
具体的实现方法：
创建两个函数，名为first和second。
1. first(x, y)函数返回当两位玩家分别选择数字x和y时，先手是否必胜。
2. second(x, y)函数返回当两位玩家分别选择数字x和y时，后手是否必胜。
两个函数来回交替调用对方，即在first(x, y)函数中调用second(x, y)函数，在second(x, y)中调用first(x, y)。如果存在必胜的策略，返回true，否则返回false。若先手玩家无法再进行操作时，也返回false。
AC代码
参考代码一：
参考代码二：
1. decision(r)函数返回当两位玩家分别选择数字val[0]和val[1]时，r选手（先手为0，后手为1）是否必胜。
复杂度分析
本道题目将通过深度优先搜索DFS的方式来实现，每一层递归模拟某一位玩家的两个决策（将数字乘二或将数字除以三）。因此本道题目的时间复杂度大致为 O(2d)O(2^d)O(2d)，其中ddd表示递归的深度。考虑题目数据范围 1<=x,y<=10001 <= x, y <= 10001<=x,y<=1000，递归深度约为 log2(x+y2)\log2(\frac{x+y}{2})log2(2x+y )，完全可以在限定时间内通过所有的测试点。
T4 - 我心中珍藏的游戏
特邀出题人MACW题解：原链接
题目解析
题目问最多可以获得的额外伤害，其实就是询问在这些技能中，如何怎样选取一个最优的发动技能顺序使得攻击加成最大。我们可以把每一个技能看作成一个图的顶点，把每一个攻击加成看作图的边，权制为 Ei,jEi,jEi,j。由于 Ei,jEi,jEi,j 与 Ej,iEj,iEj,i 相等，则可以将这个图视为无向图。 可以样样例抽象成下图：
考虑使用贪心的思想来解决本题，每次在图中找到权值最大的一条边选择即可，但图中不能出现环。因为是无向图，在考虑的时候可以忽略技能使用的顺序。接下来就是找一个最大生成树即可。
AC代码
时间复杂度分析
本道题可以使用最小生成树Kruskal算法来实现，将题目的模型抽象化后可以被看作为一个最多有 (1+n)∗n2−n\frac{(1+n)*n}{2} - n2(1+n)∗n −n 条边的无向图（化简后可得 n2−n2\frac{n^2 - n}{2}2n2−n )。注意一开始需要对每一条边进行排序。本道题的时间复杂度约为 O(2×n2log2n)O(2\times n^2 \log_2{n})O(2×n2log2 n)。
T5 - 拳击教练
题目解析
对于每一个选手，我们需要找到能力值比他小的选手的数量，并且要排除死对头的情况。
我们可以先把所有选手的能力值，从小到大排序。
如 原序列为：10 4 10 15，排序后 4 10 10 15。
那么如果我们想找到所有能力值低于10的选手数量，那么只需要找到大于等于10在序列中出现的第一个位置。这里大于等于10能力值的位置为222，则有 2−12 - 12−1 个人的能力值小于10，那这里就可以用二分去做了。
那么如处理，死对头呢？因为现在的答案是包含有死对头的情况的。
对于每个选手，我们只需要记录，所有能力值比这个选手小的，并且还是死对头的数量，这个可以在建立死对头关系的时候就处理。
AC代码
复杂度
对于每个选手都要进行一次二分查找，则复杂度为 O(n⋅log2n)O(n \cdot log_{2} n)O(n⋅log2 n)。
T6 - 一对好数
题目解析
这题最重要就是要往 &\&& 运算突破。
如果能找到 x，yx，yx，y，那么他们必然包含 aaa。
例如：a=1，b=8a = 1，b = 8a=1，b=8，找到的 x=3，y=5x = 3，y = 5x=3，y=5。
* x=3x = 3x=3 转二进制：0011
* y=5y = 5y=5 转二进制: 0101
为了让 x & y=a，3 & 5=1x \ \& \ y = a，3 \ \& \ 5 = 1x & y=a，3 & 5=1。那么他们在二进制中必须要包含 aaa 这里为 0001。
如果我把他们两个的0001都去了，xxx 就变为 0010，我们记作 x1x_1x1 。
yyy 就变成 0100，我们记作 y1y_1y1 既然 x+y=bx + y = bx+y=b。
那么我们推算 (x1+a)+(y1+a)=b(x_1 + a) + (y_1 + a) = b(x1 +a)+(y1 +a)=b，可以转为 b−(a+a)=x1+y1b - (a + a) = x_1 + y_1b−(a+a)=x1 +y1 。
并且 x1+y1x_1 + y_1x1 +y1 一定不包含 aaa，所以 (b−a−a) & a=0(b - a - a) \ \& \ a = 0(b−a−a) & a=0 时就能找到 x1，y1x_1，y_1x1 ，y1 。
AC代码
复杂度
常数级别，一眼 O(1)O(1)O(1)。
