首页 > 其他分享 >[CSP-J2023]旅游巴士

[CSP-J2023]旅游巴士

时间:2023-11-01 10:34:55浏览次数:55  
标签:nk idx int 复杂度 mid 巴士 J2023 CSP define

P9751 [CSP-J 2023] 旅游巴士

本题主要的难点在于到达和离开景区的时间都必须是 \(k\) 的非负整数倍以及每条道路均设置了一个 “开放时间” \(a_i\)。

对于第一个限制,只需要拆点,将每个点拆成距离 \(\bmod k=0\sim k-1\)。

对于第二个限制,发现求的是最小值,答案具有二段性,可二分。二分之后,就可以从终点往起点推,由于越晚可以走的边越多,此时可以贪心的求,类似最短路,到达起点看一下能到且距离大于等于 \(0\)。

可以发现图最多有 \(nk\) 个点,所以答案是在 \(nk\) 量级以内,二分时的复杂度是 \(O(\log n)\)(因为必须是 \(k\) 的倍数),check 需要 bfs,复杂度 \(O(nk)\),所以总复杂度是 \(O(nk\log n)\)。

#include<iostream>
#include<cstring>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while

const int N=10010,M=20010,K=110;
int n,m,k,h[N],e[M],ne[M],w[M],idx,dis[N][K];
typedef pair<int,int> pii;
pii q[N*K];//don't forget memset h!
void add(int a,int b,int c){
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool check(int mid){
	// cout<<mid<<'\n';
	memset(dis,-0x3f,sizeof dis);
	dis[n][0]=mid;
	int hh=0,tt=0;
	q[tt++]={n,0};
	Wh(hh!=tt){
		auto p=q[hh++];
		int x=p.first,y=p.second;
		// cout<<x<<' '<<y<<' '<<dis[x][y]<<'\n';
		Ed{
			int j=e[i],we=w[i],ne=y?y-1:k-1;
			if(dis[x][y]>we&&dis[j][ne]<dis[x][y]-1){
				dis[j][ne]=dis[x][y]-1;
				q[tt++]={j,ne};
			}
		}
	}
	return dis[1][0]>=0;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	#endif
	#ifdef ONLINE_JUDGE
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	#endif
	cin>>n>>m>>k;
	memset(h,-1,n*4+4);
	W(m){
		int a,b,c;
		cin>>a>>b>>c;
		add(b,a,c);
	}
	int l=0,r=(2e6+100)/k;
	Wh(l<r){
		// cout<<l<<' '<<r<<'\n';
		int mid=l+r>>1;
		if(check(mid*k))r=mid;
		else l=mid+1;
	}
	// cout<<l<<' '<<r<<'\n';
	if(!check(r*k))cout<<"-1\n";
	else cout<<r*k<<'\n';
	return 0;
}

标签:nk,idx,int,复杂度,mid,巴士,J2023,CSP,define
From: https://www.cnblogs.com/wscqwq/p/17802468.html

相关文章

  • P5659 [CSP-S2019] 树上的数
    相信大家都看过题,但还请搞清楚是数对应结点编号。这里用\(a_i\)表示\(i\)号结点对应的数。对于\(n\leq10\)的数据,全排列出删边的顺序然后模拟,取字典序最小的方案。对于菊花,仍然考虑删边的顺序,假设删边依次是\(rt\tov_1,rt\tov_2,\cdots,rt\tov_{n-1}\)。因为每删一......
  • P5666 [CSP-S2019] 树的重心
    考虑一个结点在什么情况下会成为重心。随便钦定一个根结点。对于结点\(u\),假设割掉了其子树\(v\)中的某条边或连接\(u\)和\(v\)的边,形成了一棵大小为\(k\)的新树。令\(mx\)表示除\(v\)子树外最大的子树大小(或\(n-siz_u\))。如果\(u\)成为了重心根据定义有\(2\ti......
  • HN CSP-2023 游祭
    以下时间均以初赛为\(0\)点(2023.09.16)Day-3免作业条批了,不用写作业了。Day-2不用写作业,晚上就随便搞搞,模拟了一下之前的csp-s初赛,打的还行罢。Day-1最后一天了,冲刺初赛!晚上有洛谷入门赛,当信心赛打了,rk69。有一道题没去想就被准点放学赶出机房了,回去也没时间写。......
  • CSP-S2 好似记
    CSP-S2好似记似了,但还是发一下。一周前教练让写的。1min发呆5min缺省源10min通看一遍题5min仔细看T1,大概是一个简单搜索5min仔细看T2,大概是一个简单DP5min仔细看T1,5min仔细看T2,5min仔细看T1,5min仔细看T2,5min,看T1题面+模拟样例。看不懂。5min,......
  • CSP-S 2022 游记&总结
    智慧神说要写总结,所以就叫总结啦Day-1上午收拾了下行李,中午出发坐高铁去九江了,高铁上本来想临时学一下class的用法的(说不定用得上),结果看着CSDN竟然睡着了......下午四点左右到了,九江在下小雨(话说赣州好久没下雨了QWQ),忘记带伞了,最后还是蹭cjc的伞去的宾馆。晚上收手机前打......
  • CSPRO 历届题目与题解
    官方题目链接:http://118.190.20.162/\(\Huge目录\)201609201612201709202104202109202112202203202206202209202303202305202309\(\Huge\text{CSP201609}\)火车购票问题描述请实现一个铁路购票系统的简单座位分配算法,来处理一节车厢的座位分配。假设一节车厢......
  • CSP-S 2023 邮寄
    前言先咕着,等什么时候心情好了再继续写。省流云斗OJ:T1100,T235,T3100,T40正文周五中午出发去九江,做的是高铁?路上看完了三本小说(但其实都是之前看过的),终于是到了九江。做出租车做了一个小时,收费73RMB(好贵QAQ),但是后来好像报销了???晚上和小A住一起(想吃外星人酿的苹果了)。晚......
  • [CSP-S2020] 儒略日 题解
    [CSP-S2020]儒略日今儿终于做掉困扰多年的题目了,其实想好细节也不难。容易发现儒略历和格里高利历的润年判断方式不一样,并且中间有消失的十天,计算起来相当不方便。所以我们可以首先计算出\(-4713.1.1\)~\(1582.10.4\)会经过多少天,可以通过一天一天暴力跳的方法计算出需要\(......
  • CSP-J 前三题详解
    没写完。先补会儿文化课作业,等会再回来继续写。T1P9748[CSP-J2023]小苹果令苹果数量为\(\texttt{n}\)。容易发现,拿苹果就是每三个一组,取第一个。需要注意的是,如果以三个一组来考虑拿苹果,最后几个苹果不满三个时也应该算一个组,第一个也要拿走。形式化的,即当\(\texttt{n}......
  • 周藤 CSP-2023游记
    Day-inf~Day-2基本上是考试状态,每天我都是自己取随机题目做,不过也保证了落实量每场模拟赛发挥基本上是不是特别稳定,考得好的时候AK了,考不好的时候只有300分,反正同届差不多第一吧。。。不过还被几个人诅咒爆零了,不过没事,一交解千愁/seDay-1教练说了考试注意事项,然后就去娱......