[HNOI2010] 弹飞绵羊

发表于 | 分类于 >
字数统计 : 478   |   阅读时长 ≈ 2 mins.

题目

链接

[HNOI2010]弹飞绵羊

题意简述

地上沿着一条直线摆着 个装置，每个装置设定初始弹力系数 ，当绵羊达到第 个装置时，它会往后弹 步，达到第 个装置，若不存在第 个装置，则绵羊被弹飞。

要支持 次 种操作。

  • 查询从 出发后几次被弹飞。
  • 将 处的弹力系数改为 。

思路

优雅的暴力

可谓：

n方过十万，暴力碾标算。

要修改就不改，累计到了 $lim$ 再一起重新统计。
暴力查询。
就这样。（说到底还是暴力
时间复杂度： $(n?)$ 。
随机数据能保证复杂度。
但要是碰到毒瘤出题人就会被卡掉。

LCT

我太蒻了，学了再补全。

代码

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 2e5 + 10, kmax_int = 2147483647, kmod = 1e4;

int n, m, lim = 100, last;
int f[kmax_num], c[kmax_num], t[kmax_num];

inline void Flush() {
    for(REG int i = n - 1; i >= 0; --i) {
        if(c[i])    f[i] = c[i], c[i] = 0;
        if(i + f[i] >= n)       t[i] = 1;
        else                    t[i] = t[i + f[i]] + 1;
    }
    return ;
}

inline int Query(REG int pos)   {
    REG int ans = 0;
    while(pos <= last)  {
        pos += (c[pos] ? c[pos] : f[pos]);
        ++ans;
    } 
    return t[pos] + ans;
}

int main()  {
    std::cin >> n;
    FOR(i,0,n)  std::cin >> f[i];

    std::cin >> m;
    REG int cmd, x, y;
    FOR(i,0,m)  {
        if(lim == 100)  lim = 0, last = -1, Flush();

        std::cin >> cmd;
        if(cmd == 1)    {
            std::cin >> x;
            printf("%d\n", Query(x));
        }
        else    {
            std::cin >> x >> y;
            if((f[x] == y && c[x] == 0) || c[x] == y)  continue;
            if(f[x] == y && c[x] != 0)  c[x] = 0;

            if(f[x] != y)   {
                c[x] = y, ++lim;
                last = std::max(last, x);
            }
         }  
    }
    return 0;
}

杂项

  • 暴力中的 $lim$ 你们可以尝试改一下。