第一课

A - 按钮变色

注意到数据范围极小，所以可以状态压缩整个矩阵然后用 BFS 计算答案。

B - 最短连续子序列

经典的双指针练习题，注意双指针的条件。

1
2
3
4
5
6
7
8
int l = 1, r = 0, tot = 0, ans = 1e9;
while(r <= n) {
    while(r <= n && tot + a[r] < S) {
        tot += a[r++];
    }
    ans = min(ans, r - l + 1);
    tot -= a[l++];
}

在上面的这段双指针代码中，因为第二个判断条件的错误，使得 $r$ 在跳出循环的时候永远保证着 $tot < S$ 的性质，与题目要求不符。并且从代码的内容和变量名声明中可以看出，这里表示的区间 $[l,r]$ 应该是一个左闭右开的区间，计算长度直接用 $r-l$ 。

1
2
3
4
5
6
int tot = 0, ans = 1e9;
for(int l = 1, r = 0; l <= n; l++) {
    while(r <= n && tot < S) tot += a[r++];
    if(tot >= S) ans = min(ans, r - l);
    tot -= a[l];
}

C - 异或和

题目让我们求满足条件的区间数量，考虑双指针。

异或被称为不进位加法。所以当若干个数字进行异或操作和求和操作时，满足异或和不大于总和，以此进行双指针，即一旦出现了异或和小于总和的情况，那么在参与求和的数都是正数的情况下，异或和不在可能等于总和，直接跳出循环。

接下来如果我们找到了一个从 $l$ 开始最长的满足异或和等于总和的子串，很显然他们不是最终答案，举个明显的例子，所有单个元素的序列都满足异或和等于总和，但是他们大概率不会是从 $l$ 开始最长的满足该条件的字串。所以考虑如何快速统计。

因为每次双指针左端点固定向右移动一，所以直接以 $l$ 为起点统计每个子串的后缀，这一定是不重不漏的，正确性显然。而一个序列后缀的数量就是它的长度。

D - 最大余数

$n$ 的大小很敏感，一般在 $40$ 左右都可以是折半搜索的范畴，考虑算法的可行性，两边的序列可以通过二分快速得出答案，所以这是一道折半搜索题。

确定做法以后考虑细节，统计了两边的所有情况以后，要合并两边的答案，很显然是通过二分找到与其相加模 $m$ 的最大值。而一个数取模 $m$ 后最大值就是 $m-1$，所以可以把两边的结果都模 $m$ 之后找到最后一个小于等于 $m-1-right$ 的值，这题就解决了。

上面的式子用代码表示出来应该是形如 upper_bound - 1 的，但是为什么就不会 RE 呢？因为右边固定会有一个什么都不选的选项，也就是零，所有数都是正数，不可能会出现 upper_bound 指向开头的 $0$ 位的情况，自然不会 RE 。

第二课

A - 最小字典序

大力贪心，但是遇到两个相同的字符，就不好判定怎么选了。考虑选择这个字符的后果，我们肯定希望这次操作可以给我们带来更多字典序较小的字符，所以我们可以看看两个字符同时向字符串中心移动第一个不同的字符谁大谁小，很显然小的数更加符合我们选择的要求，但是如果真的完全一样的话那就可以随便选了。

B - 雷达

略有思维。

注意到如果一个点可以被选到（即纵坐标在雷达半径以内）那么一定可以在数轴上找到一个区间来将其收纳。这样我们就可以从输入中提取出若干个区间，对题目经行了初步的转化。

接下来如何考虑呢？这究竟是区间选点还是点选区间？从题目的语境来讲，可能会有人误认为是区间选点，即选择若干个区间使得所有点被覆盖。但别忘了我们以及转化了题目，这里的区间对应的就是一个点，我们的目标是设置一个雷达使得其覆盖尽可能多的点。所以题目转化为使用点覆盖所有区间，到了这里题目就变成模板了。

C - 机器分配

陷阱题。

很显然一个任务，它即使带满了 $y$ 也只能提供 $400$ 的价值，但是但凡 $x$ 多一，都可以提供 $500$ 的价值，所以说对于任务来说，我们一定是优先选择 $x$ 大的，其次选择 $y$ 大的。

接下来考虑机器如何匹配。一个错误的想法是，将机器和任务都根据 $(x,y)$ 排好序以后，能匹配就匹配。这个算法的错误在于，如果这个最大的任务和最大的机器的 $y$ 差了很多，那么就大大地了浪费了机器 $y$ 的作用。可能我们会因为这个错误失去匹配一个低级的任务的机会。因为不论是大小，我们尽量匹配更多的任务，一定是更加优秀的。

延续上面的思想，不难想到把任务和机器都以价值为单位从大到小排序，对于每个任务优先匹配 $x$ 大于它且 $y$ 与它最接近的那个机器，这样就是正确的算法了。

D - 田忌赛马

经典题。

对于田忌最强和最弱马与国王最强最弱马的关系经行大分讨：

  1. 田忌最强马比国王最强马强，直接赢
  2. 田忌最强马比国王最强马弱，用最弱换最强
  3. 田忌最强马和国王最强马一样强，开始分讨最弱马：
    1. 田忌最弱马比国王最弱马强，直接赢
    2. 田忌最弱马比国王最弱马弱，以弱换强
    3. 这时候依然还有两个不同的情况：
      1. 如果田忌所有的马全部都一样了，那一定是没有任何策略的必要了
      2. 否则，就可以以弱换强争一争

田忌赛马的精髓就在于以弱换强来争夺一个胜利的可行性，因为是要赢了就可以把前面输的前赚回来，而一旦强对强就有可能一输再输。

E - 行列快乐值

并不像贪心题的贪心。

行和列互不影响，所以可以分开处理。设定 $sum1[i]$ 表示进行 $i$ 次行操作的最大收益，$sum2[i]$ 表示进行 $i$ 次列操作的最大收益。这个是可以通过弹性求得的。每次从一个大根堆里面取出来一个值即可。

然后从我们会发现忽略了行与列的互相影响，这个可以分开计算，就像两条交叉的小路面积可以分别计算两个长方形再减去中间的部分一样，我们同样可以使用类似的手法得出答案：$sum1[i]+sum2[k-i]-i\times (k-i)\times p$ 。

这样的话这道题就结束了。

F - 取数求和

非常暴力。

直接大力使用哈希+广搜跑出前 $n$ 个状态即可，注意哈希的模数。

第三课

A - 水果店

模拟题，考察 map 自动排序与 map 的遍历

B - Set

模板题，考察 multiset 的使用与判空

C - bitset

模拟题，考察 bitset 的使用

D - 举行切割

Set 的综合应用题。

分别开一组 set 和一组 multiset 分别表示切割线的位置和块的大小，模拟即可。