（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 Priori_Incantatem @ 2020-02-20 10:46:29

类型：添加标签

P2234 [HNOI2002]营业额统计

建议添加 平衡树 与 Treap 的标签

by _Rainlzy @ 2020-02-20 13:36:35

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

### 题目描述
给定一个长度是 $n$ 的数列 $A$，我们称一个数列是完美的，当且仅当对于其任意连续子序列的和都是正的。现在你有一个操作可以改变数列，选择一个区间 $X,Y$ 满足 $A_x+A_x+1+...+ A_Y < 0,1 < X \le Y < n$，令 $S=A_x +A_x+1 +...+ A_Y$，对于 $A_x-1$ 和 $A_Y+1$ 分别加上 $S$，$A_x$和 $A_Y$ 分别减去$ S$ （如果 $X=Y$ 就减两次）。问最少几次这样的操作使得最终数列是完美的。
### 输入格式
第一行一个数 $n$。             
接下来 $n$ 个数，$A_i$。
### 输出格式
一个数表示最少的操作次数，如果无解输出`-1`
### 说明/提示   
【样例解释】              
首先选择区间[$2,4$],之后数列变成 $1,9$，$-4,7,50$，然后选择[$3,3$]，数列变成$1,5,4,3,50$。
【数据范围】           
对于 $20\%$ 的数据，满足 $1 \le N \le 5$;

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$; $1 \le |A_i|≤2^{31}-1$ 。

题目描述

给定一个长度是 n 的数列 A，我们称一个数列是完美的，当且仅当对于其任意连续子序列的和都是正的。现在你有一个操作可以改变数列，选择一个区间 X,Y 满足 A_x+A_x+1+...+ A_Y < 0,1 < X \le Y < n，令 S=A_x +A_x+1 +...+ A_Y，对于 A_x-1 和 A_Y+1 分别加上 S，A_x和 A_Y 分别减去 S （如果 X=Y 就减两次）。问最少几次这样的操作使得最终数列是完美的。

输入格式

第一行一个数 n。
接下来 n 个数，A_i。

输出格式

一个数表示最少的操作次数，如果无解输出-1

说明/提示

【样例解释】
首先选择区间[2,4],之后数列变成 1,9，-4,7,50，然后选择[3,3]，数列变成1,5,4,3,50。 【数据范围】
对于 20\% 的数据，满足 1 \le N \le 5;

对于 100\% 的数据，满足 1 \le N \le 10^5; 1 \le |A_i|≤2^{31}-1 。

by u2004 @ 2020-02-20 21:02:32

@devout 我觉得 \text{lrj} 出的题还是等会再传吧......

by YosemiteHe @ 2020-02-21 10:31:26

类型：题面修改。

题目：P1234 小A的口头禅。

### 题目描述
小A最近有了一个口头禅“呵呵”，于是他给出了一个矩形，让你求出里面有几个 `hehe`（方向无所谓）。
### 输入格式
第一行两个数 $n,m$，表示这个矩形的大小。

以下 $n$ 行，每行 $m$ 的字符，表示这个矩形。
### 输出格式
一行一个数，表示有几个 `hehe`。
### 说明/提示
对于 $100\%$ 的数据，$1 \leq n,m \leq 1000$。

有 $1$ 个点就是样例！

题目描述

小A最近有了一个口头禅“呵呵”，于是他给出了一个矩形，让你求出里面有几个 hehe（方向无所谓）。

输入格式

第一行两个数 n,m，表示这个矩形的大小。

以下 n 行，每行 m 的字符，表示这个矩形。

输出格式

一行一个数，表示有几个 hehe。

说明/提示

对于 100\% 的数据，1 \leq n,m \leq 1000。

有 1 个点就是样例！

by cnyzz @ 2020-02-21 13:21:49

类型：题面修改

题目：[NOI2016]网格

将详细数据范围改成表格：

