ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年8月17日 261点热度 0人点赞 0条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ hduoj 二分 思维 算法竞赛
最后更新:2022年8月17日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号