寒假新生训练第三周题解

kblack edited 6 年，9 月前

A. 获取你的维生素

签到，注意输入输出格式和方式，注意浮点数的正确舍入，没有其他思维需求。

B. 都市地平线

你可以应用扫描线的思想，想象一条垂直于地平线的直线从左到又扫过整个平面。对于第 $i$ 栋高楼，他在 $A_i$ 进入我们的视线并在 $B_i$ 离开，而每个连续区间图案的高度则取决于最高的那座楼。因此我们需要一个可以动态插入删除，同时获得当前最大值的数据结构，堆和平衡树都能很好的符合我们的要求。在需求如此简单的情况下，无论从时空复杂度、实现复杂度、调试复杂度，手写堆或平衡树是得不偿失的，这个故事告诉我们 STL大法好！。

当然你也可以可以在对区间离散化后，按照楼高从小到大对区间赋值（通过线段树）并最后求和，然而这将会更加复杂并拥有更大的常数。

C. 排版

签到，首先你需要正确分离出所有的单词，之后只需要贪心地构造每一行，在每一行塞下尽可能多的单词的情况下，正确计算空格个数量即可。

D. 抢椅子

这几乎是一道训练中的签到题原题，原题是在一直线上排列的椅子，作为一名星际玩家，成功现场造题并坑队友（光速逃

按照期望的定义我们可以知道我们在求的是 $exp(x) = {\frac{\sum_{i=1}^{c}{dis_i(x)}}{c}}$ 的最小值，其中 $dis_i(x)$ 是位置 $x$ 到最近的颜色为 $i$ 的椅子的距离。

考虑 $dis_i(x)$ 的随 $x$ 变化的规律，$x$ 向右移动一个位置：
- 若离 $x$ 和 $x+1$ 最近的颜色为 $i$ 的椅子相同时，$dis_i(x)$ 会 $+1$ 或 $-1$，当 $x$位置的椅子颜色就是 $i$ 时，之后 $+1$ 或 $-1$ 的状态需要改变。
- 若离 $x$ 和 $x+1$ 最近的颜色为 $i$ 的椅子不同时，$dis_i(x)$ 会 $-1$ 或不变，之后 $+1$ 或 $-1$ 的状态需要改变。
换句话说，dis_i(x) 是一个分段函数，且所有分段函数解析式（或者说变化方向）最多变化 $2n$ 次（因为第一类变化每把椅子最多一次，第二类变化同理）

所以我们可以通过求出 $exp(1)$ 后，按 $dis_i(x)$ 的变化，依次计算出之后的 $exp(x)$，取最小值即可。

以上是一直线的解决方案，环上怎么办？好办的呀！把你椅子们在左右各自复制一遍就好了！

E. 密码碰撞

简单的计数问题有一个特点，当你找到了正确的计算贡献的对象和方式的时候，你就完成了问题的一半。

枚举出每个字符串有最多 55 个子串并分别去重后，再统计每个串的出现次数（可以使用map）。我们就可以通过 $pwd_j$ 在这些子串中的出现次数，知道有多少个符合条件的 $i$。然而 string 的操作、比较等都十分的缓慢，直接使用 map<string> 常数【可能】会过大。

如果我们把字符串看作一个 $27$ 进制数，从 a 到 z 分别代表 1 到 26，将其转化为 10 进制后，就可以得到一个 long long 范围内的整数，这可以大大优化 map 或 sort 需要的比较操作的常数，从而得到更快的速度。

将一个字符串看作一个高进制数并计算其值的方法，一般被称作字符串哈希，是字符串的重要处理方法，在得到两个字符串的哈希值后，可以在 $O(1)$ 的时间内确定两个字符串是否相等，并比较某种大小。然而，若字符串的长度十分长，哈希后得到的整数可能会十分庞大，我们可以将其对一个大质数取膜（或利用自然溢出对 $2^{64}$ 或 $2^{32}$ 取膜），也就是将两个哈希值在膜后的剩余系中确定是否相等（此时无法比较大小）。两个不同值在剩余系中碰撞的概率很小，通常情况下我们可以几乎认为他们甚至不会碰撞。但当需要比较的串极大极多，或有刻意的构造时，我们还是需要通过多个哈希（对不同值取膜）或再通过其他方法才能减少/消除碰撞。

9 0