（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 cmll02 @ 2020-01-21 12:57:00

类型：题面修改

题目：P1290 欧几里得的游戏

新题面：

**题目描述**
欧几里德的两个后代Stan和Ollie正在玩一种数字游戏，这个游戏是他们的祖先欧几里德发明的。给定两个正整数 $M$ 和 $N$，从Stan开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于 $0$。然后是Ollie，对刚才得到的数，和 $M,N$ 中较小的那个数，再进行同样的操作……直到一个人得到了 $0$，他就取得了胜利。下面是他们用 $(25,7)$ 两个数游戏的过程：

Start：$(25,7)$

Stan：$(11,7)$

Ollie：$(4,7)$

Stan：$(4,3)$

Ollie：$(1,3)$

Stan：$(1,0)$

Stan赢得了游戏的胜利。

现在，假设他们完美地操作，谁会取得胜利呢？

**输入格式**

**本题有多组测试数据。**

第一行为测试数据的组数 $C$。
下面 $C$ 行，每行为一组数据，包含两个正整数 $M,N(M,N<2^{31})$。

**输出格式**

对每组输入数据输出一行，如果Stan胜利，则输出 `Stan wins`；否则输出 `Ollie wins`。

by ShineEternal @ 2020-01-21 13:36:04

@青行灯 如果是模板请注明，不是请带走题目orz

by 破壁人5th @ 2020-01-21 14:36:07

类型：题面修改

题目：P4149 [IOI2011]Race

~~原数据范围不完整，应改为： \sout{1\leq n\leq 2\times10^5}，\sout{1\leq K,l_i\leq 10^6}，

~~（其中部分变量还在输入格式中未说明，一并附在下方）~~ 不够规范的细节有点多，直接将修改过的整个题面放上来算了 ```plain ## 题目描述 给一棵树，每条边有权。求一条简单路径，权值和等于 $k$，且边的数量最小。 ## 输入格式 第一行包含两个整数 $n,k$，表示树的大小与要求找到的路径的边权和。 接下来 $n-1$ 行，每行三个整数 $u_i,v_i,l_i$，代表有一条连接 $u_i$ 与 $v_i$，边权为 $w_i$ 的无向边。**点从 $0$ 开始编号**。 ## 输出格式 输出一个整数，表示最小边数量。 如果不存在这样的路径，输出 `-1`。 ## 说明/提示 保证 $1\leq n\leq 2\times10^5$，$1\leq k,l_i\leq 10^6$，$0\leq u_i,v_i<n$。 ```

by HohleFeuerwerke @ 2020-01-21 15:31:20

类型：试题提供

题目：[BOI2005] Card 卡牌游戏

by HohleFeuerwerke @ 2020-01-21 15:40:07

这个贴没人管了吗？

by haiwenhan @ 2020-01-21 15:55:27

类型：试题提供（模板题提供）

题目：【模板】动态开点线段树

自己出的模板题，BDFZ里的教练和同学都验了题，数据完全没有问题。动态开点线段树，你值得拥有。

希望收下（QwQ）

by cmll02 @ 2020-01-21 16:14:35

类型：题面修改

题目：P2341 【模板】强连通分量 / [HAOI2006]受欢迎的牛

新题面：

**题目背景**

本题测试数据已修复。

**题目描述**

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 $A$ 喜欢 $B$，$B$ 喜欢 $C$，那么 $A$ 也喜欢 $C$。牛栏里共有 $N$ 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

**输入格式**

第一行：两个用空格分开的整数：$N$ 和 $M$。

第二行到第 $M + 1$ 行：每行两个用空格分开的整数：$A$ 和 $B$，表示 $A$ 喜欢 $B$。

**输出格式**

一行单独一个整数，表示明星奶牛的数量。

**说明/提示**

只有 $3$ 号奶牛可以做明星。

【数据范围】

对于 $10\%$ 的数据，$N\le20, M\le50$。

对于 $30\%$的数据,$N\le1000,M\le20000$。

对于 $70\%$的数据,$N\le5000,M\le50000$。

对于 $100\%$的数据,$N\le10000,M\le50000$。

by cmll02 @ 2020-01-21 16:15:59

@wwqk4444

by cmll02 @ 2020-01-21 16:22:45

类型：题面修改

题目：P1296 奶牛的耳语

新题面：

**题目描述**

在你的养牛场，所有的奶牛都养在一排呈直线的牛栏中。一共有 $n$ 头奶牛，其中第 $i$ 头牛在直线上所处的位置可以用一个整数坐标 $p_i(0\le p_i \le 10^8)$ 来表示。在无聊的日子里，奶牛们常常在自己的牛栏里与其它奶牛交流一些八卦新闻。每头奶牛发出的声音响度是一样的，而由于声波的能量衰减，某头奶牛发出的声音只能被与它距离不超过 $d(0 \le d \le 10^4)$ 的奶牛所听到，这样这对奶牛就称为可以相互交流的。现在给出所有奶牛的位置和声音所能传播的最远距离 $d$ ，请你编个程序来计算你的养牛场里究竟有多少对可以相互交流的奶牛。

**输入格式**

第一行包含两个整数 $n,d$。

第二行包含 $n$ 个整数，每个整数都是一个坐标 $p_i$，描述一头奶牛在直线上的位置。

**输出格式**

一个数，表示养牛场中可以相互交流奶牛的对数。

**说明/提示**

数据规模

对于 $40\%$ 的数据，$n\le10^3$。

对于 $100\%$ 的数据，$n\le 10^6$。

by cmll02 @ 2020-01-21 16:25:57

类型：题面修改

题目：P2197 【模板】nim游戏

新题面：

**题目描述**

甲，乙两个人玩Nim取石子游戏。

Nim游戏的规则是这样的：地上有 $n$ 堆石子（每堆石子数量小于 $10000$），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 $n$ 堆石子的数量，他想知道是否存在先手必胜的策略。

**输入格式**

**本题有多组测试数据。**

第一行一个整数 $T(T\le10)$，表示有 $T$ 组数据

接下来每两行是一组数据，第一行一个整数 $n$，表示有 $n$ 堆石子，$n\le10000$。

第二行有 $n$ 个数，表示每一堆石子的数量.

**输出格式**

共 $T$ 行，如果对于这组数据存在先手必胜策略则输出 `Yes`,否则输出 `No`，每个单词一行。
上一页 | 下一页