（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 mrsrz @ 2020-02-01 14:09:56

@hanyuchen2019

  1. 题面不符合标准
  2. 难度过低，没有意义

by Itst @ 2020-02-01 14:39:44

类型：题面修改

题目：[SDOI2014]括号序列计数

新题面：


### 题目描述

Alice 和 Bob 知道，一个由空格、左括号、右括号组成的序列被称为括号序列。有一类特殊的括号序列被称为"合法括号序列"。已知：

- 空串是合法括号序列；

- 如果 $S1$ 和 $S2$ 均是合法括号序列，则 $S1+S2$ 是合法括号序列；

- 如果 $S$是合法括号序列，则 "("+$S$+")" 是合法括号序列；

- 如果 $S$ 是合法括号序列，在 $S$ 的任何位置（包括头尾位置）插入一个空格得到的序列是合法括号序列。

现在 Alice 希望知道：对于某个已知的有限状态自动机中的状态 $s$ 与 $t$ ，存在多少以 $s$ 为起点、$t$ 为终点、长度为 $k$ 的合法括号序列。

有限状态自动机是一个有向图 $G$，由 $n$ 个结点组成，每一个结点表示一个状态，且存在三类以此为起点的有向边。对于每一个状态，其向外的同一类有向边指向同样的状态。三类有向边分别代表三种符号：左括号、右括号和空格。

我们将状态从 $0$ 开始编号。对于第 $i$ 个状态，用 $dfa_{i,0/1/2}$ 分别表示从 $i$ 出发，代表了左括号、右括号和空格的那一类边指向的状态，再用 $dfa2_{i,0/1/2}$ 表示每一类边的个数。对于一条从 $s$ 出发到 $t$ 结束的路径，满足长度为 $k$ 且路径经过的边对应的符号构成的序列组成了一组合法的括号匹配，则称作"满足 $[G,s,t,k]$ 的合法括号序列"。

现在，Alice 为 Bob 提供了自动机 $G$，并提出 $Q$ 组询问。对于每一组询问，Alice 会给出 $s,t,k$，她希望 Bob 可以告诉她满足 $[G,s,t,k]$ 的合法括号序列有多少组。她只需要知道答案除以 $47$ 后的余数。

### 输入格式

第一行一个整数 $n$ 表示状态数，第二到 $n+1$ 行，第 $i$ 行六个整数 $dfa_{i-1,0},dfa2_{i-1,0},dfa_{i-1,1},dfa2_{i-1,1},dfa_{i-1,2},dfa2_{i-1,2}$，描述第 $i-1$ 个状态的出边。

接下来一行一个整数 $q$ 表示询问数，接下来 $q$ 行每行三个整数 $s,t,k$ 描述一组询问。

### 输出格式

输出 $q$ 行，每行一个整数表示对应询问的答案 $\bmod\ 47$ 的结果。

### 说明/提示

在样例解释中使用符号 `_` 代表空格。

对于第一组询问长度为 $3$ 的合法括号序列有：

- `___`，合法方案数为 $3^3 = 27$；
- `_()`、`(_)`、`()_`，合法方案数均为 $1\times2\times3=6$。

所以总方案数为 $27+6\times3=45$。

对于 $100 \%$ 的数据，$1 \leq n \leq 2$，$0 \leq dfa_{i,j} , s , t < n$，$0 \leq dfa2_{i,j} < 2^{31}$，$1 \leq k \leq 10^5$。

题目描述

Alice 和 Bob 知道，一个由空格、左括号、右括号组成的序列被称为括号序列。有一类特殊的括号序列被称为"合法括号序列"。已知：

现在 Alice 希望知道：对于某个已知的有限状态自动机中的状态 s 与 t ，存在多少以 s 为起点、t 为终点、长度为 k 的合法括号序列。

有限状态自动机是一个有向图 G，由 n 个结点组成，每一个结点表示一个状态，且存在三类以此为起点的有向边。对于每一个状态，其向外的同一类有向边指向同样的状态。三类有向边分别代表三种符号：左括号、右括号和空格。

