[杭电多校8 | HDUOJ]7224.Ironforge(思维 + 数论)

发布于 2022-08-17  589 次阅读


题目传送门: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-08-17