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

发布于 2019-07-31  363 次阅读


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;
}

愿风指引你的道路,愿你的刀刃永远锋利。