雅礼国庆集训 day1 T1 养花
题面
题目下载
算法
考虑当 \(k\) 确定的时候如何求答案,
显然对于所有形如 \([ak, (a+1)k)\) 的值域区间, 最大值一定是最优的
似乎怎么都是 \(O(n^2)\) 的算法
观察到 \(a_i\) 的值域比较小, 所以考虑桶
显然对于一段区间 \([L, R]\)
我们可以推出其 \(mod k\) 的最大值
- 方法
首先用一个数组 \(f_i (\forall i \leq 10^5)\) 表示比 \(i\) 小的最大的数
这里有一个 \(\rm{unbelievable}\) 的递推方法( \(O(N + n)\) )
for (int i = l; i <= r; i++)
f[a[i]] = a[i];
for (int i = 1; i <= N; i++) // N 为值域
f[i] = std::max(f[i], f[i - 1]);
接下来可以通过这一递推公式求出这段区间对 \(i\) 取余的最大值
\[g_i = \max (f_{i \times j - 1} \mod i), i \times j \leq N
\]
计算是调和级数的复杂度
但是此时计算单个区间的时间复杂度仍然是 \(10^5\) 级别的, 不可能在乘以一个 \(m\)
考虑分块, 这样能在 \(O(m \sqrt{n} + n \sqrt{n} \log n)\) 的复杂度下草过去
代码
后补
总结
抽象套路, 伟大的递推