本场挑战赛的所有题目的难度评级为：
题目编号 题目标题 难度 T1 午枫爱画画 入门 T2 午枫爱谦让 普及- T3 午枫爱搬家 普及- T4 午枫爱操作 普及/提高- T5 午枫爱迷宫 普及/提高- T6 午枫爱37 普及+/提高
挑战赛18题解
T1
输入输出
按照题目要求输出即可，注意多的一方需要最后额外连续输出对应字符。
用 while 或 for 循环皆可实现。
时间复杂度 O(max{n,m})O(max\{n,m\})O(max{n,m})
STD
T2
贪心，排序
由于双方都想让对方拿的数字更大且数组元素个数保证为偶数，所以每次拿的时候只会拿当前剩下数中最小的数。
具体实现方法可以将整个数组从小到大排序后，遍历整个数组，将奇数位置和偶数位置的数分别求和即是两人分别拿到的数字之和，不用真的实现删除（拿走）操作。
时间复杂度 O(nlogn)O(nlogn)O(nlogn)
STD
T3
二分
考虑二分答案，checkcheckcheck 时可以求出每次二分的搬运次数，因为是固定顺序，所以直接枚举所有物品，不断累加重量，当前重量和大于 midmidmid 值时视为一次搬运次数，并重置物品总重量。
通过调整二分的左右边界，最终确定答案。要注意的是初始二分范围是 [max(wi),1014][max(w_i),10^{14}][max(wi ),1014] ，如果左边界初始设置成 000 可能会导致在 checkcheckcheck 过程中将不该统计进去的次数算进去，如 mid<wimid<w_imid<wi 的情况。
时间复杂度 O(nlog(∑i=1nwi))O(nlog(\sum_{i=1}^n w_i))O(nlog(∑i=1n wi ))
STD
T4
贪心
通过手模不难发现，对于一段连续的 000 ，如果这段 000 右边至少有一个 111 ，那么可以通过一次操作使得这段 000 都变为 111 ，因为这段 000 一定是在高位的，所有这样的操作一定是最优的；由于操作后会出现新的 000 ，那么重复之前的过程，直到最后无法操作为止。
所以每次选取左端点为最左边的 000 ，右端点的距离左端点最近的 111 ，这样可以将这个区间除最后一位其他所有位都变成 111 ，同时提供了下一个区间的左端点，这样反复操作后，一定可以变成形如 11..00..11..00..11..00.. 的二进制数。
确定了上述方法，可以用模拟来实现，也可以记录最后一个 111 的位置直接输出。
时间复杂度 O(n)O(n)O(n)
STD
T5
bfs，模拟
不难发现小午拿钥匙、救小枫、单独找出口的过程其实一样的，那么这三个过程可以合在一起通过一次 bfsbfsbfs 判断能否到达这三个点；若可以解救小枫，再通过一次 bfsbfsbfs 判断能否到达出口，但这次 bfsbfsbfs 的遍历过程需要多一个可以走 $ 的判断条件。
总体做 222 次 BFS ，第一次判断以小午为起始位置是否能走到钥匙所在位置、小枫所在位置以及出口所在位置，若既能走到钥匙处也能走到小枫处则进行第二次BFS，判断以小枫为起始位置能否走到迷宫处。
可以用 444 个变量表示是否能到达各个特殊位置，最后按照输出优先级输出对应答案即可。
时间复杂度 O(n×m)O(n\times m)O(n×m)
STD
T6
DP
“既是 333 的倍数，又是 777 的倍数” 可以理解为 “是21的倍数”。
可以考虑 DP ，设 dp[i][j]dp[i][j]dp[i][j] 表示前 iii 个数可以组成 jjj 的方案数，其中 jjj 最多只有 212121 种状态。设当前所选数综合模 212121 为 jjj ，对于第 iii 个数都有选和不选两种情况，若不选，方案数为 dp[i−1][j]dp[i-1][j]dp[i−1][j] ；若选，方案数为 dp[i−1][(j−a[i]+21)%21]dp[i-1][(j-a[i]+21)\%21]dp[i−1][(j−a[i]+21)%21] 。那么状态转移方程为
dp[i][j]=dp[i−1][j]+dp[i−1][(j−a[i]+21)%21]dp[i][j]=dp[i-1][j]+dp[i-1][(j-a[i]+21)\%21]dp[i][j]=dp[i−1][j]+dp[i−1][(j−a[i]+21)%21] 。
由于 nnn 较大，可以考虑用滚动数组优化空间复杂度。（当然本题实际上并没有卡空间）
时间复杂度 O(21n)O(21n)O(21n)
STD
