直播预告
直播时间：3月2日（周六）下午4点-6点
直播地址： B站ACGO官方账号
直播内容：挑战赛#1复盘（欢迎观看大型翻车现场）
主讲人：小鱼老师
T1 - 算术排列
分析题目不难发现，大的数字能变小，小的数字不能变大，容易想到一个贪心的思路：
令当前数字为 xxx：
1. 若 x>nx > nx>n，将 xxx 整除 222。
2. 若已经有数字 y(1≤y≤n,y=x)y(1 \le y \le n, y = x)y(1≤y≤n,y=x)，将 xxx 整除 2。
重复以上操作直至 xxx 变为 000 或者找到一个没有得到的排列中的数字为止。
使用一个数组 ppp 存储 111 到 nnn 一共 nnn 个数字是否出现过。
若操作完整个数组 ppp 后，以上条件满足则输出 YES\tt{YES}YES 否则输出 NO\tt{NO}NO。
AC代码
复杂度分析
对于数组中的每个数字，将其做处理的时间复杂度为 logai\log{a_i}logai ，处理完整个数组时间复杂度为 O(nlogaiO(n\log{a_i}O(nlogai )。
T2 - 数组片段匹配
注意题目中标注要求满足条件的长度相同的子数组中，只需要 存在\bf{存在}存在 数对 p(xi,yi)(1≤i≤k)p(x_i, y_i) (1 \le i \le k)p(xi ,yi )(1≤i≤k) 其中 xi=yix_i = y_ixi =yi 即可。
这点提示我们要关注相同的元素。那么对于两个相同的元素，各自形成的子数组，如果两者在原数组中距离较远，则包含其子数组长度越短，反之，包含其子数组的长度越长。
在原数组中令 ai=bj(1≤i<j≤n)a_i = b_j(1 \le i < j \le n)ai =bj (1≤i<j≤n) 这个长度可以拆分成两个部分 xxx 和 yyy，其中 x=ai,y=n−ajx = a_i, y = n - a_jx=ai ,y=n−aj ，那么最终我们要求的答案就是枚举数组中相邻的相同数字的位置 x+yx + yx+y 即 n−(aj−ai)n - (a_j - a_i)n−(aj −ai ) 最大的就是答案。
若数组中没有重复数字，显然不存在满足条件的两个子片段。
AC代码
复杂度分析
代码实现上，遍历数组 aaa，令外使用一个数组 preprepre 记录数字 xxx 在数组中出现的上一个位置，随着遍历不断更新，得到答案。时间复杂度为 O(n)O(n)O(n)。
T3 - 勇敢的冒险者
题目大意
冒险者在一条 xxx 轴上，并处于点 000，假设当前的位置是 yyy ,现在正在进行第 kkk 次跳跃,有两种跳跃的方案
* 向前跳跃到 y+ky+ky+k
* 向后跳跃到 y−1y-1y−1
冒险者要到达点 xxx 点
题意分析
问最少跳跃几次，冒险者就能到达 xxx 点
解题思路
由于一开始冒险者一定是在点 000 的，并且 xxx 点一定是大于 000 的，很容易看出一开始只要一直执行 【方案一】 即 y+ky+ky+k 就一定能到达 ≥x\ge x≥x 的位置。
如果执行了 kkk 次后正好能到达 xxx 点那么答案为 kkk
那如果超过了 xxx 点呢? 这个时候我们需要考虑用 【方案二】 来进行干预了。
接下来我们分类讨论一下：
* 进行kkk次操作后，到达了 x+1x+1x+1 的位置，那么我们只需要执行一次 【方案二】
* 进行kkk次操作后，到达了 x+px+px+p 的位置，其中 ppp (p>1)(p\gt 1)(p>1) 为超出 xxx 的部分
这个时候可以有两种办法消除这个 ppp。
第一种选择执行 ppp 次 【方案二】
第二种选择在之前跳跃的某次 【方案一】 将它改为 【方案二】
显然这里选择 【方案二】 是最优的
所以我们只需要关心，经历几次 kkk 能跳到 ≥x\ge x≥x 的点上就行了，这里可以使用二分去快速找到 kkk
时间复杂度解析
对于每个 xxx 都需要进行一次二分即复杂度为：O(log2n)O(\log_{2} n)O(log2 n)
代码演示
T4 - 超能战士
题目大意
有 nnn 只怪兽，每只怪兽都有生命值 hih_ihi 和攻击力 pip_ipi ，超能战士每次可以对所有活着的怪兽造成 kkk 点伤害。
怪兽会在每次超能战士攻击后进行反击，活着最弱的怪兽会降低超能战士攻击伤害，降为 k−pik - p_ik−pi
题意分析
求问超能战士能不能消灭所有的怪兽
解题思路
从题中可以发现，超能战士的攻击力 kkk 同时可以看做是超能战士的血量，当 k≤0k \le 0k≤0 的时候，如果场上还有怪兽，则不能消灭所有怪兽。
超能战士每进行一次攻击可以消灭所有当前血量 ≤k\le k≤k 的怪兽，我们可以模拟这个过程直到超能战士的攻击力 ≤0\le 0≤0，所以重点考虑怎么去模拟这个过程，如果用暴力的方式，一遍一遍让怪兽的血量减去 kkk，那么复杂度为 O(n⋅k)O(n \cdot k )O(n⋅k)，超时！
实际上我们只需要找到第一个不能被杀死的怪兽，即第一个血量 >k\gt k>k 的怪兽。
我们可以先按照血量从小到大排序，我们记找到第一个血量 >k\gt k>k 怪兽的下标为 iii，那么 <i\lt i<i 的怪兽都视为死亡，≥i\ge i≥i的怪兽都为存活。由于血量是有序的了，满足单调性，我们可以使用二分。由于怪兽的血量是会变化的，在二分的时候要将怪兽的血量减去超能战士累积攻击的伤害。
我们还有个问题没有解决，如何在存活的怪兽中，找到最弱的，即攻击力最小的。存活的下标区间为 [i,n)[i,n)[i,n)，我们可以贪心最小值，倒着遍历不断看右边的最小值与当前值哪一个更小，来维护一个最小值数组。
时间复杂度解析
维护小最值数组，需要遍历所有怪物，复杂度为 O(n)O(n)O(n)
查找第一个不能杀死的怪物，用到了二分，直到 k≤0k \le 0k≤0 时，结束模拟过程。复杂度为 O(n⋅log2n)O(n \cdot \log_{2} n)O(n⋅log2 n)
代码演示
T5 - 迷宫L
题目大意
有一个 000 和 111 组成的矩阵，有一个操作，选择一个 2×22\times22×2 的子矩阵，在这个子矩阵中选择一个 LLL，把这个 LLL 中的三个数全部变成 000，如果选择的这个 LLL 中至少包含一个 111 的话，则可以操作。
题意分析
问最多可以操作多少次
解题思路
如果要让次数最多，那我们要尽可能用上每一个 111，换句话说最好一次只消除一个 111。我们可以发现当一个 2×22\times22×2 的子矩阵中，存在两个 000 的情况下，可以一次只消除一个 111
那么如果没有出现以上这种情况，我们可以先进行一次操作，这样必定能构造出来在 2×22\times22×2 中出现两个 000 的情况。这个时候分类讨论一下，我们记 111 出现的次数为 ononon
* 如果子矩阵中出现了一个 000 则答案为 on−1on - 1on−1
* 如果一个 000 都没有的情况，答案为 on−2on - 2on−2
时间复杂度解析
我们需要遍历一次矩阵，复杂度为：O(n×m)O(n \times m)O(n×m)
代码演示
T6 - 质数花瓣
题目大意
在一个长度为 nnn 的数字区间内，寻找符合要求的质数。
题意分析
如果每次去掉数字的最后一位，仍是质数，则满足要求
解题思路
素数筛模板题，可以套用埃氏筛或欧拉筛
如果你的埃氏筛超时了，请将标记数组换成bitset容器
如果你的欧拉筛超内存了，请将数据类型换成short
当然此题不止这一种解法，你还可以按数字位搜索，找到符合条件的数。
时间复杂度
时间复杂度为：O(nloglogn)O(n\log\log n)O(nloglogn)
代码演示
