（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 ShineEternal @ 2020-01-20 16:09:50

@fry2017 起码有数据

by ShineEternal @ 2020-01-20 16:11:04

吧

by ShineEternal @ 2020-01-20 16:11:36

等等，感觉有了这个贴人反而变少了？

by cq_loves_Capoo @ 2020-01-20 16:25:46

什么叫有问题的试题？

by cnyzz @ 2020-01-20 17:02:07

类型：题面修改

题目：[TJOI2017]可乐

新题面：

#### 题目描述

加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 $1$ 号城市上。这个可乐机器人有三种行为： 停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现在给加里敦星球城市图，在第 $0$ 秒时可乐机器人在 $1$ 号城市，问经过了 $t$ 秒，可乐机器人的行为方案数是多少？

#### 输入格式

第一行输入两个正整数 $N$，$M$。$N$ 表示城市个数，$M$ 表示道路个数。（$1 \leq N \leq30,0 < M < 100$)。

接下来 $M$ 行输入$u$，$v$，表示 $u$，$v$（$1\leq u,v \leq n$)之间有一条道路。保证两座城市之间只有一条路相连。

最后输入时间 $t$。

#### 输出格式

输出可乐机器人的行为方案数，答案可能很大，请输出对 $2017$ 取模后的结果。

#### 说明/提示

【样例解释】

$1$ ->爆炸

$1$ -> $1$ ->爆炸

$1$ -> $2$ ->爆炸

$1$ -> $1$ -> $1$

$1$ -> $1$ -> $2$

$1$ -> $2$ -> $1$

$1$ -> $2$ -> $2$

$1$ -> $2$ -> $3$

【数据范围】

对于 $20\%$ 的测试点，有 $1 < t \leq 1000$。

对于$100\%$的测试点，有 $1 < t \leq 10^6$。

by cnyzz @ 2020-01-20 17:10:37

类型：题面修改

题目：[国家集训队]聪聪可可

新题面：

#### 题目描述

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。

他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画 $n$ 个“点”，并用 $n-1$ 条“边”把这 $n$ 个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是 $3$ 的倍数，则判聪聪赢，否则可可赢。

聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

#### 输入格式
输入的第 $1$ 行包含 $1$ 个正整数 $n$。后面 $n-1$ 行，每行 $3$ 个整数 $x$、$y$、$w$，表示 $x$ 号点和 $y$ 号点之间有一条边，上面的数是 $w$。

#### 输出格式
以即约分数形式输出这个概率（即“$a/b$”的形式，其中 $a$ 和 $b$ 必须互质。如果概率为 $1$，输出“$1/1$”）。

#### 说明/提示
【样例说明】

$13$ 组点对分别是 $(1,1)(2,2)(2,3)(2,5)(3,2)(3,3)(3,4)(3,5)(4,3)(4,4)(5,2)(5,3)(5,5)$。

【数据规模】

对于 $100\%$ 的数据，$n\leq20000$。

by __我谔谔__ @ 2020-01-20 17:16:15

类型：题面修改

@chen_zhe

题目：CF33A What is for dinner?

新体面：

鲨鱼有 n 颗牙齿，分别分布于 m 行上，第 i 颗牙齿有一个初始活力值 ci。鲨鱼有 k 个食物想要吃，但是，每吃掉一个食物就要消耗某一排牙齿的每一颗牙齿各 1 点活力，而鲨鱼必须保证每个牙齿的剩余活力不能到负数。试求鲨鱼最多能吃到的食物个数。

输入:

第一排三个整数 n , m , k ，后面 n 排每行两个整数 x 和 ci ,分别表示这个牙齿所在的行数和初始活力值。

输出：

一个整数，为答案。

数据范围：

1 \le m \le n \le 1000

0 \le k \le 10^6

1 \le x \le m

0 \le ci \le 10^6

Translated by @稀神探女

鲨鱼有 $n$ 颗牙齿，分别分布于 $m$ 行上，第 $i$ 颗牙齿有一个初始活力值 $ci$。鲨鱼有 $k$ 个食物想要吃，但是，每吃掉一个食物就要消耗某一排牙齿的每一颗牙齿各 $1$ 点活力，而鲨鱼必须保证每个牙齿的剩余活力不能到负数。 试求鲨鱼最多能吃到的食物个数。

### 输入:
第一排三个整数 $n$ , $m$ , $k$ ，后面 $n$ 排每行两个整数 $x$ 和 $ci$ ,分别表示这个牙齿所在的行数和初始活力值。

### 输出：
一个整数，为答案。

### 数据范围：
$1 \le m \le n \le 1000$

$0 \le k \le 10^6$

$1 \le x \le m$

$0 \le ci \le 10^6$

Translated by @[稀神探女](/user/85216)

by George1123 @ 2020-01-20 17:32:43

题目类型：模板

@chen_zhe

【模板】网络流

by LongDouble @ 2020-01-20 17:43:09

类型：题面修改

题目：[USACO08JAN]牛大赛Cow Contest

新题面：

### 题目描述
N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.

Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

FJ的 $N$$(1 \leq N \leq 100)$ 头奶牛们最近参加了场程序设计竞赛。在赛场上，奶牛们按 $1..N$ 依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为$A$的奶牛的编程能力强于编号为 $B$ 的奶牛 $(1 \leq A \leq N; 1 \leq B \leq N; A \neq B)$  ，那么她们的对决中，编号为A的奶牛总是能胜出。 FJ想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 $M(1 \leq M \leq 4,500)$ 轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

### 输入格式
第 $1$ 行: 2个用空格隔开的整数：$N$ 和 $M$。

第 $2..M+1$ 行: 每行为2个用空格隔开的整数 $A$、$B$，描述了参加某一轮比赛的奶 牛的编号，以及结果（编号为 $A$，即为每行的第一个数的奶牛为胜者）。

### 输出格式
第 $1$行: 输出1个整数，表示排名可以确定的奶牛的数目。

### 说明/提示
输出说明:

编号为$2$的奶牛输给了编号为$1$、$3$、$4$的奶牛，也就是说她的水平比这3头奶牛都差。

而编号为5的奶牛又输在了她的手下，也就是说，她的水平比编号为$5$的奶牛强一些。

于是，编号为$2$的奶牛的排名必然为第4，编号为$5$的奶牛的水平必然最差。

其他3头奶牛的排名仍无法确定。

by cnyzz @ 2020-01-20 17:43:15

类型：题面修改

题目：[CQOI2009]中位数

新题面：

#### 题目描述
给出 $1$~$n$ 的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是 $b$。中位数是指把所有元素从小到大排列后，位于中间的数。

#### 输入格式
第一行为两个正整数 $n$ 和 $b$，第二行为 $1$~$n$ 的排列。

【数据规模】

对于 $30\%$ 的数据中，满足 $1\leq n\leq100$；

对于60%的数据中，满足 $1\leq n\leq1000$；

对于100%的数据中，满足 $1\leq n≤100000$,$1\leq b\leq n$。

#### 输出格式
输出一个整数，即中位数为 $b$ 的连续子序列个数。