【NOIP2013普及组复赛】题4:车站分级

2024-05-24 12:12

本文主要是介绍【NOIP2013普及组复赛】题4:车站分级,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题4:车站分级

【题目描述】

一条单向的铁路线上,依次有编号为 1 , 2 , … , n 1,2,…,n 1,2,,n n n n 个火车站。每个火车站都有一个级别,最低为 1 1 1 级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 x x x,则始发站、终点站之间所有级别大于等于火车站 x x x 的都必须停靠。(注意:起始站和终点站自然也算作事先已知需要停靠的站点)

例如,下表是 5 5 5 趟车次的运行情况。其中,前 4 4 4 趟车次均满足要求,而第 5 5 5 趟车次由于停靠了 3 3 3 号火车站( 2 2 2 级)却未停靠途经的 6 6 6 号火车站(亦为 2 2 2 级)而不满足要求。
在这里插入图片描述
现有 m m m 趟车次的运行情况(全部满足要求),试推算这 n n n 个火车站至少分为几个不同的级别。

【输入文件】

第一行包含 2 2 2 个正整数 n , m n,m n,m,用一个空格隔开。

i + 1 i+1 i+1 ( 1 ≤ i ≤ m ) (1≤i≤m) 1im中,首先是一个正整数 s i ( 2 ≤ s i ≤ n ) si(2≤s_i≤n) si2sin,表示第 i i i 趟车次有 s i s_i si 个停靠站;接下来有 s i s_i si 个正整数,表示所有停靠站的编号,从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

【输出文件】

输出只有一行,包含一个正整数,即 n n n 个火车站最少划分的级别数。

【输入样例1】

9 2
4 1 3 5 6
3 3 5 6

【输出样例1】

2

【输入样例2】

9 3
4 1 3 5 6
3 3 5 6
3 1 5 9

【输出样例2】

3

【数据范围】

对于 20 % 20\% 20% 的数据, 1 ≤ n , m ≤ 10 1≤n,m≤10 1n,m10

对于 50 % 50\% 50% 的数据, 1 ≤ n , m ≤ 100 1≤n,m≤100 1n,m100

对于 100 % 100\% 100% 的数据, 1 ≤ n , m ≤ 1000 1≤n,m≤1000 1n,m1000

【代码如下】:

#include <bits/stdc++.h>
using namespace std;
ifstream cin("level.in");
ofstream cout("level.out");
struct cs {int to, next;
} a[1000001];
int b[1001], f[1001], head[1001];
bool vi[1001][1001];
int n, m, x, y, z, ans, ll;
void init(int x, int y) {a[++ll].to = y;a[ll].next = head[x];head[x] = ll;
}
int dfs(int x) {for (int k = head[x]; k; k = a[k].next)if (!f[a[k].to])f[x] = max(f[x], dfs(a[k].to));elsef[x] = max(f[x], f[a[k].to]);return ++f[x];
}
int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {cin >> z;for (int i = 1; i <= z; i++) cin >> b[i];int l = 1;for (int i = b[1]; i < b[z]; i++) {if (b[l] == i) {l++;continue;} else {for (int k = 1; k <= z; k++) {if (!vi[b[k]][i]) {init(b[k], i);vi[b[k]][i] = 1;}}}}}for (int i = 1; i <= n; i++) {if (!f[i]) {ans = max(ans, dfs(i));}}cout << ans;
}

这篇关于【NOIP2013普及组复赛】题4:车站分级的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/998369

相关文章

安科瑞ASJ漏电流继电器在轨道交通地铁车站配电系统中的应用

应用背景 城市轨道交通设备门类复杂、数量庞大、分布广泛,在长期连续运行时存在火灾隐患。在国内外的地铁火灾中,因电气原因引起的火灾占比最大,达到37%,其中供电线路的漏电流更是造成电气火灾的重要因素。消防部门、行业专家往往要求地铁车站设置电气火灾监控系统,但在地铁监控防范措施中,泄漏电流的监测并不完善,现有的泄漏电流监测系统存在误报现象,使得配电系统漏电保护 频繁跳闸。为此,查找频繁误报警原因,采

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

