（2021.8.15 更新）洛谷主题库试题提供以及反馈帖

工单反馈版

chen_zhe @ 2020-01-19 19:25:41

洛谷鼓励各位用户将大型比赛的试题或者洛谷上缺乏的模板题，在确认没有版权问题的情况下，提供给洛谷。但是因为此类贴子日益增多，严重影响了讨论版面，而且部分用户所提供的试题并不符合规定，故做出以下说明：

所谓的大型比赛，指的是国家或者地区级别的比赛（例如 USACO，POI，Baltic OI 等），或者大型的网络公开赛（例如 Codeplus 等），但是不包含例如校内的网络模拟赛之类的试题。
请注意，JOI 有关竞赛（包括 JOI open）原则上是不接受用户投题的。对于其它大型竞赛题目，如果测试点过多且单个测试点时间过长也有被拒绝的可能。如果您希望搬运这类比赛题，请提前咨询管理员。另外 USACO 的铜组也不接受用户投题。
对于模板题，其在现在的 OI 中，必须存在一定的实际意义，不能是非常生僻的，全网可能没有一个算法竞赛题涉及到相关知识点的算法或者数据结构。洛谷现决定根据 OI-Wiki 判断一个模板是否有存在的必要，即必须在 OI-Wiki 中有一个专门的页面。对于以前不符合此项要求的模板题，取消模板标签。同时，建议在造模板题之前先与管理员私信沟通好洛谷是否接受该模板。
贡献大型比赛的试题必须确保没有版权争议。为防止出现版权问题导致的不必要纠纷，供题时必须标注题目来源，搬运题目必须标注原题链接。若需搬运来自其他 Online Judge 的翻译题，必须确保没有任何版权问题的情况下，按照洛谷主题库题目规范所要求的格式以及对方 Online Judge 的版权要求进行搬运。若贡献明显有版权问题的题目，视情节严重程度处以警告/禁言/棕名/封号的惩罚。另外，对于比赛赛题，请一次性提交一场比赛中所有的题目。只有在题库中相应比赛的题目出现缺漏的时候才允许零散提交。特殊地，对于 COCI 题目，如果题库中只缺失 AB 两题，从现在起不再接受补充，但是对于整套提供的题目，仍然接受前两题。
贡献的题目需严格遵守洛谷主题库题目规范，请在贡献之前对照规范逐字逐句检查。特别地，所提供的试题中，若需要 spj，则相对较易的部分必须自行完成。若实在有困难才可以征集。具体尺度由管理进行评判。
在本讨论中，允许用户提供试题，要求用户至少达到绿勾级别。
贡献题目禁止单独开帖，请在此讨论下回复，若恶意浪费管理员时间，视情节严重程度处以警告/禁言/封号的惩罚。
原则上不收距今超过 20 年（含）的题目，如果题目具有特殊价值，可以联系管理员添加单题（而不是整套提供）

