P10132 解题报告

Sternenlicht · 2024-02-06 20:34:45 · 题解

思路：

按题意模拟跳的过程。设当前跳到的点为 now，能量值为 pnt，跳跃方向为 dire，可击破的炮击目标个数为 ans。其中，dire = 1 则是向右跳，dire = -1 则是向左跳。

• 若 q_{now} = 1，即当前点是炮击目标。判断此时的能量值 pnt 是否不小于击破目标的能量值 v_{now}，如果是，说明可以击破，ans 加 1，并将 q_{now} 标记为 2。（由于题目中 q_{now} 的取值只可能是 0 或 1，将它记为 2 即可说明这个点是被击破的炮击目标。）

• 若 q_{now} = 0，即当前点是跳板。此时，让 dire 变为 -dire，即可改变方向。并让 pnt 加上 v_{now}，即增加能量值。

每次判断结束，要更新当前点的位置，让 now 加上 pnt \times dire 就行了。

这样还没做完，题目中说 Bessie 可能会一直跳下去，那我们开一个变量 cnt 记录跳的次数，若 cnt 远大于 N，说明会有死循环，这时我们退出循环并输出答案即可。

完整代码如下：

#include <bits/stdc++.h>
#define il inline
namespace Fast_IO {
    template <typename T> il void read(T &x) {
        x = 0; int f = 0; char ch = getchar();
        while (!isdigit(ch))f |= (ch == '-'), ch = getchar();
        while (isdigit(ch))x = x * 10 + (ch - 48), ch = getchar();
        x = f ? -x : x;
    }
    template <typename T, typename ...Args>
    il void read(T &x, Args& ...args) {read(x), read(args...);}
    template <typename T> il void write(T x, char c = '\n') {
        if (x) {
            if (x < 0)x = -x, putchar('-');
            char a[30]; short l;
            for (l = 0; x; x /= 10)a[l ++] = x % 10 ^ 48;
            for (l --; l >= 0; l --)putchar(a[l]);
        } else putchar('0');
        putchar(c);
    }
} using namespace Fast_IO;
using namespace std;

const int Maxn = 100005;
int n, st, ans, cnt, q[Maxn], v[Maxn];
signed main() {
    read(n, st);
    for (int i = 1; i <= n; i ++) read(q[i], v[i]);
    int now = st, pnt = 1, dire = 1; //1为向右跳，-1为向左跳 
    while (1 <= now && now <= n && cnt <= 1000000) {
        if (q[now] == 1) { //是炮击目标 
            if (pnt >= v[now]) ans ++, q[now] = 2;
        } else if (q[now] == 0) { //是跳板 
            dire = -dire, pnt += v[now];
        }
        now += pnt * dire, cnt ++;
    }
    write(ans);
    return 0;
}