（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 ix35 @ 2020-02-12 11:37:12

类型：试题提供

题目：【模板】原根

by _Rainlzy @ 2020-02-12 12:19:59

类型：试题提供
题目：[CEOI2019]立方填词

by hanyuchen2019 @ 2020-02-12 12:31:34

@chen_zhe

类型：题面修改

P1897没有使用LATEX公式，请管理员修改题面，谢谢！

新题面：U105501

by hanyuchen2019 @ 2020-02-12 12:35:28

注：我已达到绿钩级别，但不方便验证

by _Rainlzy @ 2020-02-12 14:23:25

类型：试题提供
题目：[CEOI2012]工作规划

by _Rainlzy @ 2020-02-12 14:23:49

@chen_zhe vijos里的难题可以拿过来吗

by Aw顿顿 @ 2020-02-12 14:48:41

@chen_zhe

类型：题面修改

题目：P2841 A*B Problem

新题面效果：

题目描述

给出一个数 A ，你需要给出一个最小的数 B ，使得 A\times B 的结果只含有 0 和 1 。

输入格式

一个正整数 A ;

输出格式

正整数 B 和 A\times B 的结果，两数之间用一个空格隔开。

说明/提示

对于 30\% 的数据，0<N<20 ；

对于 50\% 的数据，0<N<100 ；

对于 70\% 的数据，0<N<1000 ；

对于 100\% 的数据，0<N<10000 ；


## 题目描述

给出一个数 $A$ ，你需要给出一个最小的数 $B$ ，使得 $A\times B$ 的结果只含有 $0$ 和 $1$ 。

## 输入格式

一个正整数 $A$ ;

## 输出格式

正整数 $B$ 和 $A\times B$ 的结果，两数之间用一个空格隔开。

## 说明/提示

对于 $30\%$ 的数据，$0<N<20$ ；

对于 $50\%$ 的数据，$0<N<100$ ；

对于 $70\%$ 的数据，$0<N<1000$ ；

对于 100\% 的数据，0<N<10000 ；

by Aw顿顿 @ 2020-02-12 15:16:01

类型：题面修改

@chen_zhe

题目：P4445 [AHOI2018初中组]报名签到

题目描述

## 输入格式第一行一个整数 $n$ ，表示报名签到的同学人数。第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个同学必须与其他同学保持的距离。 ## 输出格式输出一行，包括一个整数，表示这 $n$ 位同学排队队列的最小长度。注意： $n$ 位同学要按 $1$ 到 $n$ 的次序从前往后排队。 ## 说明/提示对于 $20\%$ 的数据满足：$1\le n\le 20$ ；对于 $70\%$ 的数据满足：$1\le n\le 10^4$ ；对于 $100\%$ 的数据满足：$1\le n\le 10^5$ ， $1\le a_i\le 100000$ 。 ~~~ ## 题目描述 $n$ 位同学（编号从 $1$ 到 $n$ ）同时来到体育馆报名签到，领取准考证和参赛资料。为了有序报名，这 $n$ 位同学需要按编号次序（编号为 $1$ 的同学站在最前面）从前往后排成一条直线。然而每一位同学都不喜欢拥挤，对于第 $i$ 位同学，如果有另外一位同学距离他/她的距离小于 $a_i$，那么就会发生冲突。小可可想知道如果要不发生任何冲突的情况下，这 $n$ 位同学排队的队列最短长度是多少。 ## 输入格式第一行一个整数 $n$ ，表示报名签到的同学人数。第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个同学必须与其他同学保持的距离。 ## 输出格式输出一行，包括一个整数，表示这 $n$ 位同学排队队列的最小长度。注意： $n$ 位同学要按 $1$ 到 $n$ 的次序从前往后排队。 ## 说明/提示对于 $20\%$ 的数据满足：$1\le n\le 20$ ；对于 $70\%$ 的数据满足：$1\le n\le 10^4$ ；对于 $100\%$ 的数据满足：$1\le n\le 10^5$ ， $1\le a_i\le 100000$ 。 ~~~

by mrsrz @ 2020-02-12 15:54:59

@M_sea @ix35_ @Fish_stack @Aw顿顿 @hanyuchen2019

以上处理完毕，感谢贡献

by Aw顿顿 @ 2020-02-12 16:26:19

