2023省选训练总结

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/17245901.html

省选联考 2022

预处理器

• 模拟题，要熟悉string和unordered_map 的的使用

• 由于保证输出长度限制，所以可以暴力递归完成

//abcdef
s.substr(1,3) // bcd
s.find("cde",1) // 2
s.find("c") // 2

• 处理技巧：一串一串字符分别处理（单词之间不会互相展开）；记得标记已经展开

填树

• 考虑暴力做法，显然可以确立一个长度为 $K$ 的移动区间，每个点只能在这个区间内取来统计方案

• 但是可能出现重复情况，可以钦定此区间最小值必须取，即用 $[l,r]$ 减去 $[l+1,r]$ 的情况，这一步可以与用树形dp优化到 $O(nK)$

• 显然，对于规定区间 $[L,R]$ 在移动过程中，每个点可取范围 $[l_i,r_i]$ 的范围要么+1，要么不变，要么-1，而且这个变化必然是连续的，所以其实每个点的变化可以用三个一次函数表示

• 以单个区间来说，把每个点可取大小定义成一个点，那么我们就是要求每个点的乘积。而现在每个点变成了一次函数，那么这就变成了一个 $n$ 次多项式

• 我们可以用拉格朗日差值 $O(n^3)$ 实现