（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 _Rainlzy @ 2020-02-18 17:49:17

@♗Wendigo♝ 还没(看看究竟花落谁手)

by George1123 @ 2020-02-18 18:08:38

@Fish_stack 没事，你的上吧，蒟蒻不跟巨佬争（话说你也是抄LOJ题面的啊，你的数据是自己做的吗）

by Sai0511 @ 2020-02-19 00:46:15

类型：试题提供
题目：JSOI2009 有趣的游戏

by Thomas_ @ 2020-02-19 14:20:27

类型：题面修改题目：CF71A Way Too Long Words 新题面：题目描述

有时候，像“localization”或“internationalization”这样的词汇如此之长，以至于在一篇文章中多次写下这些词语令人厌烦。

让我们考虑一个词太长，如果它的长度严格超过 10 个字符。太长的单词应该用一个特殊的缩写代替。

这个缩写是这样写的：我们写下一个单词的第一个和最后一个字母，并在它们之间写出第一个和最后一个字母之间的字母数。该数字是十进制系统，不包含任何前导零。

因此，“localization”将拼写为“l10n”，而“internationalization”将拼写为”i18n”。

建议您使用缩写来自动更改单词的过程。因为所有太长的单词应该用缩写代替，不太长的单词不应该经历任何改变。输入输出格式输入格式：

第一行包含一个整数 n（ 1 \le n \le 100）。以下各项 n 行包含一个词。所有的单词由小写拉丁字母组成，并且拥有从 1 到 100 个字符的长度。

输出格式：

输出n 行。第 i 行应包含来自输入数据的第 i 个字替换的结果。

题目描述

有时候，像“localization”或“internationalization”这样的词汇如此之长，以至于在一篇文章中多次写下这些词语令人厌烦。

让我们考虑一个词太长，如果它的长度严格超过 $10$ 个字符。太长的单词应该用一个特殊的缩写代替。

这个缩写是这样写的：我们写下一个单词的第一个和最后一个字母，并在它们之间写出第一个和最后一个字母之间的字母数。该数字是十进制系统，不包含任何前导零。

因此，“localization”将拼写为“l10n”，而“internationalization”将拼写为”i18n”。

建议您使用缩写来自动更改单词的过程。因为所有太长的单词应该用缩写代替，不太长的单词不应该经历任何改变。 输入输出格式 输入格式：

第一行包含一个整数 $n$（ $1 \le n \le 1001 \le n \le 100$）。以下各项  $n$ 行包含一个词。所有的单词由小写拉丁字母组成， 并且拥有从 $1$ 到 $100$ 个字符的长度。 

输出格式：

输出$n$ 行。第 $i$ 行应包含来自输入数据的第 $i$ 个字替换的结果。

by Thomas_ @ 2020-02-19 14:21:41

类型：题面修改题目：CF1295A Display The Number 新题面：

输入 n

输出 n 个小木棍最多能摆放的数字最大是多少

小木棍摆放每个数字的方式如下图：

输入 $n$

输出 $n$ 个小木棍最多能摆放的数字最大是多少

小木棍摆放每个数字的方式如下图：
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1295A/f1bf3e3ee1e01404b7c2f218b7a8b65c071d6967.png)

by Rainy_chen @ 2020-02-19 15:00:33

@Thomas_ 这种明显的机翻风格的翻译就还是不要发了比较好吧（

by StudyingFather @ 2020-02-19 18:51:11

@connect

类型：试题提供

题目：JSOI2009 有趣的游戏

added & thanks.

by Sai0511 @ 2020-02-19 18:57:59

thx

by 业余门槛 @ 2020-02-19 20:27:07

类型：试题提供

题目： [Neerc2015]Distance on Triangulation

by Sai0511 @ 2020-02-20 09:48:46

类型：题面修改。
题目：P3232。

### 题目描述
一个无向连通图，顶点从 $1$ 编号到 $n$，边从 $1$ 编号到 $m$。  
小 Z 在该图上进行随机游走，初始时小 Z 在 $1$ 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。   
当小 Z 到达 $n$ 号顶点时游走结束，总分为所有获得的分数之和。   
现在，请你对这 $m$ 条边进行编号，使得小 Z 获得的总分的期望值最小。 
### 输入格式  
第一行是正整数 $n$ 和 $m$，分别表示该图的顶点数和边数。  
接下来 $m$ 行每行是两个整数 $u,v(1 \leq u,v \leq n)$，表示顶点 $u$ 与顶点 $v$ 之间存在一条边。 
### 输出格式
仅包含一个实数，表示最小的期望值，保留 $3$ 位小数。  
### 说明/提示   
对于 $30 \%$ 的数据，满足 $n \leq 10$。   
对于 $100 \%$ 的数据，满足 $2 \leq n \leq 500$。   
且图是一个无向联通图。    

------------
边$(1,2)$编号为 $1$，边$(1,3)$编号为 $2$，边$(2,3)$编号为 $3$。

题目描述

一个无向连通图，顶点从 1 编号到 n，边从 1 编号到 m。
小 Z 在该图上进行随机游走，初始时小 Z 在 1 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。
当小 Z 到达 n 号顶点时游走结束，总分为所有获得的分数之和。
现在，请你对这 m 条边进行编号，使得小 Z 获得的总分的期望值最小。

输入格式

第一行是正整数 n 和 m，分别表示该图的顶点数和边数。
接下来 m 行每行是两个整数 u,v(1 \leq u,v \leq n)，表示顶点 u 与顶点 v 之间存在一条边。

输出格式

仅包含一个实数，表示最小的期望值，保留 3 位小数。

说明/提示

对于 30 \% 的数据，满足 n \leq 10。
对于 100 \% 的数据，满足 2 \leq n \leq 500。
且图是一个无向联通图。

边(1,2)编号为 1，边(1,3)编号为 2，边(2,3)编号为 3。