首页 > 其他分享 >P10231 [COCI 2023/2024 #4] Putovanje 题解

P10231 [COCI 2023/2024 #4] Putovanje 题解

时间：2024-05-12 20:41:40浏览次数：12  
标签：P10231 return cur int 题解 vis vec 2023 dis

P10231 [COCI 2023/2024 #4] Putovanje 题解

知识点

多源 BFS，bitset。

题意分析

在一个图上，每个点有一个权值，求满足到每个点的距离都为其权值的点（权值为 \(-1\) 的点除外）。

思路分析

Subtask 1

我们可以发现，这个子任务的图一定是一个有序的链，那么转换成序列问题，直接根据坐标进行标记即可，不再赘述。

代吗时间复杂度 \(O(n)\)，空间复杂度 \(O(n+m)\)。

namespace Subtask1{
	int sum,ans;
	int cnt[N];
	bool Check(){
		if(m!=n-1)return 0;
		FOR(i,1,m)if(g.v[(i<<1)-1]!=g.v[i<<1]+1)return 0;
		return 1;
	}
	signed Cmain(){
		FOR(i,1,n)if(~a[i]){
			++sum;
			if(i-a[i]>0)++cnt[i-a[i]];
			if(i+a[i]<=n&&a[i])++cnt[i+a[i]];
		}
		FOR(i,1,n)if(cnt[i]==sum)++ans;
		wr(ans);
		FOR(i,1,n)if(cnt[i]==sum)wr(i,' ');
		return puts(""),0;
	}
}

Subtask 2

在这个子任务中，只有第一个点有可能有非负权值，那么就变成了单源 BFS，或者当第一个点也是负权值时，那么全部直接输出即可。

时间复杂度 \(O(n+m)\)，空间复杂度 \(O(n+m)\)。

namespace Subtask2{
	bool vis[N];
	int ans;
	int dis[N];
	queue<int> q;
	bool Check(){
		FOR(i,2,n)if(~a[i])return 0;
		return 1;
	}
	signed Cmain(){
		if(!~a[1]){
			wr(n);
			FOR(i,1,n)wr(i,' ');
			return puts(""),0;
		}
		vis[1]=1,dis[1]=0,q.push(1);
		while(!q.empty()){
			int u=q.front();q.pop();
			EDGE(g,i,u,v)if(!vis[v])dis[v]=dis[u]+1,vis[v]=1,q.push(v);
		}
		FOR(i,1,n)if(dis[i]==a[1])++ans;
		wr(ans);
		FOR(i,1,n)if(dis[i]==a[1])wr(i,' ');
		return puts(""),0;
	}
}

Subtask 3

注意到 \(n,m \leq 5 \times 10^3\)，那么能够支持 \(O(nm)\) 这类的时间复杂度，我们对每个权值非负的点都做一次 BFS，再做上标记，最后一起验证即可。

时间复杂度 \(O(nm)\)，空间复杂度 \(O(n+m)\)。

namespace Subtask3{
	bool mark[N],vis[N];
	int ans;
	int dis[N];
	queue<int> q;
	bool Check(){
		return n<=5000&&m<=5000;
	}
	void Bfs(int s){
		RCL(vis,0,bool,n+5),vis[s]=1,dis[s]=0,q.push(s);
		while(!q.empty()){
			int u=q.front();q.pop();
			EDGE(g,i,u,v)if(!vis[v])vis[v]=1,dis[v]=dis[u]+1,q.push(v);
		}
		FOR(i,1,n)if(dis[i]!=a[s])mark[i]=1;
	}
	signed Cmain(){
		FOR(i,1,n)if(~a[i])Bfs(i);
		FOR(i,1,n)if(!mark[i])++ans;
		wr(ans);
		FOR(i,1,n)if(!mark[i])wr(i,' ');
		return puts(""),0;
	}
}

Subtask 4

观察范围 \(n \leq 5\times 10^4\)，通过它来推测方案，我们可以想到优化上面的方法，把所有 BFS 放到一起做，变成多源 BFS，然后用一个很好用的 STL：bitset，它的原理是把 bool 的 1 字节缩到 1 bit，因此速度、空间都是一般 int 的 32 倍。

为保证每一个 BFS 的正确性，我们不能直接每个一起做，那怎么办呢？

观察题目，我们可以把原本的 \(dis\) 数组的定义改掉，原本是到源点的最短距离，现在改为到目标点（酒店）的距离，这样就对每一个点都适用，然后我们走一步的距离是 \(-1\)，所以只要我们按点权从大到小一个个加入源点，就能保证每个点在 BFS 时的阶段相同。在 BFS 时，还要注意判断不合法情况。

所以其实方法并没有很大的提升，只是对暴力的优化。

时间复杂度 \(O(\frac{nm}{w})\)，空间复杂度 \(O(\frac{nm}{w})\)，其中 \(w\) 约为 \(32\)。

namespace Subtask4{
	int tot,ans;
	int dis[N];
	bool flag=1;
	bool mark[N];
	queue<int> q;
	bitset<N> vis[N];
	vector<int> vec[N];
	void Bfs(){
		int cur=n;
		while(cur>=0&&vec[cur].empty())--cur;
		for(int i:vec[cur])dis[i]=cur,mark[i]=1,vis[i][i]=1,q.push(i);
		for(int u=q.front();!q.empty();q.pop(),u=q.empty()?u:q.front())if(dis[u]){
			while(!vec[dis[u]-1].empty()){
				int v=vec[dis[u]-1].back();vec[dis[u]-1].pop_back();
				if(mark[v]){
					if(dis[v]!=a[v])flag=0;
					continue;
				}
				mark[v]=1,dis[v]=a[v],q.push(v),vis[v][v]=1;
			}
			EDGE(g,i,u,v)if(dis[v]<dis[u]){
				dis[v]=dis[u]-1,vis[v]|=vis[u];
				if(!mark[v])q.push(v);
				mark[v]=1;
			}
		}
	}
	signed Cmain(){
		FOR(i,1,n)if(~a[i])vec[a[i]].push_back(i),++tot;
		if(!tot){
			wr(n);
			FOR(i,1,n)wr(i,' ');
			return puts(""),0;
		}
		Bfs();
		if(!flag)return (cout<<0<<endl),0;
		FOR(i,1,n)if(!dis[i]&&vis[i].count()==tot)++ans;
		wr(ans);
		FOR(i,1,n)if(!dis[i]&&vis[i].count()==tot)wr(i,' ');
		return puts(""),0;
	}
}

完整CODE

#include<bits/stdc++.h>
#define max(a,b) ((a)<(b)?(b):(a))
#define min(a,b) ((a)>(b)?(b):(a))
#define tomax(a,b) ((a)=max((a),(b)))
#define tomin(a,b) ((a)=min((a),(b)))
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define DOR(i,a,b) for(register int i=(a);i>=(b);--i)
#define EDGE(g,i,u,x) for(register int (i)=(g).h[(u)],(x)=(g).v[(i)];(i);(i)=(g).nxt[(i)],(x)=(g).v[(i)])
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=5e4+10,M=1e5+10;
int n,m;
int a[N];
struct CFS{
	int tot,v[M<<1],nxt[M<<1],h[N];
	void att(int U,int V){
		v[++tot]=V,nxt[tot]=h[U],h[U]=tot;
	}
	void con(int U,int V){
		att(U,V),att(V,U);
	}
}g;
namespace Subtask1{
	int sum,ans;
	int cnt[N];
	bool Check(){
		if(m!=n-1)return 0;
		FOR(i,1,m)if(g.v[(i<<1)-1]!=g.v[i<<1]+1)return 0;
		return 1;
	}
	signed Cmain(){
		FOR(i,1,n)if(~a[i]){
			++sum;
			if(i-a[i]>0)++cnt[i-a[i]];
			if(i+a[i]<=n&&a[i])++cnt[i+a[i]];
		}
		FOR(i,1,n)if(cnt[i]==sum)++ans;
		wr(ans);
		FOR(i,1,n)if(cnt[i]==sum)wr(i,' ');
		return puts(""),0;
	}
}
namespace Subtask2{
	bool vis[N];
	int ans;
	int dis[N];
	queue<int> q;
	bool Check(){
		FOR(i,2,n)if(~a[i])return 0;
		return 1;
	}
	signed Cmain(){
		if(!~a[1]){
			wr(n);
			FOR(i,1,n)wr(i,' ');
			return puts(""),0;
		}
		vis[1]=1,dis[1]=0,q.push(1);
		while(!q.empty()){
			int u=q.front();q.pop();
			EDGE(g,i,u,v)if(!vis[v])dis[v]=dis[u]+1,vis[v]=1,q.push(v);
		}
		FOR(i,1,n)if(dis[i]==a[1])++ans;
		wr(ans);
		FOR(i,1,n)if(dis[i]==a[1])wr(i,' ');
		return puts(""),0;
	}
}
namespace Subtask3{
	bool mark[N],vis[N];
	int ans;
	int dis[N];
	queue<int> q;
	bool Check(){
		return n<=5000&&m<=5000;
	}
	void Bfs(int s){
		RCL(vis,0,bool,n+5),vis[s]=1,dis[s]=0,q.push(s);
		while(!q.empty()){
			int u=q.front();q.pop();
			EDGE(g,i,u,v)if(!vis[v])vis[v]=1,dis[v]=dis[u]+1,q.push(v);
		}
		FOR(i,1,n)if(dis[i]!=a[s])mark[i]=1;
	}
	signed Cmain(){
		FOR(i,1,n)if(~a[i])Bfs(i);
		FOR(i,1,n)if(!mark[i])++ans;
		wr(ans);
		FOR(i,1,n)if(!mark[i])wr(i,' ');
		return puts(""),0;
	}
}
namespace Subtask4{
	int tot,ans;
	int dis[N];
	bool flag=1;
	bool mark[N];
	queue<int> q;
	bitset<N> vis[N];
	vector<int> vec[N];
	void Bfs(){
		int cur=n;
		while(cur>=0&&vec[cur].empty())--cur;
		for(int i:vec[cur])dis[i]=cur,mark[i]=1,vis[i][i]=1,q.push(i);
		for(int u=q.front();!q.empty();q.pop(),u=q.empty()?u:q.front())if(dis[u]){
			while(!vec[dis[u]-1].empty()){
				int v=vec[dis[u]-1].back();vec[dis[u]-1].pop_back();
				if(mark[v]){
					if(dis[v]!=a[v])flag=0;
					continue;
				}
				mark[v]=1,dis[v]=a[v],q.push(v),vis[v][v]=1;
			}
			EDGE(g,i,u,v)if(dis[v]<dis[u]){
				dis[v]=dis[u]-1,vis[v]|=vis[u];
				if(!mark[v])q.push(v);
				mark[v]=1;
			}
		}
	}
	signed Cmain(){
		FOR(i,1,n)if(~a[i])vec[a[i]].push_back(i),++tot;
		if(!tot){
			wr(n);
			FOR(i,1,n)wr(i,' ');
			return puts(""),0;
		}
		Bfs();
		if(!flag)return (cout<<0<<endl),0;
		FOR(i,1,n)if(!dis[i]&&vis[i].count()==tot)++ans;
		wr(ans);
		FOR(i,1,n)if(!dis[i]&&vis[i].count()==tot)wr(i,' ');
		return puts(""),0;
	}
}
signed main(){
	rd(n),rd(m);
	FOR(i,1,m){
		int u,v;
		rd(u),rd(v),g.con(u,v);
	}
	FOR(i,1,n)rd(a[i]);
	return Subtask4::Cmain();
}
/*
我们为每个点设一个 dis[] 表示它到酒店的距离,
然后根据 d[] 从大到小做多源 BFS,
并记录能够到达该点的合法点集.
在 BFS 的过程中,要注意判断不合法的情况:当判断出酒店到达某个点 x 的最短距离小于 d[x] 那么它就不合法.
最后判断酒店的条件就是 dis[x]==0&&vis[x].count()==tot,其中 tot 表示 d[] 不为 -1 的点数.
*/

（此处省略快读快写。）

标签：P10231,return,cur,int,题解,vis,vec,2023,dis
From： https://www.cnblogs.com/Cat-litter/p/18188149

相关文章

  • CF1967D Long Way to be Non-decreasing 题解
    CF1967DLongWaytobeNon-decreasing题解知识点二分答案，基环树。题意分析给定一个包含\(n\)个元素的数组\(\{a_i\}\)和一个\(m\)个元素的数组\(\{b_i\}\)。定义每次操作为：在\(\{a_i\}\)中选择任意个数，假设某个选的数为\(a_i\)，那么将其变为\(b_{a_i}\)......
  • P10227 [COCI 2023/2024 #3] Slučajna Cesta 题解
    P10227[COCI2023/2024#3]SlučajnaCesta题解知识点期望DP，树形（换根）DP，组合数学。题意分析一棵树，每个点都有点权，每一条边的方向分布都是等概率的，问从每个点出发，有路走就一直走的情况下，所途径的点的权值总和的期望值。思路分析这明显是一个树形DP，且需要变成换根DP......
  • P9425 [蓝桥杯 2023 国 B] AB 路线
    P9425[蓝桥杯2023国B]AB路线一、问题简析本题是一道\(BFS\)题。与普通的广搜题不同的是，本题中，格子可以多次访问。因此，vis数组不能只用二维，要进行升维。本题中，每个节点包含以下信息：structnode{pair<int,int>loc;//坐标charch;//......
  • [ABC261E] Many Operations 题解
    [ABC261E]ManyOperations题解思路解析首先可以发现，如果直接跑肯定会炸，于是考虑优化。首先发现操作有很多重复的，所以可以考虑把每一个数经过所有操作后的值都预处理下来，但这样显然空间也会炸。然后我们又想到可以不需要求下每个数经过操作后的值，可以把每一位二进制上在开始前......
  • ABC353C Sigma Problem 题解
    ABC353CSigmaProblem题解题目链接：AT题目中的两个求和符号\(\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\)实际上是在枚举所有的有序数对\((i,j)\)。而有序数对的个数\(N(N-1)/2=O(N^{2})\)，真的去枚举所有数对肯定会T。这时应该考虑去拆贡献，求出每个\(A_i\)对答案的贡献。......
  • 2024江苏省大学生程序设计大赛（JSCPC）热身赛题解（B）
    题目大意：求区间\([l,r]\)中有多少正整数满足\(\phi(\phi(n))=\phi(n)-1\)，其中\(\phi\)为欧拉函数。解：设\(y=\phi(n)\)，则上式变为\(\phi(y)=y-1\)，易证\(y\)为质数（注意\(\phi(1)=1\)，\(1\)与任何正整数都互质）。故原问题转化为求\([l,r]\)中有多少个正整数v满足\(\phi......
  • set 容器详解 附大根堆题解
    声明本文中题解部分内容大部分转载自@sonnety的这篇博客中，本文为为方便复习而写的结论类文章，读者可自行跳转至原文处阅读。PART1set什么是set——来源cppreference简言之，它就是一种存进去就可以自动按升序排列的特殊容器，通常的set还具有自动去重的功能。定义方......
  • 工作疑难问题解决4例
      记录一下工作上疑难问题解决：  一，方便的页面监控     前几天早上，负责的kettle抽取数据表的任务又报错了，早上看手机有4个未接报警电话，一看是人员表，原来昨天报表系统有个大的查询一直未查询完成，导致truncate这个人员表，无法活动meta的锁，后续执行抽取和计算的都报错......
  • U423621 [HDK - NRC] Sqen Paradox 题解
    题目描述及\(O(n^2)\)做法见这个设\(a_i\)表示以\(i\)为左端点，无重复元素的最长区间的左端点，这个直接拿双指针做就行。处理出来后，分类讨论，找\(\max(i-l+1,i-a_i+1)\)，找\(i-l+1\)拿个桶维护一下左端点为\(i\)的右端点有那些就行，剩下的位置找最值即可，这个是RMQ。时间......
  • 工作疑难问题解决4例
      记录一下工作上疑难问题解决：  一，方便的页面监控     前几天早上，负责的kettle抽取数据表的任务又报错了，早上看手机有4个未接报警电话，一看是人员表，原来昨天报表系统有个大的查询一直未查询完成，导致truncate这个人员表，无法活动meta的锁，后续执行抽取和计算的都报错......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99