我们将状态从 0 开始编号。对于第 i 个状态，用 dfa_{i,0/1/2} 分别表示从 i 出发，代表了左括号、右括号和空格的那一类边指向的状态，再用 dfa2_{i,0/1/2} 表示每一类边的个数。对于一条从 s 出发到 t 结束的路径，满足长度为 k 且路径经过的边对应的符号构成的序列组成了一组合法的括号匹配，则称作"满足 [G,s,t,k] 的合法括号序列"。

现在，Alice 为 Bob 提供了自动机 G，并提出 Q 组询问。对于每一组询问，Alice 会给出 s,t,k，她希望 Bob 可以告诉她满足 [G,s,t,k] 的合法括号序列有多少组。她只需要知道答案除以 47 后的余数。

输入格式

第一行一个整数 n 表示状态数，第二到 n+1 行，第 i 行六个整数 dfa_{i-1,0},dfa2_{i-1,0},dfa_{i-1,1},dfa2_{i-1,1},dfa_{i-1,2},dfa2_{i-1,2}，描述第 i-1 个状态的出边。

接下来一行一个整数 q 表示询问数，接下来 q 行每行三个整数 s,t,k 描述一组询问。

输出格式

输出 q 行，每行一个整数表示对应询问的答案 \bmod\ 47 的结果。

说明/提示

在样例解释中使用符号 _ 代表空格。

对于第一组询问长度为 3 的合法括号序列有：

所以总方案数为 27+6\times3=45。

对于 100 \% 的数据，1 \leq n \leq 2，0 \leq dfa_{i,j} , s , t < n，0 \leq dfa2_{i,j} < 2^{31}，1 \leq k \leq 10^5。

by chzhc @ 2020-02-01 14:40:06

类型：试题提供 题目：【模板】最小表示法

by hanyuchen2019 @ 2020-02-01 14:55:27

@mrsrz

类型：题面修改

题目：U101212

鲜为人知的是，金发姑娘最终经营了一个农场。在她的农场，她有一个谷仓含 $N$ 头奶牛 ($1≤N≤2e4$)。其中奶牛 $i$ 只能适应 $A(i)$ 到 $B(i)$ 这一区间的室温 ($0≤A(i)≤B(i)≤1e9$)。管理员通过设定恒温器的温度来控制室温，显然管理员可以任意设定恒温器温度（温度值一定为整数）。如果管理员设定的室温 $T$ 小于 $A(i)$，奶牛 $i$ 就会觉得冷，相应的产奶量就会变为 $X$；如果管理员设定的室温 $T$ 正好在 $A(i)$ 到 $B(i)$ 这一区间，即 $A(i)≤T≤B(i)$。奶牛 $i$ 就会觉得很舒适，相应的产奶量就会变为 $Y$；如果管理员设定的室温 $T$ 大于 $B(i)$，奶牛 $i$ 就会觉得热，相应的产奶量就会变为 $Z$。当然，$Y$ 一定大于 $X$ 和 $Z$。
现在告诉你 $X$、$Y$ 和 $Z$ 的值以及每头奶牛能适应的室温区间，请帮助管理员设定好牛棚内的最佳室温以获得最大的产奶量。$X$、$Y$ 和 $Z$ 都是范围在 $0$ 到 $1000$ 之内的整数。

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

by cnyzz @ 2020-02-02 11:19:46

@hanyuchen2019 您修改私题有什么意义呢？

by cnyzz @ 2020-02-02 11:45:59

类型：试题提供

题目：[CEOI2004]糖果

by cnyzz @ 2020-02-02 12:11:13

@hanyuchen2019 而且题面不符要求

by syksykCCC @ 2020-02-02 19:37:53

类型：模板题提供

题目：【模板】树上莫队

by u2004 @ 2020-02-02 21:39:50

类型：题面修改，提供SPJ。

[SDOI2014]酗酒者


### 题目描述

$\text{Alice}$ 发现：人在心情不好的时候，便会选择酗酒。这往往与 $\text{OI}$ 选手比赛胜利后的欢腾庆祝不同，酗酒者喝醉后便会忘记回家的路，然后在大街上无规律地乱走乱逛，同时喊着一些谁也听不懂的话。

