（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 zhouwc @ 2020-01-31 16:39:17

@Karry5307 感谢贡献

by Aleph1022 @ 2020-01-31 17:34:59

类型：题面修改
题目：[[SCOI2016]美味] 新题面：

## 题目描述
一家餐厅有 $n$ 道菜，编号 $1\ldots n$，大家对第 $i$ 道菜的评价值为 $a_i\ (1\le i\le n)$。  
有 $m$ 位顾客，第 $i$ 位顾客的期望值为 $b_i$，而他的偏好值为 $x_i$。因此，第 $i$ 位顾客认为第 $j$ 道菜的美味度为 $b_i \operatorname{xor} {(a_j+x_i)}$，$\operatorname{xor}$ 表示异或运算。

第 $i$ 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第 $l_i$ 道到第 $r_i$ 道中选择。  
请你帮助他们找出最美味的菜。

## 输入格式
第一行，两个整数，$n,m$，表示菜品数和顾客数。  
第二行，$n$ 个整数，$a_1,a_2,\ldots,a_n$，表示每道菜的评价值。  
第三至 $m+2$ 行，每行四个整数，$b,x,l,r$，表示该位顾客的期望值，偏好值，和可以选择菜品区间。

## 输出格式
输出 $m$ 行，每行一个整数，$\mathrm{ymax}$ ，表示该位顾客选择的最美味的菜的美味值。

## 说明/提示
对于所有测试数据，$1 \le n \le 2\times 10^5,0 \le a_i,b_i,x_i < 10^5,1 \le l_i \le r_i \le n\ (1 \le i \le m),1 \le m \le 10^5$。

题目描述

一家餐厅有 n 道菜，编号 1\ldots n，大家对第 i 道菜的评价值为 a_i\ (1\le i\le n)。
有 m 位顾客，第 i 位顾客的期望值为 b_i，而他的偏好值为 x_i。因此，第 i 位顾客认为第 j 道菜的美味度为 b_i \operatorname{xor} {(a_j+x_i)}，\operatorname{xor} 表示异或运算。

第 i 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第 l_i 道到第 r_i 道中选择。
请你帮助他们找出最美味的菜。

输入格式

第一行，两个整数，n,m，表示菜品数和顾客数。
第二行，n 个整数，a_1,a_2,\ldots,a_n，表示每道菜的评价值。
第三至 m+2 行，每行四个整数，b,x,l,r，表示该位顾客的期望值，偏好值，和可以选择菜品区间。

输出格式

输出 m 行，每行一个整数，\mathrm{ymax} ，表示该位顾客选择的最美味的菜的美味值。

说明/提示

对于所有测试数据，1 \le n \le 2\times 10^5,0 \le a_i,b_i,x_i < 10^5,1 \le l_i \le r_i \le n\ (1 \le i \le m),1 \le m \le 10^5。

by hanyuchen2019 @ 2020-01-31 17:53:11

@mrsrz

类型：试题提供

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

by mrsrz @ 2020-01-31 17:55:34

@hanyuchen2019 题面不规范

by HohleFeuerwerke @ 2020-01-31 19:11:21

类型：题面修改

题目：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 HohleFeuerwerke @ 2020-01-31 19:12:17

类型：试题提供

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

by Karry5307 @ 2020-01-31 20:00:37

@HohleFeuerwerke 有类似的题（NOIp 2015 解方程），而且多项式多点求值他不香吗

by HohleFeuerwerke @ 2020-01-31 20:01:34

@Karry5307 QwQ被KarryD了，，

by Itst @ 2020-01-31 20:21:04

类型：题面修改

题目：CF1147F Zigzag Game

新题面：

这是一道交互题。

给出一个两边均有 n 个节点的完全二分图，左部点由 1 到 n 编号，右部点由 n+1 到 2n 编号。输入中会给出一个 n \times n 的矩阵 a，其中 a_{i,j} 表示连接 i 和 j+n 的边的边权。

现在有两个玩家 Alice 和 Bob 在这个图上玩游戏。首先 Alice 会选择 "increasing"（增加）或者 "decreasing"（减少）中的一个属性，Bob 则会自动选择另一个。接下来由 Alice 在图上选择一个起始节点 p 放上一枚棋子，Bob 选择一条连接节点 p 的边 (p,q)，将棋子移动到 q。

接下来由 Alice 先手轮流进行操作。每一次操作时操作方需要选择一个与当前节点 x 相邻的未被经过的节点 y。设 w 为 (x,y) 的边权，w' 为上一次移动时的边权，那么如果当前操作方在最开始选择 "increasing"，则需要满足 w > w'，否则需要满足 w < w'。然后当前操作方将棋子移动到 y。无法移动的操作方失败。

现在你需要与交互库模拟这样一盘游戏，包括选择先后（"Alice" 或者 "Bob"）、选择属性（"increasing" 或者 "decreasing"）、选择初始节点、选择移动节点和游戏过程。你需要保证在与交互库的游戏过程中获胜。


**这是一道交互题。**

给出一个两边均有 $n$ 个节点的完全二分图，左部点由 $1$ 到 $n$ 编号，右部点由 $n+1$ 到 $2n$ 编号。输入中会给出一个 $n \times n$ 的矩阵 $a$，其中 $a_{i,j}$ 表示连接 $i$ 和 $j+n$ 的边的边权。

现在有两个玩家 Alice 和 Bob 在这个图上玩游戏。首先 Alice 会选择 "increasing"（增加）或者 "decreasing"（减少）中的一个属性，Bob 则会自动选择另一个。接下来由 Alice 在图上选择一个起始节点 $p$ 放上一枚棋子，Bob 选择一条连接节点 $p$ 的边 $(p,q)$，将棋子移动到 $q$。

接下来由 Alice 先手轮流进行操作。每一次操作时操作方需要选择一个与当前节点 $x$ 相邻的未被经过的节点 $y$。设 $w$ 为 $(x,y)$ 的边权，$w'$ 为上一次移动时的边权，那么如果当前操作方在最开始选择 "increasing"，则需要满足 $w > w'$，否则需要满足 $w < w'$。然后当前操作方将棋子移动到 $y$。无法移动的操作方失败。

现在你需要与交互库模拟这样一盘游戏，包括选择先后（"Alice" 或者 "Bob"）、选择属性（"increasing" 或者 "decreasing"）、选择初始节点、选择移动节点和游戏过程。你需要保证在与交互库的游戏过程中获胜。

by Karry5307 @ 2020-01-31 20:33:31

@Itst stO Itst Orz