（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 UltiMadow @ 2020-01-20 22:13:42

类型：试题提供

题目：[BOI2006]coin collector钱币收藏家

by PrincessQi @ 2020-01-20 22:17:18

类型：题面修改（标题修改？）

题目：P1856 [USACO5.5]矩形周长Picture

新标题：P1856 【模板】扫描线II / [USACO5.5]矩形周长Picture

by StudyingFather @ 2020-01-21 00:10:18

@MAGELDKI

请求增加树链剖分板子

P3384 不是吗？

（一般的树链剖分都指的是重链剖分）

（当然它原本是叫树链剖分的）

by xukuan @ 2020-01-21 07:58:53

@MAGELDKI 有了啊

by 若如初见 @ 2020-01-21 09:26:01

请问可以提供自己出的非模板题吗？

by George1123 @ 2020-01-21 09:56:30

类型：题面修改

题目：数字序列

新题面：

### 题目描述

现在我们有一个长度为 $n$ 的整数序列 $A$。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。

### 输入格式
第一行包含一个数 $n$，接下来 $n$ 个整数按顺序描述每一项的键值。

### 输出格式
第一行一个整数表示最少需要改变多少个数。

第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。

### 输入输出样例
输入 #1 复制
4
5 2 3 5
输出 #1 复制
1
4
### 说明/提示

【数据范围】

$90%$ 的数据 $n\le 6000$。

$100%$ 的数据 $n\le 35000$。

保证所有数列是随机的。

by George1123 @ 2020-01-21 09:56:49

@若如初见 no

by UltiMadow @ 2020-01-21 10:07:08

类型：试题提供

题目：[BOI2004]ships 船

by George1123 @ 2020-01-21 10:33:06

@chen_zhe

类型：题面提供

[POI]Cashier Employment

by cnyzz @ 2020-01-21 12:38:05

类型：题面修改

题目：[JSOI2010]部落划分

新题面：

#### 题目描述
聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。

不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了 $N$ 个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了 $K$ 个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法：

对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。

例如，下面的左图表示了一个好的划分，而右图则不是。请你编程帮助聪聪解决这个难题。

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

#### 输入格式
输入文件第一行包含两个整数 $N$ 和 $K(1 \leq N\leq1000$，$1<K\leq N)$，分别代表了野人居住点的数量和部落的数量。

接下来N行，每行包含两个正整数 $x$，$y$，描述了一个居住点的坐标$(0\leq x$, $y\leq 10000)$。

#### 输出格式
输出一行，为最优划分时，最近的两个部落的距离，精确到小数点后两位。
上一页 | 下一页