这套题比较简单 ？
1.
P10528 [XJTUPC 2024] 崩坏：星穹铁道
这题就是矩乘板子
码
2.
P3667 [USACO17OPEN] Bovine Genomics G
原题应该是想让二分长度后 ，哈希判断的
但数据范围小了（我的 \(n^3\) 暴力过了 ）
哈希模数取小点，然后用数组存就是 \(o(1)\) 的，有点冲突的危险
码
3.
P3084 [USACO13OPEN] Photo G
这题有显然的差分约束做法
就是把每个前缀看成点，然后列关系
然后朴素 \(spfa\) 被卡了
然后线性做法给了 \(dp\) 设 \(dp[i]\) 表示考虑 \(i\) 个，选了第 \(i\) 个，最多选几个
然后设 \(L[i]\) 为 \(i\) 左边的区间，左端点最大值，上一个位置必须在其右才能保证每个区间至少选一个
设 \(R[i]\) 为包含 \(i\) 的区间的最端点最小值，上一个位置必须在其左才能保证每个区间至多选一个
那么 \(j\) 取值范围即为 \(L[i]\) ~ \(R[i] - 1\)
然后预处理这两个数组就是先扫所有区间给初始化，然后再整体扫一遍，去 \(max / min\)
预处理出来后根据定义我们知道转移区间单调，上单调队列即可
然后这题有归纳证明 \(f[i]\) 有值即单调，可以不写单调队列
单调队列实现
4.
P11660 我终将成为你的倒影
烤柿的时候傻了，考后感觉正解所有的思路都想到了，为何没写 ？ 666
考虑 \(a , b\) 是根号级别
主要是 \(n \times b\) 复杂度刚刚好
暴力考虑枚举 \(i , a , b\) 然后处理出，然后 \(O(1)\) 查询即可
发现了什么 ？
预处理复杂度超标并且存不下，询问却游刃有余
那我们可以可以根号平衡一下 ？
继续观察柿子
我们可以发现 \(x_i / b\) 和 \(x_{i - 1} / b\) 只有差 \(1\) 的时候才可能有贡献
那具体一点呢
我们发现知道 \(x,b\) 后，合法的 \(a\) 是一段区间
这样我们使用差分完美解决
但存不下怎么办，都到这了，自然很容易想到可以存一部分
发现信息可差分，存根号个前缀和的点即可
然后这一步其实也可以用分块做
分块实现