百度之星 2015 复赛 1001 (数长方形)

数长方形    Accepts: 595    Submissions: 1225  Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description 小度熊喜欢玩木棒。一天他在玩木棒的时候,发现一些木棒会形成长方形

内蒙古土壤各种养分含量标准分级表

内蒙古地区的土壤类型复杂多样,涵盖草原、荒漠、森林等不同生态系统,土壤养分含量因气候和地域差异较大。因此,内蒙古地区土壤养分含量的标准分级主要根据当地的土壤特性进行划分。以下是根据常见的内蒙古地区土壤类型(如草原土、黑土、沙土等)给出的养分含量标准分级表: 1. 全氮含量标准(g/kg) 等级草原土森林土沙质土极低< 0.3< 0.5< 0.2低0.3 - 0.60.5 - 0.80.2 -

【软件测试】软件测试-----什么是Bug?Bug是如何分级的?Bug的生命周期是怎样的?如何描述一个Bug?

博客目录 一.软件测试的生命周期二.BUG的定义和级别2.1 bug的概念.2.2 如何描述一个bug.2.3bug的级别2.3.1 bug分级的意义.2.3.2 bug的四种级别. 三.BUG的生命周期.四.当与开发人员发生冲突该如何处理(高频面试)五.总结 一.软件测试的生命周期 软件测试贯穿于软件的整个生命周期,针对这句话我们一起来看一下软件测试是如何贯穿软件的整个生命周

CSP-J/S 复赛程序提交指南,提交错误必爆零!!!

CSP-J/S 复赛题目程序需要以文件的形式提交,如果之前没有了解过,那肯定会爆0,该怎么操作呢? 大家好,我是大李。 针对复赛考试提交详情,这里做个详细介绍,分为文件的创建和文件体提交等事项。 一、关于文件建立 复赛考试时需要根据提示,在桌面建立文件夹,将含有文件体的cpp文件保存至桌面。 每一题的命名都需要根据提示来去命名。 以2023年CSP-J/S 第二轮为例 在电

信息学奥赛初赛天天练-83-NOIP2014普及组-基础题2-输入设备、输出设备、操作系统、二进制、整数除法、while、do while循环

1 NOIP 2014 普及组 基础题2 4 以下哪一种设备属于输出设备( ) A 扫描仪 B 键盘 C 鼠标 D 打印机 5 下列对操作系统功能的描述最为完整的是( ) A 负责外设与主机之间的信息交换 B 负责诊断机器的故障 C 控制和管理计算机系统的各种硬件和软件资源的使用 D 将没有程序编译成目标程序 11 下列各无符号十进制整数中,能用八位二进制表示的数中最大的是( ) A 296

免费SSL证书大全,加速普及网站实现HTTPS加密

免费SSL证书大全,加速普及网站实现HTTPS加密   SSL 证书用于加密 HTTP 协议,实现网站通过HTTPS加密协议访问。随着国内外各大网站实现全站 HTTPS 协议,以及搜索引擎对使用 HTTPS 协议网站的更加友好,加之互联网对数据和隐私安全的加强,网站添加 SSL 证书并实现 HTTPS 加密协议访问已经成为趋势和必然。 SSL证书大全​zzzjtd.com 而对于给网站添加

讨论运维监控工具的普及程度

在讨论运维监控工具的普及程度时,加入PIGOSS BSM产品的分析是非常有意义的,因为PIGOSS BSM是一款在中国市场具有一定影响力的运维监控工具。 PIGOSS BSM运维监控工具是一款综合性的IT运维监控解决方案,它能够对多层次的IT资源进行监测,包括但不限于性能监测、事件管理、报表管理等功能模块。PIGOSS BSM的一个独特之处在于其拓扑关联配置工具,这使得用户可以根据自身的I

P2239 [NOIP2014 普及组] 螺旋矩阵

P2239 [NOIP2014 普及组] 螺旋矩阵 50分 //O(n^2)复杂度,能算n<=10000的 #include <bits/stdc++.h>using namespace std;//row当前行, column当前列, left:左边界,righ:右边界,top:上边界,bottom:下边界 int n, x, y, ans, row=1, column=0, lef,