同时，对于已在洛谷主题库中但不符合洛谷主题目题目规范的题目，我们鼓励用户进行更正，但也至少要达到绿勾级别。要求更正后的题面严格遵守规范，同样回复在本讨论下，为了方便管理员，请将题面使用代码框```括起来。

若有发现难度标签明显有问题（即对于普及-以及以下的题目相差两个档次，或者对于提高-以及以上难度相差一个档次），欢迎大家提供建议。请在本楼回复题号和应当修正的难度。

为了提高管理员的审核效率，本贴禁止任何无意义回复，所有无意义回复均会被删除，行为恶劣者将会禁言，但是可以询问说明中的问题。若为修复题目问题，建议带上链接以增加效率。

请不要@管理员，会有管理员不定期来本帖处理。

by 霍士弘 @ 2020-02-06 14:09:03

类型：试题提供
题目：【模板】树的重心

by Karry5307 @ 2020-02-06 16:02:22

@mrsrz

类型：试题提供

题目：[JSOI2010]排名

by Karry5307 @ 2020-02-06 18:10:30

@StudyingFather

by StudyingFather @ 2020-02-06 18:11:55

@Karry5307 added & thanks

by 木木！ @ 2020-02-06 18:25:43

类型：题面修改题目：P2620 虫洞新题面：

题目背景

applepi 想进行宇宙旅行。当然，applepi 知道这是有可能的，因为 applepi 的特殊能力能使他观测到宇宙中的虫洞。所谓虫洞就是一个在三维之外的维度打开的快捷通道，通过虫洞能够从一个地方瞬间移动到另外一个地方。

applepi 想进行宇宙旅行。当然，applepi 知道这是有可能的，因为 applepi 的特殊能力能使他观测到宇宙中的虫洞。所谓虫洞就是一个在三维之外的维度打开的快捷通道，通过虫洞能够从一个地方瞬间移动到另外一个地方。

题目描述

为了简化问题，我们建立一个一维坐标系，地球的位置为 0，而 applepi 的目的地的位置是一个正整数 w。在每一个单位时间里，applepi 可以向正方向移动不超过 s 的一个整数。虫洞可以被表示为二元组 \left(b_i, e_i\right)，即如果在某次移动之后 applepi 在位置 b_i，那么 applepi 就会被立刻传送到位置 e_i。注意，applepi 在移动过程中如果经过位置 b_i，由于 applepi 的速度极快是不会被传送的。而且，applepi 不能够向负方向移动，但是虫洞引起的除外。现在 applepi 想请你帮助他计算一下他至少需要多少个单位时间才能够到达目的地。

为了简化问题，我们建立一个一维坐标系，地球的位置为 0，而 applepi 的目的地的位置是一个正整数 $w$。在每一个单位时间里，applepi 可以向正方向移动不超过 $s$ 的一个整数。虫洞可以被表示为二元组 $\left(b_i, e_i\right)$，即如果在某次移动之后 applepi 在位置 $b_i$，那么 applepi 就会被立刻传送到位置 $e_i$。注意，applepi 在移动过程中如果经过位置 $b_i$，由于 applepi 的速度极快是不会被传送的。而且，applepi 不能够向负方向移动，但是虫洞引起的除外。现在 applepi 想请你帮助他计算一下他至少需要多少个单位时间才能够到达目的地。

输入格式

输入包含多组测试数据。

每组测试数据的第一行是三个正整数 w,s,p，表示目的地位置，移动限制和虫洞的数目。之后 p 行，每行两个整数 b_i 和 e_i，表示一个虫洞。

输入文件的最后一行是一个整数 0，表示输入的结束。

输入包含多组测试数据。

每组测试数据的第一行是三个正整数 $w$,$s$,$p$，表示目的地位置，移动限制和虫洞的数目。之后 $p$ 行，每行两个整数 $b_i$ 和 $e_i$，表示一个虫洞。

输入文件的最后一行是一个整数 0，表示输入的结束。

输出格式

对于每组测试数据，在单独的一行内输出结果。

对于每组测试数据，在单独的一行内输出结果。

输入输出样例

输入

输出

4
3

说明/提示

对于 30\% 的数据，w\leq 1000。

对于 100\% 的数据，0\leq w\leq10^9，2\leq s\leq 6，1\leq p\leq 40，没有 b_i=0 或 b_i=w 的虫洞，输入数据保证目的地可达。

对于 $30\%$ 的数据，$w\leq 1000$。

对于 $100\%$ 的数据，$0\leq w\leq10^9$，$2\leq s\leq 6$，$1\leq p\leq 40$，没有 $b_i=0$ 或 $b_i=w$ 的虫洞，输入数据保证目的地可达。

by wmy_goes_to_thu @ 2020-02-06 21:48:11

类型：试题提供题目：[USAICO2005]布丁

by wmy_goes_to_thu @ 2020-02-06 21:54:56

@StudyingFather

by wmy_goes_to_thu @ 2020-02-07 08:54:04

类型：试题提供

题目：【模板】分层图最短路

by wmy_goes_to_thu @ 2020-02-07 08:54:18

@StudyingFather

by Karry5307 @ 2020-02-07 08:55:47

@wangmaohua20090908 有类似的题