（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-01-23 13:27:51

@xht37 那请问一下题面是符合规范的吗？

by cmll02 @ 2020-01-23 17:14:59

类型：题面修改

题目：P2835 刻录光盘

新题面：

### 题目描述
在 JSOI2005 夏令营快要结束的时候，很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家，以便大家回去后继续学习。组委会觉得这个主意不错！可是组委会一时没有足够的空光盘，没法保证每个人都能拿到刻录上资料的光盘，又来不及去买了，怎么办呢？！

组委会把这个难题交给了 LHC，LHC 分析了一下所有营员的地域关系，发现有些营员是一个城市的，其实他们只需要一张就可以了，因为一个人拿到光盘后，其他人可以带着U盘之类的东西去拷贝啊！

可是，LHC 调查后发现，由于种种原因，有些营员并不是那么的合作，他们愿意某一些人到他那儿拷贝资料，当然也可能不愿意让另外一些人到他那儿拷贝资料，这与我们 JSOI 宣扬的团队合作精神格格不入！！！

现在假设总共有 $N$ 个营员 $(2\le N \le 200)$，营员的编号为 $1,2,\cdots,N$。LHC 给每个人发了一张调查表，让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然，如果 $A$ 愿意把资料拷贝给 $B$，而 $B$ 又愿意把资料拷贝给 $C$，则一旦 $A$ 获得了资料，则 $B,C$ 都会获得资料。

现在，请你编写一个程序，根据回收上来的调查表，帮助 LHC 计算出组委会至少要刻录多少张光盘，才能保证所有营员回去后都能得到夏令营资料？

### 输入格式
第一行是一个数 $N$。

接下来的 $N$ 行，分别表示各个营员愿意把自己获得的资料拷贝给其他哪些营员。即输入数据的第 $i+1$ 行表示第 $i$ 个营员愿意把资料拷贝给那些营员的编号，以一个 $0$ 结束。如果一个营员不愿意拷贝资料给任何人，则相应的行只有一个 $0$，一行中的若干数之间用一个空格隔开。

### 输出格式
一个正整数，表示最少要刻录的光盘数。

by Smile_Cindy @ 2020-01-24 11:26:15

类型：题面修改

[ZJOI2010]排列计数

鉴于题面太长就不发了，将题目中的式子改为

P_i>P_{\lfloor\frac{i}{2}\rfloor}

by Smile_Cindy @ 2020-01-24 11:28:44

原帖

by Froggy @ 2020-01-24 13:00:47

@xht37

线段树分裂

您看看星不星QAQ

by ShineEternal @ 2020-01-24 13:40:11

@Froggy 窝觉得海星，但是请不要@管理员qwq

by ShineEternal @ 2020-01-24 13:40:46

~~@Froggy 不过如果您每次都提供高质量题目@几下也没啥事~~

by cmll02 @ 2020-01-24 14:13:31

类型：题面修改

题目：P1955 [NOI2015]程序自动分析

新题面：

### 题目描述
在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设$x_1,x_2,x_3,\cdots$ 代表程序中出现的变量，给定 $n$ 个形如 $x_i=x_j$ 或 $x_i\neq x_j$ 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：$x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1$，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

### 输入格式
输入的第一行包含一个正整数 $t$，表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题，包含若干行：

第一行包含一个正整数 $n$，表示该问题中需要被满足的约束条件个数。接下来 $n$ 行，每行包括三个整数 $i,j,e$，描述一个相等/不等的约束条件，相邻整数之间用单个空格隔开。若 $e=1$，则该约束条件为 $x_i=x_j$；若$e=0$，则该约束条件为 $x_i\neq x_j$；

### 输出格式

输出包括 $t$ 行。

输出文件的第 $k$ 行输出一个字符串 `YES` 或者 `NO`（字母全部大写），`YES` 表示输入中的第 $k$ 个问题判定为可以被满足，`NO` 表示不可被满足。

### 说明/提示

【样例解释1】

在第一个问题中，约束条件为：$x_1=x_2,x_1\neq x_2$。这两个约束条件互相矛盾，因此不可被同时满足。

在第二个问题中，约束条件为：$x_1=x_2,x_1 = x_2$。这两个约束条件是等价的，可以被同时满足。

【样例说明2】

在第一个问题中，约束条件有三个：$x_1=x_2,x_2= x_3,x_3=x_1$。只需赋值使得 $x_1=x_2=x_3$，即可同时满足所有的约束条件。

在第二个问题中，约束条件有四个：$x_1=x_2,x_2= x_3,x_3=x_4,x_4\neq x_1$。由前三个约束条件可以推出 $x_1=x_2=x_3=x_4$，然而最后一个约束条件却要求 $x_1\neq x_4$，因此不可被满足。

【数据范围】

![](https://cdn.luogu.com.cn/upload/pic/1503.png)

注：实际上 $n\le 10^6$ 

【时限 $2$ s，内存 $512$ M】

by syksykCCC @ 2020-01-25 18:57:31

题面修改：https://www.luogu.com.cn/problem/P2455

## 题目描述

已知 $n$ 元线性一次方程组。

$\large \begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases}$

请根据输入的数据，编程输出方程组的解的情况。

## 输入格式

第一行一个正整数 $n$，表示未知数的个数。

接下来 $n$ 行，每行 $n + 1$ 个整数。第 $i$ 行的前 $n$ 个数分别表示 $a_{i-1, 1}, a_{i-1, 2} \cdots a_{i-1, n}$，最后一个数表示 $b_i$。

## 输出格式

如果方程组无实数解输出 $-1$。

如果有无穷多实数解，输出 $0$。

如果有唯一解，则输出解（若不为 $0$，则小数点后保留两位小数，否则直接输出 $0$）。解的输出形式为 `xi=...`，具体可以看样例来理解。

## 说明/提示

对于 $100\%$ 的数据，$1 \le n \le 50$。对于 $\forall 1\le i, j \le n$，有 $|a_{i, j}| \le 100$，$|b_i| \le 300$。

题目描述

已知 n 元线性一次方程组。

\large \begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases}

请根据输入的数据，编程输出方程组的解的情况。

输入格式

第一行一个正整数 n，表示未知数的个数。

接下来 n 行，每行 n + 1 个整数。第 i 行的前 n 个数分别表示 a_{i-1, 1}, a_{i-1, 2} \cdots a_{i-1, n}，最后一个数表示 b_i。

输出格式

如果方程组无实数解输出 -1。

如果有无穷多实数解，输出 0。

如果有唯一解，则输出解（若不为 0，则小数点后保留两位小数，否则直接输出 0）。解的输出形式为 xi=...，具体可以看样例来理解。

说明/提示

对于 100\% 的数据，1 \le n \le 50。对于 \forall 1\le i, j \le n，有 |a_{i, j}| \le 100，|b_i| \le 300。

by NaCly_Fish @ 2020-01-25 23:36:09

@Froggy 放进主题库了，但是题面不太符合规范的，我已经改了。