https://codeforces.com/contest/797/problem/E
题目大意
给出 $n \ (\le 10^5)$ 长的数组 $a \ (1 \le a_i \le n)$。
给出 $q$ 个询问。每个询问给出 $p \ (1 \le p \le n)$ 和 $k \ (1 \le k \le n)$。问要对 $p$ 执行多少次 $p = p + a[p] + k$ 才能使 $p > n$。
简要题解
对于固定的 $k$ 这是一道动态规划题目
$$ \begin{align} dp[i] = \begin{cases} dp[i + a[i] + k] + 1, \quad & i + a[i] + k \le n \\ 1, \quad & otherwise. \end{cases} \end{align} $$但是我们无法对所有的 $k$ 都跑一遍算法。
方法一：
注意到因为 $a_i \ge 1$，所以朴素算法暴力枚举在 $k$ 较大时跑的很快，因为对于 $k \ge \sqrt{n}$ 的情况 最多会有不超过 $\frac{n}{k} \le \sqrt{n}$ 跳，于是我们将两种方法结合起来，即可得到一个 $(n + q) \sqrt{n}$ 的算法。
复杂度
$T$：$O((n + q) \sqrt{n})$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const int THRE = 300;
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
vector<vector<PII>> qs(n + 1);
int q; cin >> q;
int u, k;
for (int i = 0; i < q; i++) {
cin >> u >> k; u--;
qs[k].push_back({u, i});
}
vector<int> ans(q);
vector<int> dp(n);
for (int i = 1; i <= THRE && i <= n; i++) {
for (int j = n - 1; j >= 0; j--) {
int nxt = j + a[j] + i;
if (nxt < n) dp[j] = dp[nxt] + 1;
else dp[j] = 1;
}
for (auto [u, qid] : qs[i]) {
ans[qid] = dp[u];
}
}
for (int i = THRE + 1; i <= n; i++) {
for (auto [u, qid] : qs[i]) {
int cur = 0;
while (u < n) {
u += a[u] + i;
cur++;
}
ans[qid] = cur;
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
方法二：
这里注意到其实直接按照 $k$ 枚举，然后每次做记忆化搜索，则结果不会比上述按 $\sqrt{n}$ 的做法更慢（$k$ 较大的情况一致，$k$ 较小的情况不需要每次全部计算）。重点是需要比较聪明的判断每个位置的 $dp$ 值对于当前的 $k$ 有没有算过，$mk$ （mark）数组只需要按照当前 $k$ 标记而不是 $1, 0$ 标记即可。这里最差复杂度是一致的。（可能会好写一点？且不用调 $\sqrt{n}$ 的值。实测 $300$ 的阈值跑了 $203ms$ 而 dp 可能常数比较大跑了 $437ms$ 反而更慢……）
复杂度
$T$：$O((n + q) \sqrt{n})$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
template<typename Func> struct YCombinatorResult {
Func func;
template<typename T>
explicit YCombinatorResult(T &&func) : func(std::forward<T>(func)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) {
return func(std::ref(*this), std::forward<Args>(args)...);
}
};
template<typename Func> decltype(auto) y_comb(Func &&fun) {
return YCombinatorResult<std::decay_t<Func>>(std::forward<Func>(fun));
}
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
vector<vector<PII>> qs(n + 1);
int q; cin >> q;
int u, k;
for (int i = 0; i < q; i++) {
cin >> u >> k; u--;
qs[k].push_back({u, i});
}
vector<int> ans(q);
vector<int> dp(n);
vector<int> mk(n);
auto dfs = y_comb([&](auto dfs, int u, int i) -> int {
if (u >= n) return 0;
if (mk[u] == i) return dp[u];
mk[u] = i;
dp[u] = dfs(u + a[u] + i, i) + 1;
return dp[u];
});
for (int i = 1; i <= n; i++) {
for (auto [u, qid] : qs[i]) {
ans[qid] = dfs(u, i);
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] D. Broken BST - Educational Codeforces Round 19