河北邯郸网络科技有限公司_建设工程信息管理网_澳门seo推广_我们公司想做网络推广

5525. 炮弹

题意

存在一个区间为 ([L, R]) 的整数数轴，每个点是一个跳板或者目标，遇到跳板会让跳跃距离 $(k\leftarrow -(k+v_i))$，遇到目标，若 $(k\ge v_i)$ 则可以击破该目标，最开始跳跃距离 (k = 1)，现在从 (S) 开始，每次可以跳跃到 (S + k)，问最终能击破多少个不同的目标。

解题思路

直接暴力模拟跳跃过程即可，需要注意的是，可能会出现形如这样的数据：

0 0
1 1
0 0

也就是形成一个反复横跳的环形，可以考虑引入一个 set 容器记录每个点起跳的 (k)，如果这个 (k) 之前从这个点起跳过，则说明进入了一个环，直接退出即可。

时间复杂度分析：这个题的时间复杂度分析比较特殊，由于 (k) 是递增的（要么不变要么增加），考虑最坏的情况，每个点都以不同的 (k) 起跳，那么每轮都会经过 $\frac{N}{k}$ 个点，我们将点数累和，形如调和级数：

$$\sum _{k=1}^N\frac{N}{k}=N\ln N$$

因此最多起跳 (N \ln N) 次，每次加上 set 的判重复杂度为 (\log k)，因此最终的时间复杂度为 (O(N \ln N \log N))。

AC Code

// Problem: 炮弹
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/5528/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
typedef long long ll; // 确保 ll 在使用前被定义
using namespace std;
using i64 = long long;
#define f for(int i = 0; i < n;++i)
#define ff for(int i = 1; i <= n;++i)
#define int long long 
#define pii pair<int,int>
#define In \ll n; \std::cin >> n;\

const int mod = 1e9 + 7, N = 1e7;struct node{int q, v;bool y = true;
};void solve(){int n, s; std::cin >> n >> s;std::vector<node> mm(n);f {std::cin >> mm[i].q >> mm[i].v;}f mm[i].y = true;std::vector<std::set<int>> vis(n + 1); // 记录点 i 是否以 set 中的值起跳过int ans = 0,v = 1;int flag = 1;while((s - 1) >= 0 && (s - 1) < n) {if(mm[s - 1].q == 1 && mm[s - 1].y && mm[s - 1].v <= std::abs(v) ) {ans++;mm[s - 1].y = false ;}if(mm[s - 1].q == 0) {v = (v + mm[s - 1].v);flag = - flag;}if(vis[s - 1].count(flag * v)) break;else vis[s - 1].insert(flag * v);s = s + (flag * v);}std::cout << ans << "\n";
}signed main(){std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);ll T = 1;//std::cin >> T;for(int i = 1; i <= T; ++i) solve();
}