CF-1075-B. The Curse of the Frog（遇到一个值，可以直接减掉的话最好，避免后续处理） · znzryb
## 题目大意：B. The Curse of the Frog
一只青蛙位于数轴的 $0$ 点，目标是到达坐标 $x$。青蛙掌握 $n$ 种跳跃技能，每种技能 $i$ 包含三个参数：
- $a_i$：最大跳跃距离。单次跳跃可从 $k$ 移动到 $[k, k + a_i]$ 范围内的任意整数点。
- $b_i$：回滚周期。每当**第** $b_i, 2b_i, 3b_i \dots$ 次使用该技能时，会触发诅咒。
- $c_i$：回滚距离。触发诅咒时，青蛙会先从当前位置 $k$ 后退到 $k - c_i$，然后再进行跳跃，最终落点范围为 $[k - c_i, k - c_i + a_i]$。
**目标：** 计算到达 $x$ 点所需经历的**最小回滚总次数**。如果无法到达，则输出 $-1$。
---
### 样例解释
### 样例 1
- **输入：** $x=1$, 技能：$a=3, b=3, c=3$。
- **过程：** 第一次使用技能，不触发回滚（因为 $1 < b=3$）。直接从 $0$ 跳到 $1$。
- **结果：** $0$ 次回滚。
### 样例 4
- **输入：** $x=8$, 拥有 $5$ 种技能。其中包含 $(12, 1, 11)$ 和 $(10, 1, 4)$ 等。
- **过程：**
1. 使用第 $1$ 种技能（$b=1$）：触发回滚，从 $0$ 退到 $-11$，跳到 $1$。
1. 使用第 $4$ 种技能（$b=2$）：这是该技能第 $1$ 次使用，不回滚，从 $1$ 跳到 $2$。
1. 使用第 $2$ 种技能（$b=1$）：触发回滚，从 $2$ 退到 $-2$，跳到 $8$。
- **结果：** 总计 $2$ 次回滚。
### 样例 6
- **输入：** $x=10$, 技能：$a=2, b=2, c=1$。
- **过程：**
- 第 $1$ 次跳：不回滚，$0 \to 2$。
- 第 $2$ 次跳：**回滚**（第 $b=2$ 次），$2 \to 1 \to 3$。
- 第 $3$ 次跳：不回滚，$3 \to 5$。
- 第 $4$ 次跳：**回滚**（第 $2b=4$ 次），$5 \to 4 \to 6$。
- 以此类推，通过交替回滚逐步前进。
- **结果：** 总计 $3$ 次回滚。
## 思路讲解
starsilk 的代码。不需要的值，我们其实可以减掉。会清爽一些。
然后最后的这个向上取整除法，可以这样子想，没消耗一个回滚，可以前行多少距离？$w\gets a\times b-c$。这个可以这么看，你先回滚 $-c$（因为前面的免费步已经用完了），然后可以走 $b$ 步，每步 $a$ 的长度。
```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int T;
long long n,x,i,a,b,c,w;
for(cin>>T;T>0;T--)
{
cin>>n>>x;
w=0;
for(i=0;i<n;i++)
{
cin>>a>>b>>c;
x-=(b-1)*a;
w=max(w,a*b-c);
}
if(x<=0)cout<<"0\n";
else if(w==0)cout<<"-1\n";
else cout<<(x+w-1)/w<<'\n';
}
return 0;
}
```
## AC代码
AC
[https://codeforces.com/contest/2189/submission/359582687](https://codeforces.com/contest/2189/submission/359582687)
::: 源代码
```cpp
/**
* Problem: B. The Curse of the Frog
* Contest: Codeforces Round 1075 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2189/problem/B
* Created: 2026-01-23 22:41:09
* Author: Gospel_rock
*/
#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
struct Abc {
ll a,b,c;
};
void Solve() {
ll N,X;
cin >> N >> X;
vector<Abc> abc_vec(N);
ll mx_w=0;
for (int i=0;i<N;++i) {
ll a,b,c;
cin>>a>>b>>c;
abc_vec[i]={a,b,c};
X-=a*(b-1);
ll w=a*b-c;
mx_w=max(mx_w,w);
}
if (X<=0) {
cout<<0<<"\n";
return;
}
if (mx_w==0) {
cout << -1 << "\n";
return;
}
cout<<(X+mx_w-1)/mx_w<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2189/submission/359582687
*/
```
:::
## 心路历程（WA，TLE，MLE……）