请改蓝
查看原帖
请改蓝
234992
SkyWave楼主2023/3/19 12:44

理由:这道题首先 trick 就非常的好玩且冷门。

首先最显眼的就是题目限制的值域为 'a' - 'r',所以算法的复杂度肯定与此相关。又注意到一个非常好玩的性质,举例,如果两个字符串包含 abc 字符时字符串相同,那么他们包含 abc 的子串后的结果也一定是相同的,即他们包含 ab、ac、bc 时也一定是相同的,反之亦然。也就是说如果我们将询问字符串降解成长度相同的所有子串,判断这两个字符串是否包含这个子串的所有字符时结果相同,那么就会避免大量重复计算。

所以我们需要预处理两个字符串中包含长度一定的子串重的所有字符后是否相同。预处理哪个长度合适呢?注意时间复杂度,既要平衡预处理也要平衡询问。最终发现预处理长度为 2 的子串时,预处理需要枚举两个字符串与所有长度为 2 的 'a' - 'z' 串,所以时间复杂度为 O(max(si)2×max(s,r))O(max(s_i)^2 \times max(|s|,|r|)) 。询问需要降解字符串,所以为 O(max(si)2×Qmax(s_i)^2 \times Q) 的复杂度,综合下来原子操作大约为 18 * 18 * 10'0000 = 3240'0000 < 1e8,如果值域为 'a' - 'z' 时直接爆炸。

这种 trick 同时既有 dp 与倍增的思想,属于一道非常好的提高组选手练手题,思维难度为绿,代码难度为绿,所以定位为中位蓝。

2023/3/19 12:44
加载中...