P10132 Cannonball 题解

Su777 · 2024-02-06 11:28:27 · 题解

题意简述

你的初始位置为 S，初始能量为 v，初始方向为向右。每次操作，如果向右则位置加上 v，否则减去 v。
在 [1,n] 区间内，每一个数都代表一个有特定数值的跳板或目标。如果是数值为 v 的跳板，它会更改你的弹跳方向，并将能量增加 v。如果是数值为 v 的目标，它不会对你的弹跳产生任何影响，但如果你的能量大于等于 v，该目标会被击碎。已击碎的目标上也可以正常弹跳。
如果你在 [1,n] 区间内弹跳无限次或直到你离开这个区间，你会击碎多少个目标？

解题思路

暴力做法

直接暴力模拟弹跳过程。注意同一个目标的击碎条件可能会多次被满足，所以只能在过程中记录目标的击碎情况，最后再统计。

这种做法没有考虑在 [1,n] 区间内弹跳无限次的情况，在一些情况中会 TLE。

核心代码：

ll pos = s, ctar = 0, power = 1;
bool dir = true; // true 表示向右, false 表示向左
while (pos >= 1 && pos <= n) {
    if (type[pos] == 0) {
        power += val[pos];
        dir ^= 1;
    } else if (type[pos] == 1) {
        if (power >= val[pos]) {
            ctar ++;
            broken[pos] = 1;
        }
    }
    if (dir) pos += power;
    else pos -= power;
}

满分做法

加两行，75 \to 100！

说人话就是加入特判弹跳无限次的情况。在每次循环时统计总共的弹跳次数，最后在弹跳次数大于 3n 时就可以判断会武仙坛跳下去，退出循环即可。

如果弹跳无限次，那么一定存在一个弹跳循环，而这个循环的最大长度是 n，在弹跳总统计次数大于 n 时就说明存在循环。

那为什么要选择 3n 而不是 n 呢？因为在循环过程中，能量可能会增加，而这可能会在增加被击碎的目标个数，在超过 n 次后直接退出循环可能会造成答案偏小，需要多执行几次循环才可以。

那怎么确定 n 前面的系数呢？在不关注提交次数时，从 2n 开始往上尝试，直到通过为止。在提交次数影响分数时，把系数设得大一点，保证不超时即可。

核心代码：

ll pos = s, ctar = 0, power = 1, jumpcnt = 0;
bool dir = true; // true 表示向右; false 表示向左
while (pos >= 1 && pos <= n) {
    jumpcnt ++;
    if (type[pos] == 0) {
        power += val[pos];
        dir ^= 1;
    } else if (type[pos] == 1) {
        if (power >= val[pos]) {
            ctar ++;
            broken[pos] = 1;
        }
    }
    if (dir) pos += power;
    else pos -= power;
    if (jumpcnt > 3 * n) break;
}