这套题比较简单 ?
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\) 是一段区间
这样我们使用差分完美解决
但存不下怎么办,都到这了,自然很容易想到可以存一部分
发现信息可差分,存根号个前缀和的点即可
然后这一步其实也可以用分块做
分块实现