（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 xht @ 2020-01-26 17:10:24

@shygo_cmll02 顺便，您前面贡献的所有题面都不合格

by cmll02 @ 2020-01-26 18:05:15

是因为没有数据下限吗？但是原题中没有下限的怎么办啊

by HohleFeuerwerke @ 2020-01-26 18:23:15

类型：题面修改

题目：CF65A Harry Potter and Three Spells


#### 题目描述

很久以前（可能甚至在第一本书中），尼古拉斯·勒梅，一位伟大的炼金术士和魔法石的创造者，教了哈利·波特三个有用的咒语。第一种方法可以将 $a$ 克沙子转换成 $b$ 克铅，第二种方法可以将 $c$ 克铅转换成 $d$ 克金，第三种方法可以将 $e$ 克金转换成 $f$ 克沙子。

当哈利告诉他的朋友这些咒语时，罗恩很惊讶。毕竟，如果他们能把沙子变成铅，铅变成金，然后再把部分金变成沙子，那么就有可能从少量的沙子开始得到大量的金！即是无限量的黄金！

相比之下，格兰杰对这个想法持怀疑态度。她认为，根据物质守恒定律，获得无限量的物质，即使使用魔法，也是不可能的。相反，物质在转化过程中甚至会减少，转化为能量。

虽然赫敏的理论似乎令人信服，罗恩却不相信她。罗恩觉得，赫敏制定了只属于她的物质守恒定律，以阻止哈利和罗恩在这些胡言乱语上浪费时间，并且让他们去做作业。

这就是为什么罗恩已经收集了一定数量的沙子进行实验。

朋友之间的争吵似乎是不可避免的。帮助哈利确定他的朋友中哪一个是对的，避免争吵。要做到这一点，你必须弄清楚是否有可能从有限数量的沙子中获得比任何预先分配黄金数量更多的黄金数量。

---

#### 输入格式

输入共一行，包含 $6$ 个整数，$a,b,c,d,e,f$ $(a,b,c,d,e,f\leq 1000)$。

---

#### 输出格式

如果可以获得无限的黄金，输出`Ron`，否则输出`Hermione`。

---

#### 样例解释

##### 样例一

如果最初有 $500$ 克沙子，应用第一种法术 $5$ 次，把沙子变成 $1000$ 克铅。然后应用第二个法术 $4$ 次，得到 $600$ 克黄金，把其中 $400$ 克的黄金转化成沙子，得到 $500$ 克沙子和 $200$ 克黄金。对这其中的 $500$ 克沙子进行同样的操作，可以得到无限黄金。所以输出`Ron`。

##### 样例四

由于得不到任何物质，所以不能得到无限黄金，输出`Hermione`。

##### 样例五

因为使用第二种法术可以无限凭空得到金子，所以输出`Ron`。

##### 样例七

用第三种法术，可以凭空得到无限沙子。我们用这种方法先得到 $10000$ 克沙子，然后用第一种法术 $100$ 次获得 $100$ 克铅。用这些铅，可以转化为 $1$ 克黄金。显然，因为沙子数量无限，所以可以得到无限数量的黄金，输出`Ron`。

by StudyingFather @ 2020-01-26 18:51:06

@shygo_cmll02

零也是个下界啊（

如果没有说有负数（或者这个数显然不是负数）的话就默认下界是零。

by HohleFeuerwerke @ 2020-01-27 10:19:21

类型：试题提供

题目：【模板】多项式求值

by cnyzz @ 2020-01-27 12:08:16

类型：题面修改

题目：P1623 [CEOI2007]树的匹配Treasury

新题面:

题目描述

给一棵树，你可以匹配有边相连的两个点，问你这棵树的最大匹配是多少，并且计算出有多少种最大匹配。

输入格式

第一行一个数 N，表示有多少个结点。

接下来 N 行，每行第一个数，表示要描述的那个结点。然后一个数 m，表示这个结点有 m 个儿子，接下来 m 个数，表示它的 m 个儿子的编号。

【数据规模】

#### 输出格式 输出两行，第一行输出最大匹配数，第二行输出最大匹配方案数。 ``` #### 题目描述 给一棵树，你可以匹配有边相连的两个点，问你这棵树的最大匹配是多少，并且计算出有多少种最大匹配。 #### 输入格式 第一行一个数 $N$，表示有多少个结点。 接下来 $N$ 行，每行第一个数，表示要描述的那个结点。然后一个数 $m$，表示这个结点有 $m$ 个儿子，接下来 $m$ 个数，表示它的 $m$ 个儿子的编号。 【数据规模】 $1\leq N\leq 1000$，其中 $40\%$ 的数据答案不超过 $10^8$。 #### 输出格式 输出两行，第一行输出最大匹配数，第二行输出最大匹配方案数。 ```

