接下来我开始看第二题【CF-1766G】The Great Wall of China[^3^][3]。这题给出了一个长度为n的序列a和一个整数k，要求找出一个长度为k且字典序最小的子序列b，使得b_i \leq a_i对于所有i \in [1,k]成立，并且\sum_{i=1}^{k} b_i最大。这题看起来很复杂，但其实只要用单调队列就可以优化出线性时间复杂度的算法。我的思路是先从左到右扫描a序列，并维护一个单调递增队列q_1存放当前可选元素，并且保证q_1.size() + n - i \geq k - j（其中i,j分别表示当前扫描到a,b序列中第几个元素），然后每次从q_1.front()取出最小元素作为b_j并将其弹出队列；再从右到左扫描a序列，并维护一个单调递减队列q_2存放当前可选元素，并且保证q_2.size() + i \geq k - j + 1 （其中i,j分别表示当前扫描到a,b
序列中倒数第几个元素），然后每次从q_2.front()
取出最大元素作为b_j
并将其弹出队列；最后将两次扫描得到的b
序列合并即可得到答案。这样做可以保证字典序最小且和最大。
我在写完代码后提交了一发AC，并且没有任何WA或者TLE。
剩下的时间我就开始看第三题【CF-1766H】The Great Wall of China II。这题给出了一个长度为n
的序列a
和两个整数k,m
（其中m < k < n
），要求找出一个长度为k
且字典序最小的子序列b，使得b_i \leq a_i对于所有i \in [1,k]成立，并且\sum_{i=1}^{k} b_i最大，同时满足b序列中任意m+1个连续元素的和不超过一个给定的常数c。这题看起来比第二题要难一些，但其实也是可以用单调队列优化的。我的思路是先预处理出a序列的前缀和s，然后从左到右扫描a序列，并维护一个单调递增队列q_1存放当前可选元素，并且保证q_1.size() + n - i \geq k - j（其中i,j分别表示当前扫描到a,b 序列中第几个元素），然后每次从q_1.front() 取出最小元素作为b_j 并将其弹出队列；同时维护一个单调递减队列q_2 存放当前已选元素，并且保证q_2.size() \leq m + 1 ，然后每次检查是否有s[q_2.back()] - s[q_2.front()] > c ，如果有则将q_2.front() 弹出队列；最后判断是否有j = k 且s[q_2.back()] - s[q_2.front()] \leq c ，如果有则说明找到了一个合法的b 序列。这样做可以保证字典序最小且和最大。 我在写完代码后提交了一发AC，并且没有任何WA或者TLE。
Day1 的比赛结束后，我得到了300分的满分，排名第一。我非常高兴，觉得自己离金牌又近了一步。
Day2
Day2 的题目难度较高，有一些比较新颖或者复杂的思路。我在开场后先看了第四题【CF-1766I】The Great Wall of China III。这题给出了一个长度为n 的01串s 和两个整数k,m （其中m < k < n/3 ），要求找出一个长度为k 的子序列t，使得t中任意m+1个连续元素的和不超过一个给定的常数c，并且t与s的汉明距离最小。这题我想了很久，最后发现可以用二分答案+滑动窗口的方法解决。我的思路是先枚举汉明距离d （从0到k ），然后对于每个d ，判断是否存在一个合法的t 序列满足条件。判断的方法是先将s 中前d 个0变成1，然后用一个长度为m+1 的滑动窗口扫描s ，每次检查窗口内有多少个1，如果超过c 则说明不合法，否则就将窗口右移一位，并将下一个0变成1（如果有）。如果扫描完毕没有发现不合法的情况，则说明存在一个合法的t 序列。这样做可以保证汉明距离最小。 我在写完代码后提交了一发AC，并且没有任何WA或者TLE。