第二次双周赛详解
第二次双周赛详解
BrotherCall
·
2023-11-10 22:58:52
·
个人记录
难度排序：\text{A} \approx \text{D} < \text{B} < \text{C} < \text{E} < \text{F}
关于通过人数：\text{C} 题不符合预期，其他比较正常。
小北的包
不会建议 ~~重开~~ **重新看一遍杭电的课**。
由于杭电课里有，网上题解也有很多，属于典题中的典题，所以不说了。
如果对背包或者 $\text{dp}$ 很感兴趣，但一直理解不了，只能背板子，欢迎在 qq 上找我，或者线下到综合楼 1121 和我讨论。
---
# 铺瓷砖
其实是一道 $\text{dp}$ ，但打表找规律也能做。
不过打表找规律是小学生做题法，你已经是一个成熟的大学生了，自然要从理解入手做题。
第一步，是在脑子里幻想出一个 $2 \times n$ 个方格的长条。
它可以长这样 $\uparrow$ 。
其实求方案数的 $\text{dp}$ 跟高中的组合数没什么区别，重要的是从哪里切入。
一个很自然的想法就是把这个长条从最左端开始填，直到填满。
首先，最左端那个 $2\times1$ 的格子得填满吧，就是最左端那一列。
有几种填的方式呢？
**第一种**是直接竖着贴一个 $2\times1$ 的瓷砖。
**第二种**是贴两个横着的 $2\times1$ 的瓷砖（相当于填了 $2\times2$ 的格子，但也满足填满了最左边的那一列）。
**第三种**是直接贴一个 $2\times2$ 的瓷砖。
没有其他的贴法了。
以上是静态地思考这题的性质。
好，既然这题是动态规划，我们就化静为动，来动态的考虑这个问题。
不管用哪种贴法，贴完之后，右边所有空的位置会形成一个新的宽度为 2 的长条瓷砖。
对于这个新的长条瓷砖，我们可以用同样的“贴最左端一列”的思路来不断地向右扩展。直到前 $n$ 列全填完。
根据这个思路，我们设 $f_i$ 为恰好填完前 $2\times i$ 个格子的总方案数。
## 填表法
填表法就是对每一个还未计算的状态，找到它所有所依赖的状态，从所依赖的状态转移过来。
对于恰好填完前 $i$ 列，一种方案是根据上面的**第一种**填法，从填满 $i - 1$ 列的情况转移过来。另两种方案是根据上面的**第二 三种**填法，从填满 $i - 2$ 列的情况转移过来。
所以得到转移方程 $f_i$ = $f_{i - 1} + 2 f_{i-2}$ 。
初始值可以设为 $f_1 = 1/f_2=3$ ，然后从 $i=3$ 开始转移，一直推到 $i=n$ 。
核心代码：
```cpp
f[1] = 1; f[2] = 3;
for(int i = 3;i <= 30;i ++){
f[i] = f[i - 2] * 2 + f[i - 1];
}
```
还有种初始化方法是，初始值设为 $f_0 = 1$ ，就可以从 $i = 1$ 转移了，具体为什么可以这么做，大家开动脑筋吧！
## 刷表法
刷表法是用已经更新过的状态去更新未更新的状态。
转移方程为 $f_{i+1} = f_{i+1} + f_i$ ，$f_{i+2}=f_{i+2}+2f_i$ 。
这种做法更易理解，更自然，感兴趣的同学可以自己研究。
---
# 小源爱写题
简单解释下状态这个概念，**状态就是用一些关键信息描述一个结果**，这个结果可以由不同的过程得来，而不同的过程数就是方案数。
状态一般放在 dp数组 的维度里，这样就可以进行不同状态的转移，而这个 dp数组 状态所对应的数值就是方案数。
所以我们考虑这题的状态，“天数”/“一共写的题个数”/“最后一天所写的题的个数”，可以用三个维度刻画状态。
不难发现“天数”这个状态没用，因为要求的结果和“天数”无关。仅用“写题总数”就能刻画所有状态，而 “最后一天所写的题的个数” 是用来转移的必要状态（要满足从上一天比该天写得少的状态转移过来，没有这一维度就相当于丢失信息，无法转移）。
设 $f[i][j]$ 代表一共写了 $i$ 题，最后一天写了 $j$ 题的方案数。
转移方程为 $f[i][j] += f[i - j][k]$ ，其中 $i$ 为 $1\to n$ ，$j\leqslant i $ ， $k < j$ 。
解释下为什么这么转移，最外层 $i$ 很显然，从少的题数转移到大的题数，满足无后效性。中间一层由于我们枚举的是最后一天写 $j$ 题，所以答案为所有倒数第二天写的个数比 $j$ 小的状态之和。这里用一层循环 $k$ 就可以实现，$k$ 表示枚举倒数第二天的写题数。
核心代码：
```cpp
f[0][0] = 1;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= i;j ++)
for(int k = 0;k < j;k ++)
f[i][j] += f[i - j][k]
```
答案就是一共写 $n$ 题，最后一天写任意道题，的方案数的总和，减一（至少两天，所以要排除一天全做完的情况）。
时间复杂度 $O(n^3)$ ，可以通过。
（ps：这题前缀和优化可以做到 $O(n^2)$ ，有感兴趣的同学可以自己研究）。
---
# 以上是本周学习的算法题。
# 下面是 $\text{cf}$ 类型题目，旨在更贴近比赛，锻炼思维。
---
# 自动补全
暴力是成为算法竞赛选手的第一步。
先用 sort 给所有字符串排序，然后逐位比较即可，匹配了一个就可以直接输出答案结束程序。
用 C++ 自带函数 substr 同样可以实现，但由于我不会所以大家自己百度。
# 数组
贪心思维的利用，非常有意思的一题。
先枚举每一位 $i$，代表我钦定这位 $a_i$ 为最大值。
接着，扫一遍所有操作，如果第 $i$ 位没有 $-1$ ，则执行这个操作。
每扫一遍之后，如果第 $i$ 位不是最大值，说明这一批操作不满足假设，跳过。
如果第 $i$ 位是最大值，则拿此时的最大值减最小值更新答案。
此题到此结束。
时间复杂度 $O(n(n+m))
最小生成树
这题是你们滴 N神 用来打击竞赛队（尤其我）的自信心的，难度评级 2100。
考虑 \text{Kruskal} 最小生成树
先对于边权排序，对于边权为 i 的边进行合并两个森林的时候，设合并前有 m_i 个森林，合并后有 n_i 个森林。若边权为 i 且边连接的两个点不联通的边一共有 v_i 个，则 ans=\sum\limits_i(v_i-m_i+n_i)
现考虑其正确性：
对于边权为 i 的边进行合并时，一定有 m_i-n_i 条边被留下作为生成树的边，而其余的且连接的两个点不联通的边任意一条都可以替代留下来的边。所以这些边必然需要加一。不难发现这也是最小的方案。充分性得以保证。