题目描述 一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站.每个火车站都有一个级 别,最低为 1 级.现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车 次停靠了火车站 x,则始发站.终点站之间所有级别大于等于火车站 x 的都必须停靠.(注 意:起始站和终点站自然也算作事先已知需要停靠的站点) 例如,下表是 5 趟车次的运行情况.其中,前 4 趟车次均满足要求,而第 5 趟车次由于 停靠了 3 号火车站(2 级)却未停靠途经的 6 号火车站(亦为 2 级)而

题目传送门 我们注意到,题目中说:如果这趟车次停靠了火车站 x,则始发站.终点站之间所有级别大于等于火车站x的都必须停靠.有阶级关系,满满的拓扑排序氛围.但是,如果我们按大于等于的关系连,等于的情况就会连双向边,这不利于我们在有向无环图中(DAG)进行拓扑排序.于是我们不妨换一种思路,将所有小于当前火车站级别的车站向输入的车站序列间连一条有向边.之后边拓扑排序边更新车站级数即可. 注意建图的细节过程.首先对于每个车次,我们应该从起点出发终点结束,也就是代码中的w[1]和w[n]:其次由于有很多车

妈蛋这道普及组水(神)题搞了我非常久. 一. 首先一个非常显然的事情就是每一个火车告诉了站与站之间的等级关系,所以拓扑求最长路. 可是发现暴力建边的话最坏能够达到500*500,所以时间复杂度有O(MN2)≈2.5∗108,常数相当小. .数据水成狗,所以绝对能够过的. 二. 所以我就想到了bitset,把每辆火车做成一个长N的布尔向量.经过为1,不经过为0,第一个车站的左边和最后一个车站的右边补1,. 然后对于每一个车站,把全部它所在的位为1的向量都&起来,然后扫一遍向量连边. 这样做的时间复

