一、总体情况
- 考试分数极其不稳定，好的时候300多分，差的时候100分
- 没做出来的题很多都是DP和搜索，也有一些思维和数学
二、题解
Day 1
A
按照题意模拟即可，但要做一些优化
- 本题的复杂度瓶颈再 $a$ 和 $b$ 互质，而这种情况下，要想办法算出减去 $1$ 的个数
- 设个数为 $x$，可以得到： 当 $(a-b)\mod d = 0)$ 时，$x=\min(x,a\mod d)$
B
最小生成树模板，将边建出来后跑一边kruscal或prim就可以了
C
首先，可以先算出每头奶牛跑的圈数，然后 $O(n)$ 算出当前的答案（不考虑小数），但这样会多算。因此，我们发现，圈数在整数一样的情况下，小数部分如果是逆序的，就会多算 $1$。所以，求一遍小数的逆序对，用答案减去即可
D
区间DP
- 状态定义：设 $f[i][j]$ 表示在区间 $[i,j]$ 中所有可以改成合法括号序列的方案中，花费最少的方案的花费
- 状态计算：$f[i][j]=\min(f[i+1][j]+w[i,j],f[i][k]+f[k+1][j])(k\in [i,j - 1])$，其中，$w[i,j]$ 表示将括号 $i$ 和括号 $j$ 匹配的最小花费
Day 2
A
暴力枚举 $A$ 即可
B
使用DP
- 状态定义：令 $f[i]$ 表示飞到第 $i$ 棵树的所有情况中，所要耗费的最小的劳累值
- 状态计算：$f[i]=min(f[j])+1\ \ \ \ \ \ \ (h[j]\le h[i])$
或 $f[i]=min(f[j])\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (h[j]>h[i])
C
使用并查集
- 设在第 $i$ 位时开始两个序列不一样，则之前的每个数都对应相等，可以使用并查集将这些数维护成一个集合，最终统计答案即可
D
看到题目首先想到前缀和
- 若要找出一个区间 $[i,j]$ 平均值不小于 $k$，则：
$$
sum[i]-sum[j-1]\ge k*(i-j+1）
$$
用 $j$ 来替代 $j-1$，则：
$$
sum[i]-sum[j]\ge k*i-k*j
$$
$$
sum[i]-k*i>=sum[j]-k*j
$$
随后按照上面的式子计算即可
Day 3
A
先构造一个答案字符串 $ans$，为了字典序最小，初始化成 $0$
接下来，先算出两个串分别和 $ans$ 的距离 $d_1$、$d_2$
再从后往前枚举答案串，让 $d_1=d_2$ 即可。
每次修改答案串上的一个值，$d_1$ 和 $d_2$ 要么同时加 $1$，要么一个加 $1$，一个减 $1$，所以，如果距离差是奇数，就直接输出 $-1$
B
先算出 $0$ 和 $1$ 两种奶牛数量的前缀和，然后，如果想得到答案，则：
$$
sum0[i]-sum0[j]=sum1[i]-sum1[j]
$$
$$
sum0[i]-sum1[i]=sum0[j]-sum1[j]
$$
预处理出所有的 $sum0[i]-sum1[i]$，然后求解即可
C
不难发现，$s$ 到 $t$ 的最短路和 $s\mod n$ 到 $t\mod n$ 是一样的。然后用Floyd算法求解
注意要特判 $s\mod n=0$ 或 $t\mod n=0$
D
可以先枚举前两个动物，就可以递推出第三个动物，一直推下去，最后看最后的动物和开头的之间的关系符不符合题目要求
Day 4
A
可以先枚举第一行填的情况，之后往下递推：
- 如果 $[i,j]$ 的位置灯是灭的，就把 $[i+1][j]$ 变换一下状态，因为这样在这一排只会影响到 $j$
- 递推到最后看最后一排能不能全部点亮就行\
B
枚举往左走后或往右走后的转折点，算出时间取最小就是答案
C
区间DP
- 状态定义：令 $f[i][j][k]$ 表示将区间 $[i,j]$ 分成 $m$ 个区间之后的最大值/最小值
- 状态计算：枚举是从点 $k$ 开始，将区间分成 $[i,k]$ 和 $[k+1,j]$，随后按照题目要求计算答案就可以，要用前缀和优化区间和
D
Day 5
A
使用DFS+状压DP
int dfs(int row, int column, int s, int next)
// 行、列、上一列竖着放的（二进制）、这一列竖着放的（二进制）
之所以要记录上一列和这一列竖着放的，是因为上一列竖着放的地方这一列不能放
B
先找到一段最长连续上升子序列（数字连续）$lis$，然后可以将整个数列分为 $3$ 种数：
- 在 $lis$ 中
- 比 $lis$ 的最小值要小
- 比 $lis$ 的最大值要大
其中，第二种要移动到队首，第三种要移动到队尾
答案就是 $n-len(lis)$
C
和 $Day2$ $D$ 题一模一样
D
按题意模拟即可，注意：一个人有可能换多次队伍
三、补题情况（2024年9月6日）
还差 $Day2\ C$ 题、$Day4\ C$ 题和 $Day5\ A$ 题未补
计划在 9 月 9 号之前补完
四、下学期学习计划
主要还是要多练一些DP和DFS的题，这几场考试很多DP和DFS的题丢分