这几天， $\text{Bob}$  因为考试的原因心情很不好，每天晚上都会在城里面找一处酒吧。喝醉后离开酒吧开始在城市街道中无规律乱走，直到某一时刻，若他碰巧遇到了在夜晚出来看星星的 $\text{Alice}$ ，便会被她带回家。

已知 $\text{Alice}$ 和 $\text{Bob}$  所在的城市街道可以被描绘为一个 $N$ 行 $M$ 列的格点地图， $N$ 行依次编号为 $0$ 到 $N-1$ ， $M$ 列依次编号为 $0$ 到 $M-1$ 。城市中共有 $N \times M$ 处路口，每一个路口可以用坐标 $(i,j)$ 表示。若 $i<N$ ，则 $(i,j)$ 与 $(i+1,j)$ 有无向的连边，边权长度 ， $p_{(i,j)}$ 表示走过这一条路所需的时间。若 $j<M$ ，则 $(i,j)$ 与 $(i,j+1)$ 有连无向边，边权长度 $q_{(i,j)}$ 。

对于给定的两个点 $(u,v)$ 和 $(s,t)$ 分别为 $\text{Bob}$ 今晚去的酒吧的位置，和 $\text{Alice}$ 今晚看星星的位置。 $\text{Bob}$ 离开酒吧后，对于每一个路口，他会等概率选择其中之一，然后走向下一个路口。在走到下一个路口之前， $\text{Bob}$ 不会回头。同时 $\text{Bob}$ 并不会因为之前走过什么道路而影响之后的行走路线。

具体来说：如果 $\text{Bob}$ 从 $(3,4)$ 走到 $(3,5)$ ，他有可能在抵达 $(3,5)$ 后立刻折回 $(3,4)$。对于四叉路口， $\text{Bob}$ 向每一个方向行走的概率都是 $1/4$ ，对于三叉路口（这只存在于城市的边界上）则是 $1/3$ ，对于二叉路口（这只存在于城市的 $4$ 个角落）就是 $1/2$。

 $\text{Alice}$ 希望知道，从 $\text{Bob}$ 离开酒吧， $\text{Alice}$ 期望情况下还需要等多久才能等到 $\text{Bob}$ ，即对于给定的两个点(u,v)与(s,t)， $\text{Bob}$ 从 $(u,v)$ 走到 $(s,t)$ 的期望用时是多少？

### 输入格式

第一行 $N$ ， $M$ 。 之后 $N-1$ 行，每行 $M$ 个正整数，其中第 $i$ 行第 $j$ 个为 $p_{(i,j)}$ 。 

之后 $N$ 行，每行 $M-1$ 个正整数，其中第 $i$ 行第 $j$ 个为 $q_{(i,j)}$ 。 单独一行给出一个整数 $Q$ ，表示总询问次数。

之后 $Q$ 行，每行有 $4$ 个整数 $u$ ，$v$ ，$s$ ，$t$ 。

### 输出格式

一共 $Q$ 行，每一行对应一次询问：从 $(u,v)$ 走到 $(s,t)$ 的期望距离是多少？你的答案可以保 留任意多位小数，但只有与正确答案的错误率在 $0.1\%$ 内才算正确。

### 说明/提示
对于 $10\%$ 的数据， $N \times M \le 25$ 。

对于 $30\%$ 的数据， $N \times M \le 625$ 。

对于 $50\%$的数据， $N \times M \le 2500$。

对于 $100\%$ 的数据， $N \times M \le 10000$ ， $Q<=100$ 。 $\forall i,j$ , $ p_{(i,j)}$ , $q_{(i,j)}$ $\le 200$。

此外存在 $10\%$ 的数据，$min(N,M) \le 10$。

题目描述