n,m 测试点 c
n*m\leq 4 1 c\leq n*m
n*m\leq 8 2 c\leq n*m
n*m\leq 15 3 c\leq n*m
n*m\leq 30 4 c\leq n*m
n*m\leq 100 5 c\leq n*m
n*m\leq 300 6 c\leq n*m
n*m\leq 10^3 7 c\leq n*m
n*m\leq 2\times 10^4 8 c\leq 5
n*m\leq 2\times 10^4 9 c\leq 15
n*m\leq 2\times 10^4 10 c\leq 30
n,m\leq 2\times 10^4,n*m\leq2\times 10^4 11 \sum c\leq 2\times 10^4
n,m\leq 2\times 10^4,n*m\leq10^5 12 \sum c\leq 2\times 10^4
n,m\leq 2\times 10^4,n*m\leq3\times 10^5 13 \sum c\leq 2\times 10^4
n,m\leq 2\times 10^4,n*m\leq10^6 14 \sum c\leq 2\times 10^4
n,m\leq 2\times 10^4,n*m\leq 10^9 15 \sum c\leq 2\times 10^4
n,m\leq 10^5 16 \sum c\leq 10^5
n,m\leq 10^9 17 c=0
n,m\leq 10^9 18 c\leq 1
n,m\leq 10^9 19 c\leq 2
n,m\leq 10^9 20 c\leq 3
n,m\leq 10^9 21 c\leq 10
n,m\leq 10^9 22 c\leq 30
n,m\leq 10^9 23 c\leq 300
n,m\leq 10^9 24 \sum c\leq 2 \times 10^4
n,m\leq 10^9 25 \sum c\leq 10^5 
| $n,m$ | 测试点 | $c$ |
| :----------: | :----------: | :----------: |
| $n*m\leq 4$ | $1$ | $c\leq n*m$ |
| $n*m\leq 8$ | $2$ | $c\leq n*m$ |
| $n*m\leq 15$ | $3$ | $c\leq n*m$ |
| $n*m\leq 30$ |  $4$| $c\leq n*m$ |
| $n*m\leq 100$ | $5$ | $c\leq n*m$ |
| $n*m\leq 300$ | $6$ | $c\leq n*m$ |
| $n*m\leq 10^3$ | $7$ | $c\leq n*m$ |
| $n*m\leq 2\times 10^4$ | $8$ | $c\leq 5$ |
| $n*m\leq 2\times 10^4$ | $9$ | $c\leq 15$ |
| $n*m\leq 2\times 10^4$ | $10$ | $c\leq 30$ |
| $n,m\leq 2\times 10^4,n*m\leq2\times 10^4$ | $11$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 2\times 10^4,n*m\leq10^5$  | $12$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 2\times 10^4,n*m\leq3\times 10^5$ | $13$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 2\times 10^4,n*m\leq10^6$ | $14$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 2\times 10^4,n*m\leq 10^9$ | $15$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 10^5$ | $16$ | $\sum c\leq 10^5$ |
| $n,m\leq 10^9$ | $17$ | $c=0$ |
| $n,m\leq 10^9$ | $18$ | $c\leq 1$ |
| $n,m\leq 10^9$ | $19$ | $c\leq 2$ |
| $n,m\leq 10^9$ | $20$ | $c\leq 3$ |
| $n,m\leq 10^9$ | $21$ | $c\leq 10$ |
| $n,m\leq 10^9$ | $22$ | $c\leq 30$ |
| $n,m\leq 10^9$ | $23$ | $c\leq 300$ |
| $n,m\leq 10^9$ | $24$ | $\sum c\leq 2 \times 10^4$ |
| $n,m\leq 10^9$ | $25$ | $\sum c\leq   10^5$ |

by cnyzz @ 2020-02-21 13:58:09

类型：题面修改。

题目：[NOI2013]向量内积

将详细数据范围改成表格：

测试点编号 n d k x_{i,j}
1 2 20 2 \leq 10
2 5 20 2 \leq 10
3 10 20 3 \leq 10
4 20 20 2 \leq 100
5 50 20 3 \leq 100
6 50 50 2 \leq 10^3
7 50 50 3 \leq 3\times 10^6
8 80 80 2 \leq 2\times 10^6
9 100 100 3 \leq 3\times 10^6
10 500 100 3 \leq 3\times 10^6
11 10^3 100 2 \leq 2\times 10^6
12 10^3 100 3 \leq 3\times 10^6
13 10^4 100 2 <10
14 10^4 100 3 <10
15 1.5\times 10^4 100 2 <10
16 1.8\times 10^4 100 2 <10
17 2\times 10^4 100 2 <10
18 5\times 10^4 30 3 <10
19 8\times 10^4 30 3 <10
20 10^5 30 3 <10 
| 测试点编号 | $n$ | $d$ | $k$ | $x_{i,j}$ |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $2$ | $20$ | $2$ | $\leq 10$ |
| $2$ | $5$ | $20$ | $2$ | $\leq 10$ |
| $3$ | $10$ | $20$ | $3$ | $\leq 10$ |
| $4$ | $20$ | $20$ | $2$ | $\leq 100$ |
| $5$ | $50$ | $20$ | $3$ | $\leq 100$ |
| $6$ | $50$ | $50$ | $2$ | $\leq 10^3$ |
| $7$ | $50$ | $50$ | $3$ | $\leq 3\times 10^6 $ |
| $8$ | $80$ | $80$ | $2$ | $\leq 2\times 10^6 $ |
| $9$ | $100$ | $100$ | $3$ | $\leq 3\times 10^6 $ |
| $10$ | $500$ | $100$ | $3$ | $\leq 3\times 10^6$ |
| $11$ | $10^3$ | $100$ | $2$ | $\leq 2\times 10^6$ |
| $12$ | $10^3$ | $100$ | $3$ | $\leq 3\times 10^6$ |
| $13$ | $10^4$ | $100$ | $2$ | $<10$ |
| $14$ | $10^4$ | $100$ | $3$ | $<10$ |
| $15$ | $1.5\times 10^4$ | $100$ | $2$ | $<10$ |
| $16$ | $1.8\times 10^4$ | $100$ | $2$ | $<10$ |
| $17$ | $2\times 10^4$ | $100$ | $2$ | $<10$ |
| $18$ | $5\times 10^4$ | $30$ | $3$ | $<10$ |
| $19$ | $8\times 10^4$ | $30$ | $3$ | $<10$ |
| $20$ | $10^5$ | $30$ | $3$ | $<10$ |

