2022年信息学奥赛NOI省选真题

NOI2022省选 DAY1 时间： 2023年4月 1日 08:30 ∼2022 年4月 1日 13:00 题目名称 火车站 城市建造 人员调度 题目类型 传统型 传统型 传统型 目录 station cities transfer 可执行文件名 station cities transfer 输入文件名 station.in cities.in transfer.in 输出文件名 station.out cities.out transfer.out 每个测试点时限 1.0秒 1.0秒 5.0秒 内存限制 512 MiB 512 MiB 512 MiB 测试点数目 10 20 50 测试点是否等分 是 是 是 提交源程序文件名 对于 C++ 语言 station.cpp cities.cpp transfer.cpp 编译选项 对于 C++ 语言 ‐O2 ‐std=c++14 ‐static .注 .意 .事 .项（ .请 .仔 .细 .阅 .读） 1. 文件名（程序名和输入输出文件名）必须使用英文小写。 2. C/C++ 中函数main()的返回值类型必须是 int，程序正常结束时的返回值必须 是 0。 3. 提交的程序代码文件的放置位置请参考各省的具体要求。 4. 因违反以上三点而出现的错误或问题，申诉时一律不予受理。 5. 若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。 6. 选手提交的程序源文件必须不大于 100KB。 7. 程序可使用的栈空间内存限制与题目的内存限制一致。 8. 全国统一评测时采用的机器配置为： Intel(R) Core(TM) i7-8700K CPU @3.70GHz ， 内存 32GB 。上述时限以此配置为准。 9. 只提供 Linux格式附加样例文件。 10. 评测在当前最新公布的 NOI Linux下进行，各语言的编译器版本以此为准。 NOI2022 省选 DAY1火车站（ station） 火车站（station） 【题目描述】有 n个火车站排成一条直线，从 1到 n编号。一共有 m条火车轨道，每条轨道覆 盖一段火车站区间 [l i, r i] 。 对于一个被多条火车轨道覆盖的火车站，火车在经过这里的时候，可以在此处改变 轨道。但是火车无法掉头，只能朝着一个方向运行（即只能一直往 1的方向开或者一直 往 n的方向开）。 小 A从火车站 x出发，即搭上了经过 x的任意一列火车（这列火车也可能是从车 站 x出发）。这列火车可能行驶在火车站 x所处的任一条轨道上，其运行方向既可能是 往 1的方向开，也可能是往 n的方向开。小 A上车后就开始昏睡，直到乘坐的火车到 达某条线路的终点站停下，他才醒过来。问小 A最后可能到达的车站。 注意：火车应运行至少一个车站，且火车切换轨道后不会立刻停下来，而是会继续 沿着当前轨道前进。 【输入格式】从文件 station.in 中读入数据。 输入的第一行包含三个正整数 n, m ,x，分别表示火车站的数量，火车轨道的数量 以及小 A初始的起点。 接下来 m行，每行包含两个正整数 l i, r i，表示一条火车轨道运行的区间。 【输出格式】输出到文件 station.out 中。 输出一行，包含若干个用单个空格分隔的正整数，表示小 A最后可能到达的车站， 按照车站编号升序排序输出。 【样例 1输入】 1 7 5 4 2 3 4 3 4 6 4 1 3 5 5 7 6 4 6 第2页 共 9 页 NOI2022 省选 DAY1火车站（ station） 【样例 1输出】 1 1 3 6 7 【样例 1解释】 火车从车站 4出发，沿着第一条轨道可以运行到终点 3，也可以接着沿第三条轨道 运行到终点 1。 火车从车站 4出发，沿着第二条轨道可以运行到终点 6，也可以在车站 5换到第四 条轨道运行到终点 7。 所以最终按顺序输出 1, 3, 6, 7。 【样例 2】 见选手目录下的 station/station2.in 与station/station2.ans 。 【样例 3】 见选手目录下的 station/station3.in 与station/station3.ans 。 【样例 4】 见选手目录下的 station/station4.in 与station/station4.ans 。 【数据范围】对于所有的数据，保证 1≤ n, m ≤2× 105 ； 1≤ x≤ n； 1≤ l i < r i≤ n。 测试点 n, m≤ 特殊性质 1 50 无2 3 50004 5 6 2× 105 A 7 8 无9 10 特殊性质 A：保证 x= 1 。 第3页 共 9 页 NOI2022 省选 DAY1城市建造（ cities） 城市建造（cities） 【题目描述】在这个国度里面有 n座城市，一开始城市之间修有若干条双向道路，导致这些城市 形成了 t≥ 2个连通块，特别的，这些连通块之间两两大小差的绝对值不超过 0≤ k≤ 1。 为了方便城市建设与发展， n座城市中的某 t座城市 .在 .这t .座 .城 .市 .之 .间额外修建了至少 一条双向道路，使得所有城市连通。 现在已经知道额外修建后的所有道路，你需要算出有哪些双向道路集合 E′ ，满足这 些道路有可能是后来额外修建的，请输出答案对 998,244 ,353 取模的结果。 即给定一张 n个点 m条边的 .无 .向 .连 .通图 G= ( V , E )，询问有多少该图的子图 G ′ = ( V′ , E ′ ) ，满足 E′ ̸ = ∅ 且 G− E′ 中恰好有 |V ′ | 个连通块，且任意两个连通块大小 之差不超过 k，保证 0≤ k≤ 1，请输出答案对 998,244 ,353 取模的结果。 【输入格式】从文件 cities.in 中读入数据。 输入的第一行包含三个正整数 n, m, k，分别表示城市数、修建后的道路数以及任意 两个连通块大小之差的上限。 接下来 m行每行包含两个正整数 u, v，表示城市 u和 v之间存在一条双向道路，保 证 u̸ = v。 【输出格式】输出到文件 cities.out中。 输出一个数表示