（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 u2004 @ 2020-02-03 16:47:08

类型：题面修改

题目：【模板】manacher算法

### 题目描述
给出一个只由小写英文字符 $a,b,c...y,z$ 组成的字符串 $S$ ,求 $S$ 中最长回文串的长度 。

字符串长度为 $n$ 。

### 输入格式
一行小写英文字符 $a,b,c...y,z$ 组成的字符串 $S$ 。

### 输出格式
一个整数表示答案 。

### 说明/提示
字符串长度 $len \le 11000000$。

题目描述

给出一个只由小写英文字符 a,b,c...y,z 组成的字符串 S ,求 S 中最长回文串的长度。

字符串长度为 n 。

输入格式

一行小写英文字符 a,b,c...y,z 组成的字符串 S 。

输出格式

一个整数表示答案。

说明/提示

字符串长度 len \le 11000000。

by 警策看取 @ 2020-02-04 10:35:08

@Gomory_Hu_Tree 有些东西不需要LaTeX吧，像人名之类的

by cnyzz @ 2020-02-04 11:15:26

类型：题面修改

题目：营救

#### 题目描述
“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动的热泪盈眶，开起了门……

妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 $t$ 区，而自己在 $s$ 区。

该市有 $m$ 条大道连接 $n$ 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 $s$ 至 $t$ 的路线，使得经过道路的拥挤度最大值最小。

#### 输入格式
第一行四个数字 $n$，$m$，$s$，$t$。

接下来 $m$ 行，每行三个数字，分别表示两个区和拥挤度。

（有可能两个区之间有多条大道相连。)

#### 输出格式
输出题目要求的拥挤度。

#### 说明/提示
数据范围

对于 $30\%$ 的数据 $n\leq 10$。

对于 $60\%$ 的数据 $n\leq 100$。

对于 $100\%$ 的数据 $n\leq 10^4$，$m\leq 2n$，拥挤度$\leq 10^4$。

题目保证 $1\leq s,t\leq n$ 且 $s\neq t$，保证可以从 $s$ 区出发到 $t$ 区。

样例解释：

小明的妈妈要从 $1$ 号点去 $3$ 号点，最优路线为 $1$->$2$->$3$。

题目描述

“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动的热泪盈眶，开起了门……

妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 t 区，而自己在 s 区。

该市有 m 条大道连接 n 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 s 至 t 的路线，使得经过道路的拥挤度最大值最小。

输入格式

第一行四个数字 n，m，s，t。

接下来 m 行，每行三个数字，分别表示两个区和拥挤度。

（有可能两个区之间有多条大道相连。)

输出格式

输出题目要求的拥挤度。

说明/提示

数据范围

对于 30\% 的数据 n\leq 10。

对于 60\% 的数据 n\leq 100。

对于 100\% 的数据 n\leq 10^4，m\leq 2n，拥挤度\leq 10^4。

题目保证 1\leq s,t\leq n 且 s\neq t，保证可以从 s 区出发到 t 区。

样例解释：

小明的妈妈要从 1 号点去 3 号点，最优路线为 1->2->3。

by 2018一维 @ 2020-02-04 14:12:15

类型：题面修改题目：P4284 [SHOI2014]概率充电器

新题面:https://www.luogu.com.cn/paste/gdzx07pa

by LiuTianyou @ 2020-02-04 22:33:12

类型：试题提供

题目：未来程序·改

by LiuTianyou @ 2020-02-04 22:33:27

@chen_zhe

by chzhc @ 2020-02-05 11:23:27

@刘天佑您直接把loj的网址发过来，这不太好吧，题面数据什么的您要自己弄吧

by u2004 @ 2020-02-05 12:26:25

@刘天佑可能有版权问题吧

by Smile_Cindy @ 2020-02-05 21:37:36

P3806

正确的输入格式：

第一行两个数 n,m 。

接下来 n-1 条边 a,b,c 描述 a 到 b 有一条长度为 c 的边。

接下来 m 行每行询问一个 K。

by Smile_Cindy @ 2020-02-05 21:37:44

@chen_zhe