by cnyzz @ 2020-02-21 15:09:49

题面修改

[NOI2016]循环之美

将图片修改为文字：

对于所有的测试点，保证 $1\leq n\leq 10^9,1\leq m \leq 10^9,2\leq k \leq 2\times 10^3 $。

对于每个测试点，有以下约束（其中留空的表示没有特殊的约束）：
| 测试点编号 | $n$ | $m$ | $k$ |
| :-----------: | :-----------: | :-----------: | :-----------: |
| $1$ | $\leq 10$ | $\leq 20$ | $=2$ |
| $2$ | $\leq 100$ | $\leq 10^4$ | $=2$ |
| $3$ | $\leq 10^3$ |  | $=2$ |
| $4$ | $\leq 10^4$ |  | $=2$ |
| $5$ | $\leq 10$ | $\leq 20$ | $=3$ |
| $6$ | $\leq 100$ | $\leq 10^4$ | $=3$ |
| $7$ | $\leq 10^3$ |  | $=3$ |
| $8$ | $\leq 10^4$ |  | $=3$ |
| $9$ | $\leq 10$ | $\leq 20$ | $\leq 100$ |
| $10$ | $\leq 100$ | $\leq 10^4$ | $\leq 100$ |
| $11$ | $\leq 10^3$ |  | $\leq 10^3$ |
| $12$ | $\leq 10^4$ |  |  |
| $13$ | $\leq 10^5$ | $\leq 10^8$ | $\leq 100$ |
| $14$ | $\leq 2\times 10^5$ |  | $\leq 10^3$ |
| $15$ | $\leq 5\times10^5$ |  |  |
| $16$ | $\leq 10^6$ | $\leq 10^8$ | $\leq 100$ |
| $17$ | $\leq 2\times 10^6$ |  | $\leq 10^3$ |
| $18$ | $\leq 5\times 10^6$ |  |  |
| $19$ | $\leq 10^7$ | $\leq 10^8$ | $100$ |
| $20$ | $\leq 2\times10^7$ |  | $\leq 10^3$ |
| $21$ | $\leq 2\times10^7$ |  |  |
| $22$ | $\leq 10^8$ | $\leq 10^8$ |  |
| $23$ | $\leq 10^8$ | $\leq 10^8$ |  |
| $24,25$    |  |  |

对于所有的测试点，保证 1\leq n\leq 10^9,1\leq m \leq 10^9,2\leq k \leq 2\times 10^3 。

对于每个测试点，有以下约束（其中留空的表示没有特殊的约束）： 测试点编号 n m k
1 \leq 10 \leq 20 =2
2 \leq 100 \leq 10^4 =2
3 \leq 10^3 =2
4 \leq 10^4 =2
5 \leq 10 \leq 20 =3
6 \leq 100 \leq 10^4 =3
7 \leq 10^3 =3
8 \leq 10^4 =3
9 \leq 10 \leq 20 \leq 100
10 \leq 100 \leq 10^4 \leq 100
11 \leq 10^3 \leq 10^3
12 \leq 10^4
13 \leq 10^5 \leq 10^8 \leq 100
14 \leq 2\times 10^5 \leq 10^3
15 \leq 5\times10^5
16 \leq 10^6 \leq 10^8 \leq 100
17 \leq 2\times 10^6 \leq 10^3
18 \leq 5\times 10^6
19 \leq 10^7 \leq 10^8 100
20 \leq 2\times10^7 \leq 10^3
21 \leq 2\times10^7
22 \leq 10^8 \leq 10^8
23 \leq 10^8 \leq 10^8
24,25

