题目描述

题目传送门1

题目传送门2

给定长度为 nn 的序列 aamm 次询问。

每次询问给出 p,kp,k。您要不断地执行操作 pp+ap+kp\gets p+a_p+k,直到 p>np>n 为止。询问的答案为操作次数。
1n,q1051\le n,q\le 10^51ain1\le a_i\le n

思路

Algorithm1

考虑动态规划。

假设 dp[i][j]dp[i][j] 表示当 p=i,k=jp=i,k=j 时的答案。

方程显然可以写出来:

dpi,j={1                            i+ai+n>ndpi+ai+n,j+1       otherwisedp_{i,j} = \left\{ \begin{array}{lc} 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i+a_i+n>n\\ dp_{i+a_i+n,j}+1 \ \ \ \ \ \ \ otherwise \end{array} \right.

预处理时间复杂度 O(nk)O(nk),空间复杂度 O(nk)O(nk)

显然做不了。

Algorithm2

考虑暴力,每次询问时间复杂度 O(nk)O(\frac{n}{k})

显然也做不了。


我们发现,Algorithm1 在 kk 比较小的时候可以 AC, Algorithm2 在
kk 比较大的时候可以 AC。

所以我们可以大胆结合,当 knk \le \sqrt n 时使用 Algorithm1,当 knk \ge \sqrt n 的时候使用 Algorithm2。

这样我们的时间和空间复杂度均变成了 O(nn)O(n \sqrt n), 可以 AC。

这种思想被称作 根号分治

代码

#include <bits/stdc++.h>
using namespace std;

int N , Q , Num[100010] , NN;
int P , K;

int Dp[100010][350];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N;
	NN = sqrt(N);
	for(int i = 1; i <= N; i++) {
		cin >> Num[i];
	}

	for(int i = N; i >= 1; i--) {
		for(int j = 1; j <= NN; j++) {
			if(i + Num[i] + j > N) Dp[i][j] = 1;
			else Dp[i][j] = Dp[i + Num[i] + j][j] + 1;
		}
	}

	cin >> Q;
	while(Q--) {
		cin >> P >> K;
		if(K <= NN) {
			cout << Dp[P][K] << endl;
		}
		else {
			int res = 0;
			while(P <= N) {
				P = P + Num[P] + K;
				res++;
			}
			cout << res << endl;
		}
	}
	return 0;
}