类型：题面修改

@mrsrz

题目背景

蒟蒻HansBug在英语考场上，挠了无数次的头，可脑子里还是一片空白。

题目描述

眼下出现在HansBug蒟蒻面前的是一篇英语作文，然而智商捉急的HansBug已经草草写完了，此时他发现离考试结束还有 40 分钟，于是他打算估计一下这篇共有 M 个单词的英语作文的含金量如何。众所周知的是，在中高考英语作文中使用高级词汇可以有效提高文章的含金量，从而获得更好的分数。已知蒟蒻HansBug知道 N 个高级词汇，该词汇为 A_i（词汇长度为 L_i ，包含数字、大小写字母），该高级词汇的含金量为 B_i，则该高级词汇每出现一次便可增加 B_i 的含金量。可是他脑细胞和RP已经消耗殆尽，所以这个伟大的任务就交给你啦！

输入格式

第一行包含两个整数 N 和 P ， N 表示HansBug共知道的高级词汇个数， P 为模数

第 2-N+1行，每行包含一个单词 A_i （长度为Li）和一个整数 B_i ，其中 B_i(0<B_i\le 10^5) 表示该单词的含金量

接下来直到输入结束的若干行为一篇英语作文，其中包含共计 M 个单词，以及若干的分隔符（分隔符包含且仅包含,、.、!、?）

输出格式

一行，包含一个整数，为该文章的总含金量对 P 的模。

说明/提示

样例 1 中，共计出现了 2 次hansbug、 2 次absi2011 、 1 次 yyy 、 1 次kkksc03、 1 次 lzn ，所以总含金量为 1\times2+2\times4+3\times1+4\times1+100\times1=115，对 99 取模就是 16 。

样例 2 中，和样例 1 基本一样，值得注意的是整体的 yyyy 不可以被认为是 yyy 出现 2 次，请注意这是一篇英语作文，一切以单词为最小单位。

此题目中大小写敏感。

数据范围（设所有单词的最大长度为 Lmax ）：


## 题目背景
蒟蒻HansBug在英语考场上，挠了无数次的头，可脑子里还是一片空白。

## 题目描述
眼下出现在HansBug蒟蒻面前的是一篇英语作文，然而智商捉急的HansBug已经草草写完了，此时他发现离考试结束还有 $40$ 分钟，于是他打算估计一下这篇共有 $M$ 个单词的英语作文的含金量如何。众所周知的是，在中高考英语作文中使用高级词汇可以有效提高文章的含金量，从而获得更好的分数。已知蒟蒻HansBug知道 $N$ 个高级词汇，该词汇为 $A_i$（词汇长度为 $L_i$ ，包含数字、大小写字母），该高级词汇的含金量为 $B_i$，则该高级词汇每出现一次便可增加 $B_i$ 的含金量。可是他脑细胞和RP已经消耗殆尽，所以这个伟大的任务就交给你啦！

## 输入格式
第一行包含两个整数 $N$ 和 $P$ ， $N$ 表示HansBug共知道的高级词汇个数， $P$ 为模数

第 $2-N+1$行，每行包含一个单词 $A_i$ （长度为Li）和一个整数 $B_i$ ，其中 $B_i(0<B_i\le 10^5)$ 表示该单词的含金量

接下来直到输入结束的若干行为一篇英语作文，其中包含共计 $M$ 个单词，以及若干的分隔符（分隔符包含且仅包含`,`、`.`、`!`、`?`）

## 输出格式
一行，包含一个整数，为该文章的总含金量对 $P$ 的模。

## 说明/提示
样例 $1$ 中，共计出现了 $2$ 次`hansbug`、 $2$ 次`absi2011` 、 $1$ 次 `yyy` 、 $1$ 次`kkksc03`、 $1$ 次  `lzn` ，所以总含金量为 $1\times2+2\times4+3\times1+4\times1+100\times1=115$，对 $99$ 取模就是 $16$ 。

样例 $2$ 中，和样例 $1$ 基本一样，值得注意的是整体的 `yyyy` 不可以被认为是 `yyy` 出现 $2$ 次，请注意这是一篇英语作文，一切以单词为最小单位。

此题目中大小写敏感。

数据范围（设所有单词的最大长度为 $Lmax$ ）：