夏令营8.1总结

今天主要讲了啥都不是（杂题）其实是模考。

但是全班这个断网的模考，对惨的就是我。由于集训带了一个台式机，所以没法搬到考试的地方，就只能用备用的电脑。

题目

T1

这题还是比较简单（其实是纯签到题）。唯一可能错的原因就是把输出的内容抄错了。

代码就是输入每个数，判断是否为0，如果不为0，就去过的地方加一。最后判断去过的地方的数量，输出对应的内容即可。

T2

这题的正解其实就是暴力枚举。

但是考试的时候不知道为什么看了半天题目才写出来。

一开始考虑使用六层循环，但是寻思着时间复杂度就爆炸了，就仔细地观察了一下样例。发现由于抹布是正方形的，所以如果把地板切成很多片，每一片都单独看的话，每一个连续的脏东西区间的长度都必须要$%k==0$才能保证可以刚好擦完。

自己在考试的时候举了很多例子，也没能证伪。就按照这个方法写了，其实考试的时候是怕复杂度爆炸的，但是实际上没有问题（或许是因为数据太水了？），居然跑出了所有点都不超过 10ms 的时间。

T3

下面的这两题在模考的时候没做出来，所以会比较偏题解。

核心思路：目录树构建与递归遍历

1. 目录树的构建：

• 通过解析输入的目录路径（如/a/b/c），将其拆分为多个层级的父目录（如/、/a/、/a/b/）。
• 用双向映射（m1 和 m2）将目录路径与唯一标识 id 关联，便于处理。
• 用邻接表vec存储目录之间的父子关系，用集合 s 记录每个目录的直接子目录。

2. 目录大小计算：

• 采用深度优先搜索（dfs）从叶子目录向上计算每个目录的总大小（sizee），即当前目录大小加上其所有子目录大小之和。

3. 递归判断与输出：

• 从根目录（/）开始递归处理每个目录（solve 函数）。
• 对于每个目录，判断其最大子目录的大小是否达到limit：
  • 若达到，则标记为需要展开（输出-），并递归处理其所有子目录。
  • 若未达到，则标记为不需要展开（输出+）。

T4

还没搞懂QwQ。

总结

今天的模考还是比较神奇的。

T2不知道为什么就过了

这次，模考，我觉得收获还是比较大的。

首先，核对答案时要注意哪些小细节。比如T1，如果抄错了一个字母或大小写搞错了就直接爆炸了。

还有人在这种IO赛制的时候会把用户的文件夹名字写错。这样就直接爆0了。

如果输入输出文件名字写错了，那么后果也是灾难性的。还有人忘记加上文件名后面的.in于.out。