by cnyzz @ 2020-01-27 12:09:16

同时请管理审核一下我之前发的修改。

by tzc_wk @ 2020-01-27 13:41:31

类型：题面修改

题目：P4281 [AHOI2008]紧急集合 / 聚会


## 题目描述

欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有 $n$ 个等待点，有 $n-1$ 条道路连接着它们，每一条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一个点到另一个点要花费一个游戏币。

参加游戏的人三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对话机（用于和同组的成员联系）。当集合号吹响后，每组成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在 $n$ 个等待点中确定一个集结点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。

小可可和他的朋友邀请你一起参加这个游戏，由你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？

## 输入格式

第一行两个正整数 $n$ 和 $m$，分别表示等待点的个数（等待点也从 $1$ 到 $n$ 进行编号）和获奖所需要完成集合的次数。

随后 $n-1$ 行，每行两个正整数 $a,b$，表示编号为 $a$ 和编号为 $b$ 的等待点之间有一条路。

随后 $m$ 行，每行用三个正整数 $x,y,z$，表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。

## 输出格式

输出共 $m$ 行，每行两个用空格隔开的整数 $p,c$。其中第 $i$ 行表示第 $i$ 次集合点选择在编号为 $p$ 的等待点，集合总共的花费是 $c$ 个游戏币。

## 说明/提示

对于 $40\%$ 的数据，$n\leq2\times10^3$，$m\leq2\times 10^3$。

对于 $100\%$ 的数据，$1\leq x,y,z\leq n\leq 5\times10^5$，$1\leq m\leq 5\times 10^5$。

题目描述

欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有 n 个等待点，有 n-1 条道路连接着它们，每一条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一个点到另一个点要花费一个游戏币。

参加游戏的人三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对话机（用于和同组的成员联系）。当集合号吹响后，每组成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在 n 个等待点中确定一个集结点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。

小可可和他的朋友邀请你一起参加这个游戏，由你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？

输入格式

第一行两个正整数 n 和 m，分别表示等待点的个数（等待点也从 1 到 n 进行编号）和获奖所需要完成集合的次数。

随后 n-1 行，每行两个正整数 a,b，表示编号为 a 和编号为 b 的等待点之间有一条路。

随后 m 行，每行用三个正整数 x,y,z，表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。

输出格式

输出共 m 行，每行两个用空格隔开的整数 p,c。其中第 i 行表示第 i 次集合点选择在编号为 p 的等待点，集合总共的花费是 c 个游戏币。

说明/提示

对于 40\% 的数据，n\leq2\times10^3，m\leq2\times 10^3。

对于 100\% 的数据，1\leq x,y,z\leq n\leq 5\times10^5，1\leq m\leq 5\times 10^5。

by StudyingFather @ 2020-01-27 14:19:58

@HohleFeuerwerke

您这题和 NOIP2014 解方程 做法一致啊 orz

既然已经有做法一致的题了就没必要再加个模板了吧（

by Itst @ 2020-01-27 14:26:50

类型：题面修改

题目：CF1156F Card Bag

新题面：

### 题目描述

你有一个装有 $n$ 张卡牌的卡包，卡包中第 $i$ 张卡牌上写有数字 $a_i$。在接下来的每一个回合，你会从卡包中等概率随机抽出一张卡牌，每一回合抽出的卡牌不会重新放回卡包中。

从第二回合开始，每一回合，你需要对这一回合抽出的卡牌的点数 $x$ 和上一次抽出的卡牌的点数 $y$ 进行比较：

- 如果 $x < y$，游戏失败并结束；
- 如果 $x = y$，游戏胜利并结束；
- 如果 $x > y$，游戏继续。

如果某一次抽牌的时候卡包中没有牌，则游戏失败。

你需要求出游戏胜利的概率，对 $998244353$ 取模。

### 输入格式

第一行一个正整数 $n$ 表示卡牌数量，接下来一行 $n$ 个整数 $a_1,a_2,...,a_n$ 表示卡包中每张卡牌上的数字。

### 输出格式

输出一行一个整数表示游戏获胜的概率，对 $998244353$ 取模。

### 数据范围

$2 \leq n \leq 5000$，$1 \leq a_i \leq n$。
上一页 | 下一页