Day 1

题单：蓝桥杯模拟赛 2

这次的节奏还可以，没有莫名其妙地浪费大把时间 debug。虽然一直知道排名不重要，但是看到自己是 19 名的那一下还是有点小失落的。只是一些不合理的情绪吧，我也没怎么学算法，又凭什么做得比别人好呢？其实，我并不觉得这次做得差，只是多亏了这次题目的描述过于严谨、精美和符合语境逻辑。

以下是补题：

解码

第一题只有 10 分，也太搞笑了吧？提示一下，重复次数大于等于 0，小于等于 9 哟。

成绩分析

谢谢，得分也帮我“四舍五入”一下吧。

整除序列

什么，前三题没一道做对？好吧，不嘴硬了，这题确实漏条件了，数据范围是 $[0,10^{19}]$ ，我没看到，用的整型。这个故事告诉我们：做题一定要确认数据范围。

Day 3

题单：SMU Winter 2023 Round #3 (Div.2)

这次题整体比较简单。我相比于之前，审题意、审范围都好多了，这才是刷题比赛的意义。不过有些小细节经常忽略，还记得上周英文赛的调温度那题吗？和今天的三元组一样忘记改了，以后复制粘贴的地方要注意修改。此外，今天没怎么动笔，可能题目比较简单，但是有几题是 TLE 了再改的，如果一开始就思考到位的话，也许就会采用更优雅的算法，这才是算法题的真谛。

以下是补题：

三元组

为了方便，复制粘贴循环，结果第三层循环的初始化没有修改，应当承接第二层循环，却和复制的第二层一样承接的是第一层循环，导致提交了很多次都没过。

直播获奖

一看完题目就很自然地想到了做法，排序嘛，取数嘛，谁不会？却没有思考这种算法的时间复杂度会不会太大，能不能优化。在 TLE 之后我才反省这个问题，又是改输入输出，又是该排序插入，却没有触及问题的本质——数据结构（数据的存储和读取方式）的妙用。更好的做法是：明确了分数的上线是 600，而且分数是非负整数，于是可以开一个数组来记录所有分数对应的数量，从后往前，取到需要的位置。在提交之前，我并没有意识到，排序和插入都会带来额外的耗时。而这些，都可以通过一个以分数为下标的数组巧妙避免。当一个数组的重复元素远多于数组的值域时，应该想到，是否可以通过改变存储方式来进行整合呢？

采药

经典的 01 背包问题。我曾以为我完全地领悟了 01 背包和完全背包，然而这次需要完整地写代码的考验提醒我：我还有太多没有想透的底层细节。这次的问题是，在遍历物品之前，是否要对物品进行排序？答案是不需要，对于任意物品，最优解一定在“取该物品，剩下的最优”和“不要该物品，剩下的最优”中诞生，层层往前推，0 个容量或 0 个物品一定是最优解。以下是超级经典的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int dp[1005], w[1005], v[1005], n, limit;
int main()
{
    cin >> limit >> n ;
    for(int i = 1; i <= n; i++ ) cin >> w[i] >> v[i] ;
    for(int i = 1; i <= n; i++ )
        for(int j = limit; j >= w[i]; j-- ) 
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    cout << dp[limit] ;
    return 0;
}

异或橙子

这题设计了两个考点：

  1. 实现，需要了解异或的性质。异或运算满足交换律（某一位的结果只与那一位上 0 和 1 的数量有关，与顺序无关）和结合律（同理，与顺序无关）。此外， $a\oplus0=a$，$a\oplus a=0$；
  2. 优化，需要在快速求前缀和与快速修改之间寻找平衡。如果只需要前者，直接用前缀和数组无疑最快，但它的修改很慢。此时的人们不得不寻找一种满足二者平衡的存储方式，树状数组便诞生了······

Day 5

题单：SMU Winter 2023 Round #4 (Div.2)

做题分为思考和写代码两步，这次比赛让我明白：思考又可以分为实现（建模）和优化，有时实现并不难优化难，而难的优化恰恰就是题目的考点，所以每一题要尽量看透本质再动键盘，例如：Day 3 的直播获奖。还有一个收获：数据结构和算法都是先从问题中诞生，再被用来处理相似问题的。例如 Day 3 的异或橙子，我根本不知道什么树状数组，但是我知道我需要一种能够平衡快速求前缀和与快速修改的数据结构，恰巧树状数组就能解决这个问题。反过来看，图论的题目我遇见不少了，却从来没做出过，甚至从来没尝试过，因为我认为自己”还没学过图论“，然而正确的想法应该是：这个问题需要一个特定的模型，图论适合，那就它了。”万一目前没有适合的呢？“这是每一个算法（数据结构）发明者都思考过的问题。

以下是补题：

Hotpot

做这题时，我已经有一点点的优化思想了，本来想开 vector 存菜，联想到 Day 3 的直播获奖就立马想到可以开一个数组来记录菜的状态。然后发现菜的状态只有”有“和”无“两种，所以可以用 bool 数组？如果往优化更深一步想：两圈下来，bool 数组回到初始状态，而且每个这样的两圈对于 happiness 的改变都是相同的，如此，m 个动作就可以大大减少到小于 4n。

总结

  1. 复制粘贴的地方要仔细检查；
  2. 做题分为三步：思考实现、思考优化和代码实现；
  3. 现实的需求催生出更适合问题的算法和数据结构。

因为没学过某个领域而逃避问题的人是可悲的；因为直面问题而进入甚至开创某个领域的人是可敬的。