题目描述 一条单向的铁路线上,依次有编号为 1, 2, …, n1,2,…,n的 nn个火车站.每个火车站都有一个级别,最低为 11 级.现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 xx,则始发站.终点站之间所有级别大于等于火车站xx 的都必须停靠.(注意:起始站和终点站自然也算作事先已知需要停靠的站点) 例如,下表是55趟车次的运行情况.其中,前44 趟车次均满足要求,而第 55 趟车次由于停靠了 33 号火车站(22 级)却未停靠途经的 66 号火车站(亦

题面 题解 不难想到拓扑排序 于是每一个等级高的向等级低的连一条边 考虑拓扑排序过程中的分层 对于每个点进行分层 于是答案就是这些点中的最大层数 然后就会RE 发现我们多连了一些重复的边 用一个标记数组记录两个点之间是否连边即可 代码 #include <bits/stdc++.h> using namespace std; inline int gi() { int f = 1, x = 0; char c = getchar(); while (c < '0' || c > '

[NOIP2013 普及组]车站分级 一.题目 [NOIP2013 普及组]车站分级 时间限制: 1 Sec  内存限制: 128 MB 提交: 3  解决: 0 [提交][状态][讨论版] 题目描述 一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站.每个火车站都有一个级别,最低为 1 级.现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 x,则始发站.终点站之间所有级别大于等于火车站 x 的都必须停靠.(注意:起始站和终点站自然也算作事先已

P1983 车站分级 297通过 1.1K提交 题目提供者该用户不存在 标签图论贪心NOIp普及组2013 难度普及/提高- 提交该题 讨论 题解 记录 最新讨论 求帮忙指出问题! 我这么和(diao)谐(zha)… 题目描述 一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站.每个火车站都有一个级 别,最低为 1 级.现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车 次停靠了火车站 x,则始发站.终点站之间所有级别大于等于火车站 x 的都必须停靠.(注 意

车站分级 题目链接 首先,可以发现火车停靠站点的大小是没有什么规律的, 火车可以停靠在级别<=当前级别的站点,必须停靠在级别>=当前最高级别的站点 但是所有没有被停靠的站点级别一定比所有被停靠了的站点级别低 于是就可以据此建一个DAG,拓扑排序或记搜即可 (O(n^3)建图居然过了) #include<iostream> #include<cstring> #include<cstdio> #include<bitset> using names

洛谷\(P1983\)车站分级(拓扑排序) 目录 题目描述 题目分析 思路分析 代码实现 题目描述 题目在洛谷\(P1983\)上 ​ 题目: 一条单向的铁路线上,依次有编号为 \(1, 2, -, n1,2,-,n\)的 \(n\)个火车站.每个火车站都有一个级别,最低为 11 级.现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 \(x\),则始发站.终点站之间所有级别大于等于火车站\(x\) 的都必须停靠.(注意:起始站和终点站自然也算作事先已知需要停靠的站点

问题描述 LG1983 题解 考虑建立有向边\((a,b)\),代表\(a\)比\(b\)低级. 于是枚举每一辆车次经过的车站\(x \in [l,r]\),如果不是车辆停靠的车站,则从\(x\)向每个停靠了的车站连边. 拓扑排序,建立分层图,搞出最大的层数即可. \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; template <typename Tp> void read(Tp &x){ x=

思路: 对于每一趟车,将区间内所有经停的站和所有未经停的站连一条边,表示前者优先级一定高于后者,然后用Kahn跑一遍拓扑排序即可.然而这样会创造大量多余的边,会TLE1个点.考虑一种优化:因为每趟车本身也有一个优先级,因此可以将这趟车也看作一个点,每次先所有将经停的站连一条边到这两车上,表示这些站的优先级一定大于等于车的优先级,再将车连若干边到未经停的点,表示车的优先级一定大于未经停的站的优先级. #include<queue> #include<cstdio> #include&

题目描述 一条单向的铁路线上,依次有编号为 , , …, n 的 n 个火车站.每个火车站都有一个级别,最低为 级.现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 x,则始发站.终点站之间所有级别大于等于火车站 x 的都必须停靠.(注意:起始站和终点站自然也算作事先已知需要停靠的站点) 例如,下表是 趟车次的运行情况.其中,前 趟车次均满足要求,而第 趟车次由于停靠了 号火车站( 级)却未停靠途经的 号火车站(亦为 级)而不满足要求. 现有 m 趟车次的运行情况(

题目链接 https://www.luogu.org/problemnew/show/P1983 题目描述 一条单向的铁路线上,依次有编号为 1,2,…,n的 n个火车站.每个火车站都有一个级别,最低为1 级.现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 x,则始发站.终点站之间所有级别大于等于火车站x 的都必须停靠.(注意:起始站和终点站自然也算作事先已知需要停靠的站点) 例如,下表是5 趟车次的运行情况.其中,前4 趟车次均满足要求,而第 5趟车次由于停靠了

题目 这个题非常毒瘤,只要还是体现在其思维难度上,因为要停留的车站的等级一定要大于不停留的车站的等级,因此我们可以从不停留的车站向停留的车站进行连边,然后从入度为0的点即不停留的点全都入队,然后拓扑排序即可 代码 #include <bits/stdc++.h> #pragma GCC optimize(2) #pragma GCC optimize(3) using namespace std; int in[199091], lin[100100], dep[100100], data[1

题目来源:NOIP2013 普及第四题 题目描写叙述 Description 一条单向的铁路线上,依次有编号为1, 2, -, n的n个火车站.每一个火车站都有一个级别,最低为1级.现有若干趟车次在这条线路上行驶.每一趟都满足例如以下要求:假设这趟车次停靠了火车站x.则始发站.终点站之间全部级别大于等于火车站x的都必须停靠. (注意:起始站和终点站自然也算作事先已知须要停靠的网站) 比如,下表是5趟车次的执行情况.当中.前4趟车次均满足要求,而第5趟车次因为停靠了3号火车站(2级)却未停靠途经的

题目大意 一些火车站排成一行.给出一些火车的停靠站情况,要求对每一个火车,其经过且不停靠的站的级别比它任意停靠的站的级别小.问所有车站最少需要多少个级别. 题解 不要只看到这道题的背景设立在一个区间上,就只想线段上的动规与贪心.由火车停靠站的情况可以得到不同站与不同站之间的级别满足偏序关系,这样就可以建立拓扑图求最长路径即可. 普通建图$O(nm)$,要注意重边的情况,否则会MLE. #include <cstdio> #include <cstring> #include <

题目描述 一条单向的铁路线上,依次有编号为 1, 2, -, n1,2,-,n的 nn个火车站.每个火车站都有一个级别,最低为 11 级.现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 xx,则始发站.终点站之间所有级别大于等于火车站xx 的都必须停靠.(注意:起始站和终点站自然也算作事先已知需要停靠的站点) 例如,下表是55趟车次的运行情况.其中,前44 趟车次均满足要求,而第 5 趟车次由于停靠了 3 号火车站(2级)却未停靠途经的 6号火车站(亦为 2 级)

这题好像是个蓝题.(不过也确实差不多QwQ)用到了拓扑排序的知识 我们看这些这车站,沿途停过的车站一定比未停的车站的级别高 所以,未停靠的车站向已经停靠的车站连一条边,入度为0的车站级别就看做1 然后我们把入度为0的边依次取出来,那么它的出边所指车站就一定比这个车站级别高 那么也就是说,一个车站的级别一定比所有指向它的车站中,级别最高的那个车站级别还要高1级 (x的级别小于y) 再跑一个拓扑就行了qwq Code: #include<bits/stdc++.h> using namespace

%%%rqy 传送 我们注意到题目中这段话: 既然大于等于x的站都要停,那么不停的站的级别是不是都小于x?(这里讨论在始发站和终点站以内的站(注意这里是个坑)) 我们可以找出每趟车没停的站,向所有停了的站建一条边,表示没停的站的级别<停了的站的级别,同时记录所有的站的入度 这样,一开始入度为0的站级别就是1. 对于那些入度不为0的点来说,它们的级别就是所有指向它的点中,级别最大的那个点的级别+1 for example 因为每个级别为a车站x不一定只有级别为a-1的车站向x连边. 那程序怎么实现

对每趟车建一个虚点p,对于不停车的x,连边(x,p,1):对于停车的y,连边(p,y,0)有一条边(a,b,l)就是说b-a>=l由于题目保证一定能走,直接拓扑序dp算最大的就行了 #include<bits/stdc++.h> #define pa pair<int,int> #define CLR(a,x) memset(a,x,sizeof(a)) using namespace std; typedef long long ll; ,maxm=2e6+; inline