这几天， $\text{Bob}$ 因为考试的原因心情很不好，每天晚上都会在城里面找一处酒吧。喝醉后离开酒吧开始在城市街道中无规律乱走，直到某一时刻，若他碰巧遇到了在夜晚出来看星星的 $\text{Alice}$ ，便会被她带回家。 已知 $\text{Alice}$ 和 $\text{Bob}$ 所在的城市街道可以被描绘为一个 $N$ 行 $M$ 列的格点地图， $N$ 行依次编号为 $0$ 到 $N-1$ ， $M$ 列依次编号为 $0$ 到 $M-1$ 。城市中共有 $N \times M$ 处路口，每一个路口可以用坐标 $(i,j)$ 表示。若 $i<N$ ，则 $(i,j)$ 与 $(i+1,j)$ 有无向的连边，边权长度 ， $p_{(i,j)}$ 表示走过这一条路所需的时间。若 $j<M$ ，则 $(i,j)$ 与 $(i,j+1)$ 有连无向边，边权长度 $q_{(i,j)}$ 。 对于给定的两个点 $(u,v)$ 和 $(s,t)$ 分别为 $\text{Bob}$ 今晚去的酒吧的位置，和 $\text{Alice}$ 今晚看星星的位置。 $\text{Bob}$ 离开酒吧后，对于每一个路口，他会等概率选择其中之一，然后走向下一个路口。在走到下一个路口之前， $\text{Bob}$ 不会回头。同时 $\text{Bob}$ 并不会因为之前走过什么道路而影响之后的行走路线。 具体来说：如果 $\text{Bob}$ 从 $(3,4)$ 走到 $(3,5)$ ，他有可能在抵达 $(3,5)$ 后立刻折回 $(3,4)$。对于四叉路口， $\text{Bob}$ 向每一个方向行走的概率都是 $1/4$ ，对于三叉路口（这只存在于城市的边界上）则是 $1/3$ ，对于二叉路口（这只存在于城市的 $4$ 个角落）就是 $1/2$。 $\text{Alice}$ 希望知道，从 $\text{Bob}$ 离开酒吧， $\text{Alice}$ 期望情况下还需要等多久才能等到 $\text{Bob}$ ，即对于给定的两个点(u,v)与(s,t)， $\text{Bob}$ 从 $(u,v)$ 走到 $(s,t)$ 的期望用时是多少？ ### 输入格式 第一行 $N$ ， $M$ 。 之后 $N-1$ 行，每行 $M$ 个正整数，其中第 $i$ 行第 $j$ 个为 $p_{(i,j)}$ 。 之后 $N$ 行，每行 $M-1$ 个正整数，其中第 $i$ 行第 $j$ 个为 $q_{(i,j)}$ 。 单独一行给出一个整数 $Q$ ，表示总询问次数。 之后 $Q$ 行，每行有 $4$ 个整数 $u$ ，$v$ ，$s$ ，$t$ 。 ### 输出格式 一共 $Q$ 行，每一行对应一次询问：从 $(u,v)$ 走到 $(s,t)$ 的期望距离是多少？你的答案可以保 留任意多位小数，但只有与正确答案的错误率在 $0.1\%$ 内才算正确。 ### 说明/提示 对于 $10\%$ 的数据， $N \times M \le 25$ 。 对于 $30\%$ 的数据， $N \times M \le 625$ 。 对于 $50\%$的数据， $N \times M \le 2500$。 对于 $100\%$ 的数据， $N \times M \le 10000$ ， $Q<=100$ 。 $\forall i,j$ , $ p_{(i,j)}$,$q_{(i,j)}$ $\le 200$。 此外存在 $10\%$ 的数据，$min(N,M) \le 10$。 ### Special Judge ```cpp #include "testlib.h" int n,m; int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int q; n=inf.readInt();m=inf.readInt(); for(int i=0;i<n-1;i++) { for(int j=0;j<m;j++) { q=inf.readInt(); } } for(int i=0;i<n;i++) { for(int j=0;j<m-1;j++) { q=inf.readInt(); } } int Q=inf.readInt(); for(int i=0;i<Q;i++) { double pans = ouf.readDouble(); double jans = ans.readDouble(); if (fabs(pans - jans)>0.001*pans) quitf(_wa, "The answer is wrong."); } quitf(_ok, "The answer is correct."); } ```

by u2004 @ 2020-02-02 21:41:11

@mrsrz

上一页 | 下一页