Week3_250303~250309_OI日志（待完善）
Week3_250303~250309_OI日志
- 250303
- 大致安排
- 题目
- 字符串hash
250303
大致安排
上午讲了字符串hash初步，感觉很NB，下午补题，但因为字符串太菜，补题速度过于缓慢。
题目
- P3370 【模板】字符串哈希
- U461211 字符串 Hash（数据加强）
- P3763 [TJOI2017] DNA
字符串 k k k 次失配问题，在这里 k = 3 k=3 k=3 ，直接枚举起始位置，并三次二分失配位置即可，字符串hash判断即可。但需要注意一点hash复杂度可能凭空多log，时间复杂度从而达到惊人的 O ( T ⋅ n ⋅ 3 ⋅ l o g 2 ( n ) ⋅ l o g ? ( ? ) ) O(T \cdot n \cdot 3 \cdot log_2(n) \cdot log_?(?)) O(T⋅n⋅3⋅log2(n)⋅log?(?))，常数飞起。这时考虑到有前几位均不失配的概率很小，且数据比较随机，所以直接手动特判，而不上二分。或者是，改成单模数，不过我一般设 998244 8 53 998244\color{red}8\color{black}53 998244853。 - P4824 [USACO15FEB] Censoring S
考虑这个操作，就是个栈，而且每次删的字符串长度固定，考虑如何判断何时删，在栈上维护一个动态的字符串hash - P4407 [JSOI2009] 电子字典
这道题有 2 2 2 种解法：
方法一，把操作一次后的字符串搞出来放入先前建好的Trie树上跑查询。
方法二，hash扔进map 特别注意这里的操作二"+" 必须将原字典字符串操作扔到一个新的map进行查询，否则凭空 26 26 26 倍常数，导致TLE - AT_arc172_c [ARC172C] Election
数学，hash均可解决