题目传送门:Problem - 7224 (hdu.edu.cn)
题目 / Problem
在一条横轴上有n个点,每两个相邻的点有一条边,一共n-1条边,每个点上有一个权值a,走到一个点时就可以将某个点上的a所有质因子放入背包中,每条边有一个质数权值pri,只有当pri存在于当前背包中时才能通过这条边。
有M次询问,问能否从x走到y。
思路 / Thought
这道题容易想到用两个数组 array l 和 array r 来表示某个点向左和向右可以到达的最远位置,但是不知道怎么去处理这个最大位置。因为从某个点出发,可以左右横跳到达更远的点。
先处理出暂时不考虑向左走的情况下向右可以到达的最远位置,记作r[i],再通过这个r[i]来更新l[i]。
如何知道当拥有[s, e]区间的所有数字的权值后能否通过边b[i]呢?因为b[i]是一个1 ~ 2e5的质数,不难想到用一个数组来保存下质数b[i]出现的所有位置,如果有一个出现在[s, e]中,说明可以通过b[i]这条边,这个可以通过二分O(logN)查询,我们把这个操作同一个函数check来表示。
最后就是如何更新l[i]和r[i]了,从左往右更新,如果i-1能到i,并且i能到i - 1(这个通过check来检查,因为此时i的左右最远距离l, r并非正确的),那么i的左右最远位置就是i-1的左右最远距位置。
如果不能到达,就进行多次左右横跳直到不能跳为止。
复杂度均摊下来是O(NlogN)。
代码 / Code
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 9; int a[maxn], b[maxn]; bool check(int l, int r, vector<int>& v) { int pos = lower_bound(v.begin(), v.end(), l) - v.begin(); return pos < v.size() && v[pos] <= r; } void solve() { int N, M;cin >> N >> M; for(int i = 1;i <= N; ++ i)cin >> a[i]; for(int i = 1;i < N; ++ i)cin >> b[i]; vector<int> l(maxn, 0), r(maxn, 0), v[maxn]; for(int i = 1;i <= N; ++ i) { int t = a[i]; for(int j = 2;j <= t; ++ j) { if(t % j == 0)v[j].push_back(i); while(t % j == 0)t /= j; } if(t != 1)v[t].push_back(i); } for(int i = N;i >= 1; -- i)//仅考虑向右走 { r[i] = i; for(int j = r[i] + 1;j <= N; ++ j) { //如果i能够向右走到j,就将r[i]拓展到r[j] if(check(i, r[i], v[b[j - 1]]))j = r[j], r[i] = j; else break; } } l[1] = 1; for(int i = 2;i <= N; ++ i) { l[i] = i; if(r[i - 1] >= i)//i-1能到i { if(check(l[i], r[i], v[b[i - 1]]))l[i] = l[i - 1], r[i] = r[i - 1]; } else { bool tag = true; while(tag) { tag = false; //向左 for(int j = l[i] - 1;j >= 1; -- j) { if(check(l[i], r[i], v[b[j]]))j = l[j], l[i] = j, tag = true; else break; } //向右 for(int j = r[i] + 1;j <= N; ++ j) { if(check(l[i], r[i], v[b[j - 1]]))j = r[j], r[i] = j, tag = true; else break; } } } } while(M --) { int x, y;cin >> x >> y; cout << ((l[x] <= y && y <= r[x]) ? "Yes" : "No") << '\n'; } } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _;cin >> _; while(_ --)solve(); return 0; }
Comments NOTHING