某游记 | Day 02

2024-03-31 10:11:52

章零 · 序言

今天是 Day 2，主要讲简单字符串（

Hash 是字符串常用的算法，主要思想就是把一个不容易储存的数据转为便于储存的哈希值。

当然由于记录的时候少了一定的信息，会出现哈希冲突，避免方法就是扩大值域并增强随机，本来是想写自然溢出，但是没想到~~自然溢出已经死了。~~

还是老老实实双模数 Hash 吧，实现也很简单，就是 hash1[i]=hash1[i-1]*p+s[i]%mod1,hash2[i]=hash2[i-1]*p+s[i]%mod2; 即可。

给出一个字符串 \(S\)，按照字典序后缀大小排序，然后逐个输出。字符串长度 \(1\le|S|\le 10^5\)。

考虑对于两个字符串 \(A , B\)，如果 \(A < B\)，那么必然有一个位置 \(x\) 满足 \(A[1 \cdots x-1]=B[1 \cdots x-1],A[x] < B[x]\)，然后二分去枚举这个位置。这样就能判断两个后缀之间的大小，于是就能上快速排序了。

题目链接。

观察操作发现所有操作都是可逆的，操作都能转化为将一个 \(0\) 不跨过的其它 \(0\) 的左右移动。

给出一个序列 \(a\)，定义一个数 \(x\) 在区间 \(a[l \cdots r]\) 中是炫酷的，当且仅当它出现了奇数次。

求满足条件的 \(a\) 的子区间个数使得区间内的所有数都是炫酷的。

根据定义发现，如果一个数出现两次相当于没出现过，于是我们用集合 Hash 来直接表示某个子区间。

对于原序列，每个位置对应的权值做前缀 \(\tt{xor}\) 和。

题目链接。

用秦九韶算法把原方程不断提取出来 \(x\)，因为本题 \(a_i\) 的范围很大，于是我们需要在输入的时候就取模来防止很慢的高精度成为算法瓶颈。

通过 Hash 函数计算一个 Hash 值，并将数据存储在 Hash 值所对应的链表中。

unordered_map 就是基于 Hash Table 来实现的，C++98 可以用#include <tr1/unordered_map> 和 using namespace tr1; 来使用。

题目链接。

枚举 \(S\) 的后缀作为 \(C\)，考虑将剩余部分划分为 \((AB) ^ i\) 的方案数。

用 KMP 可以找到每个前缀最长的 nex，然后将 nex 取反即为它的最短循环节，并且其它所有的循环节都是这个循环节的若干次重复。

题目链接。