[分块]bzoj-2002-Bounce 弹飞绵羊

https://vjudge.net/problem/HYSBZ-2002

7月31日 似乎是第一个 没有在家里过的生日。。。好像是真的 高中那么紧张。。。老天爷为了让我回家 都下雨把学校楼冲垮了。。。话说今天阴阳师抽卡虽然没有抽到大岳丸(正常拉)但是居然出了3黄 还是蛮开心的。。。

说说这个题吧 题目是中文题 题意很明确
解题思路 分为根号n块 统计每块内的每一个小块何时跳出这个块
我们搞两个数组 一个叫pos[]数组 一个叫times[]数组
Pos数组表明下标为这个号的这个块跳出当前块的落地点
times[]是跳出当前块(注意不是整块)要跳几次
如果Pos直接跳出整个数组(即达成目标)pos=-1;
跳出当前块 pos=i+arr[i]
否则 pos=pos[i+arr[i]]
就样例来说
4
1 2 1 1
pos 3 3 -1 -1
time 2 1 2 1

之后 根据询问 实时更新 注意是倒序更新 因为某一块的数值更新 其后面的数值不会受到影响 只会影响前面的

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
#include<sstream>
#include<queue>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int maxn = 2e5 + 5;

int pos[maxn], arr[maxn], times[maxn];

int main() {
	int n, m, blocks, k, x, y, ans=0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	blocks = (int)sqrt(n + 1e-7);//分为根号n块
	for (int i = n - 1; i >= 0; i--) {//从后往前
		if (i + arr[i] >= n) {//如果能直接跳出界外
			pos[i] = -1;
			times[i] = 1;//只需要一步
		}
		else if (i + arr[i] >= ((i / blocks) + 1) * blocks) {//如果能跳出当前块
			pos[i] = i + arr[i];//块外落地点
			times[i] = 1;
		}
		else {
			pos[i] = pos[i + arr[i]];//在块内 跳出点有一点递归的思想 就是直到跳到界外
			times[i] = times[i + arr[i]] + 1;
		}
	}
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d", &k);
		if (k == 1) {
			scanf("%d", &x);
			ans = 0;
			while (x != -1) {
				ans += times[x];//统计步数
				x = pos[x];//直接下一块
			}
			printf("%d\n", ans);
		}
		else {
			scanf("%d%d", &x, &y);
			arr[x] = y;
			for (int i = x; i >= x / blocks * blocks; i--) {//只更新当前块中这个点之前的那部分
				if (i + arr[i] >= n) {
					pos[i] = -1, times[i] = 1;
				}
				else if (i + arr[i] >= ((i / blocks) + 1) * blocks) {
					pos[i] = i + arr[i];
					times[i] = 1;
				}
				else {
					pos[i] = pos[i + arr[i]];
					times[i] = times[i + arr[i]] + 1;
				}
			}
		}
	}
	return 0;
}

发表评论