by cnyzz @ 2020-02-21 15:11:11

对于所有的测试点，保证 1\leq n\leq 10^9,1\leq m \leq 10^9,2\leq k \leq 2\times 10^3 。

对于每个测试点，有以下约束（其中留空的表示没有特殊的约束）：

测试点编号 n m k
1 \leq 10 \leq 20 =2
2 \leq 100 \leq 10^4 =2
3 \leq 10^3 =2
4 \leq 10^4 =2
5 \leq 10 \leq 20 =3
6 \leq 100 \leq 10^4 =3
7 \leq 10^3 =3
8 \leq 10^4 =3
9 \leq 10 \leq 20 \leq 100
10 \leq 100 \leq 10^4 \leq 100
11 \leq 10^3 \leq 10^3
12 \leq 10^4
13 \leq 10^5 \leq 10^8 \leq 100
14 \leq 2\times 10^5 \leq 10^3
15 \leq 5\times10^5
16 \leq 10^6 \leq 10^8 \leq 100
17 \leq 2\times 10^6 \leq 10^3
18 \leq 5\times 10^6
19 \leq 10^7 \leq 10^8 100
20 \leq 2\times10^7 \leq 10^3
21 \leq 2\times10^7
22 \leq 10^8 \leq 10^8
23 \leq 10^8 \leq 10^8
24,25

抱歉锅掉了。

对于所有的测试点，保证 $1\leq n\leq 10^9,1\leq m \leq 10^9,2\leq k \leq 2\times 10^3 $。

对于每个测试点，有以下约束（其中留空的表示没有特殊的约束）：

| 测试点编号 | $n$ | $m$ | $k$ |
| :-----------: | :-----------: | :-----------: | :-----------: |
| $1$ | $\leq 10$ | $\leq 20$ | $=2$ |
| $2$ | $\leq 100$ | $\leq 10^4$ | $=2$ |
| $3$ | $\leq 10^3$ |  | $=2$ |
| $4$ | $\leq 10^4$ |  | $=2$ |
| $5$ | $\leq 10$ | $\leq 20$ | $=3$ |
| $6$ | $\leq 100$ | $\leq 10^4$ | $=3$ |
| $7$ | $\leq 10^3$ |  | $=3$ |
| $8$ | $\leq 10^4$ |  | $=3$ |
| $9$ | $\leq 10$ | $\leq 20$ | $\leq 100$ |
| $10$ | $\leq 100$ | $\leq 10^4$ | $\leq 100$ |
| $11$ | $\leq 10^3$ |  | $\leq 10^3$ |
| $12$ | $\leq 10^4$ |  |  |
| $13$ | $\leq 10^5$ | $\leq 10^8$ | $\leq 100$ |
| $14$ | $\leq 2\times 10^5$ |  | $\leq 10^3$ |
| $15$ | $\leq 5\times10^5$ |  |  |
| $16$ | $\leq 10^6$ | $\leq 10^8$ | $\leq 100$ |
| $17$ | $\leq 2\times 10^6$ |  | $\leq 10^3$ |
| $18$ | $\leq 5\times 10^6$ |  |  |
| $19$ | $\leq 10^7$ | $\leq 10^8$ | $100$ |
| $20$ | $\leq 2\times10^7$ |  | $\leq 10^3$ |
| $21$ | $\leq 2\times10^7$ |  |  |
| $22$ | $\leq 10^8$ | $\leq 10^8$ |  |
| $23$ | $\leq 10^8$ | $\leq 10^8$ |  |
| $24,25$    |  |  |

by Ynoi @ 2020-02-21 19:17:01

https://www.luogu.com.cn/problem/U84618

Floyd最小环qaq

by Aw顿顿 @ 2020-02-22 16:19:57

类型：题面修改

题目：CF886A ACM ICPC

将翻译改为：

有 6 个整数 a1,a2,a3,a4,a5,a6 (a_i\leq 10^3) 。现在希望你把这 6 个整数分成和相等的 2 组。若能，输出 YES ，反之输出 NO 。输出无需考虑大小写。

有 $6$ 个整数 $a1,a2,a3,a4,a5,a6$ $(a_i\leq 10^3)$ 。现在希望你把这 $6$ 个整数分成和相等的 $2$ 组。若能，输出 `YES` ，反之输出 `NO` 。输出无需考虑大小写。
上一页 | 下一页