（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 Itst @ 2020-01-31 20:38:07

@Karry5307 本贴禁止无意义回复/

by NaCly_Fish @ 2020-01-31 22:21:27

@Itst 感谢您的贡献

by 5ab_juruo @ 2020-02-01 10:13:53

不好意思，有一点错误。

类型：题面修改

题目：[P1776 宝物筛选]

终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物……这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了……小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为W的采集车，洞穴里总共有 $n$ 种宝物，每种宝物的价值为 $v_i$，重量为 $w_i$，每种宝物有 $m_i$ 件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

第一行为一个整数 $n$ 和 $W$，分别表示宝物种数和采集车的最大载重。

接下来 $n$ 行每行三个整数 $v_i,w_i,m_i$。

输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。

对于$30\%$的数据：$n\leq \Sigma m_i\leq 10^4$；$0\le W\leq 10^3$。

对于$100\%$的数据：$n\leq \Sigma m_i \leq 10^5$；$0\le W\leq 4\times 10^4$；$1\leq n\le 100$。

by mrsrz @ 2020-02-01 10:18:49

@不刷题的5ab added&thanks

by StudyingFather @ 2020-02-01 10:19:17

@不刷题的5ab 感谢您的贡献。

by 霍士弘 @ 2020-02-01 10:32:24

类型：题面修改
题目：P2032 扫描
新题面：

## 题目描述  
有一个 $1 \times n$ 的矩阵，有 $n$ 个整数。  
现在给你一个可以盖住连续 $k$ 个数的木板。  
一开始木板盖住了矩阵的第 $1 \sim k$ 个数，每次将木板向右移动一个单位，直到右端与第 $n$ 个数重合。
每次移动前输出被覆盖住的数字中最大的数是多少。
## 输入格式
第一行两个数，$n,k$ 表示共有 $n$ 个数，木板可以盖住 $k$ 个数。  
第二行 $n$ 个数，表示矩阵中的元素。  
## 输出格式
共 $n - k + 1$ 行，每行一个整数。
第 $i$ 行表示第 $i \sim i + k - 1$ 个数中最大值是多少。  
## 说明/提示
对于 $20\%$ 的数据，$1 \leq k \leq n \leq 10^3$。  
对于 $50\%$ 的数据，$1 \leq k \leq n \leq 10^4$。  
对于 $100\%$ 的数据，$1 \leq k \leq n \leq 2 \times 10^6$，矩阵中的元素大小不超过 $10^4$ 并且均为正整数。

by Meatherm @ 2020-02-01 11:49:22

类型：题面修改
题目：P4178 Tree
新题面：

给你一棵树，每条边带权，问有多少对点它们的距离 \leq k。

第一行一个整数 n。

接下来 n-1 行，每行三个整数 u_i,v_i,w_i，表示存在一条连接 u_i 和 v_i 的边，长度是 w_i。

接下来一行一个整数 k。

输出一行一个非负整数，表示点对的数量。注意：点对是无序的，(u,v) 和 (v,u) 算作同一条路径，一个点不算一条路径。

对于 100\% 的数据，1\leq n \leq4 ·10^4，1\leq w_i\leq 1000。

by Meatherm @ 2020-02-01 11:49:49

草没括起来

by Meatherm @ 2020-02-01 11:51:37

给你一棵树，每条边带权，问有多少对点它们的距离 $\leq k$。

第一行一个整数 $n$。

接下来 $n-1$ 行，每行三个整数 $u_i,v_i,w_i$，表示存在一条连接 $u_i$ 和 $v_i$ 的边，长度是 $w_i$。

接下来一行一个整数 $k$。

输出一行一个非负整数，表示点对的数量。**注意：点对是无序的，$(u,v)$ 和 $(v,u)$ 算作同一条路径，一个点不算一条路径。**

对于 $100\%$ 的数据，$1\leq n \leq4 ·10^4$
 ，$1\leq w_i\leq 1000$。

by hanyuchen2019 @ 2020-02-01 14:02:15

@mrsrz

类型：题面修改

题目：[U101212 [USACO2013NOV]金发姑娘和N头牛 milktemp]

（改的太多了，不方便写出）

（我已达到绿钩级别但不方便验证）