chen_zhe @ 2020-01-19 19:25:41
洛谷鼓励各位用户将大型比赛的试题或者洛谷上缺乏的模板题，在确认没有版权问题的情况下，提供给洛谷。但是因为此类贴子日益增多，严重影响了讨论版面，而且部分用户所提供的试题并不符合规定，故做出以下说明：
USACO，POI，Baltic OI 等），或者大型的网络公开赛（例如 Codeplus 等），但是不包含例如校内的网络模拟赛之类的试题。spj，则相对较易的部分必须自行完成。若实在有困难才可以征集。具体尺度由管理进行评判。同时，对于已在洛谷主题库中但不符合洛谷主题目题目规范的题目，我们鼓励用户进行更正，但也至少要达到绿勾级别。要求更正后的题面严格遵守规范，同样回复在本讨论下，为了方便管理员，请将题面使用代码框```括起来。
若有发现难度标签明显有问题（即对于普及-以及以下的题目相差两个档次，或者对于提高-以及以上难度相差一个档次），欢迎大家提供建议。请在本楼回复题号和应当修正的难度。
为了提高管理员的审核效率，本贴禁止任何无意义回复，所有无意义回复均会被删除，行为恶劣者将会禁言，但是可以询问说明中的问题。若为修复题目问题，建议带上链接以增加效率。
请不要@管理员，会有管理员不定期来本帖处理。
by u2004 @ 2020-02-03 10:27:23
### 题目描述
现在给出一个表达式，形如 $a_{1}/a_{2}/a_{3}/.../a_{n}$。
如果直接计算，就是一个个除过去，比如 $1/2/1/4 = 1/8$。
然而小$\text{A}$看到一个分数感觉很不舒服，希望通过添加一些括号使其变成一个整数。一种可行的办法是 $(1/2)/(1/4)=2$ 。
现在给出这个表达式，求问是否可以通过添加一些括号改变运算顺序使其成为一个整数。
### 输入格式
一个测试点中会有多个表达式。
第一行 $t$ ，表示表达式数量。
对于每个表达式，第一行是 $n$ ，第二行 $n$ 个数，第 $i$ 个数表示 $a_{i}$ 。
### 输出格式
输出 $t$ 行。
对于每个表达式，如果可以通过添加括号改变顺序使其变成整数，那么输出```Yes```，否则输出```No```。
### 说明/提示
对于 $40\%$ 的数据， $n \le 16$。
对于 $70\%$ 的数据， $n \le 100$。
对于全部数据， $2 \le n \le 10000$ ， $1 \le t \le 100$ ， $1 \le a_{i}\le \text{maxlongint}$。现在给出一个表达式，形如
如果直接计算，就是一个个除过去，比如
然而小
现在给出这个表达式，求问是否可以通过添加一些括号改变运算顺序使其成为一个整数。
一个测试点中会有多个表达式。
第一行
对于每个表达式，第一行是
输出
对于每个表达式，如果可以通过添加括号改变顺序使其变成整数，那么输出Yes，否则输出No。
对于
对于
对于全部数据，
by u2004 @ 2020-02-03 10:28:10
### 题目背景
所谓同花顺，就是指一些扑克牌，它们花色相同，并且数字连续。
### 题目描述
现在我手里有 $n$ 张扑克牌，但它们可能并不能凑成同花顺。我现在想知道，最少更换其中的多少张牌，我能让这 $n$ 张牌都凑成同花顺？
### 输入格式
第一行一个整数 $n$ ，表示扑克牌的张数。接下来 $n$ 行，每行两个整数 $a_{i}$ 和 $b_{i}$ 。其中 $a_{i}$ 表示第 $i$ 张牌的花色，$b_{i}$ 表示第 $i$ 张牌的数字。
### 输出格式
一行一个整数，表示最少更换多少张牌可以达到目标。
### 说明/提示
数据范围
对于 $30\%$ 的数据， $n \le 10$ 。
对于 $60\%$ 的数据，$n \le 10^{5}$ ，$ 1 \le a_{i} \le 10^{5}$， $1 \le b_{i} \le n$ 。
对于 $100\%$ 的数据，$n \le 10^{5}$，$1 \le a_{i}, b_{i} \le 10^{9}$。所谓同花顺，就是指一些扑克牌，它们花色相同，并且数字连续。
现在我手里有
第一行一个整数
一行一个整数，表示最少更换多少张牌可以达到目标。
数据范围
对于
对于
对于
by u2004 @ 2020-02-03 10:28:38
修改的试题依顺序给出
by syksykCCC @ 2020-02-03 11:42:49
类型：题面修改
题目：P4503 [CTSC2014]企鹅QQ
PenguinQQ 是中国最大、最具影响力的 SNS（Social Networking Services）网站，以实名制为基础，为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验，满足用户对社交、资讯、娱乐、交易等多方面的需求。
PenguinQQ 是中国最大、最具影响力的 SNS（Social Networking Services）网站，以实名制为基础，为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验，满足用户对社交、资讯、娱乐、交易等多方面的需求。小 Q 是 PenguinQQ 网站的管理员，他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析，小 Q 发现同一个人注册的账户名称总是很相似的，例如 Penguin1，Penguin2，Penguin3……于是小 Q 决定先对这种相似的情形进行统计。
小 Q 定义，若两个账户名称是相似的，当且仅当这两个字符串等长且恰好只有一位不同。例如 Penguin1 和 Penguin2 是相似的，但 Penguin1和 2Penguin 不是相似的。而小 Q 想知道，在给定的
为了简化你的工作，小 Q 给你的 @ 共
小 Q 是 PenguinQQ 网站的管理员，他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析，小 Q 发现同一个人注册的账户名称总是很相似的，例如 `Penguin1`，`Penguin2`，`Penguin3`……于是小 Q 决定先对这种相似的情形进行统计。
小 Q 定义，若两个账户名称是相似的，当且仅当这两个字符串等长且恰好只有一位不同。例如 `Penguin1` 和 `Penguin2` 是相似的，但 `Penguin1`和 `2Penguin` 不是相似的。而小 Q 想知道，在给定的 $N$ 个账户名称中，有多少对是相似的。
为了简化你的工作，小 Q 给你的 $N$ 个字符串长度均等于 $L$，且只包含大小写字母、数字、下划线以及 `@` 共 $64$ 种字符，而且不存在两个相同的账户名称。第一行包含三个正整数
若 0 和 1 共
若 @ 共
随后
第一行包含三个正整数 $N$，$L$ 和 $S$。其中 $N$ 表示账户名称数量，$L$ 表示账户名称长度，$S$ 用来表示字符集规模大小，它的值只可能为 $2$ 或 $64$。
若 $S$ 等于 $2$，账户名称中只包含字符 `0` 和 `1` 共 $2$ 种字符；
若 $S$ 等于 $64$，账户名称中可能包含大小写字母、数字、下划线以及 `@` 共 $64$ 种字符。
随后 $N$ 行，每行一个长度为 $L$ 的字符串，用来描述一个账户名称。数据保证 $N$ 个字符串是两两不同的。仅一行一个正整数，表示共有多少对相似的账户名称。
仅一行一个正整数，表示共有多少对相似的账户名称。by u2004 @ 2020-02-03 12:19:11
类型：题面修改
题目：P3709 大爷的字符串题
### 题目背景
在那遥远的西南有一所学校
/*被和谐部分*/
然后去参加该省省选虐场
然后某蒟蒻不会做，所以也出了一个字符串题：
### 题目描述
给你一个字符串 $a$，每次询问一段区间的贡献
贡献定义：
每次从这个区间中随机拿出一个字符 $x$ ，然后把 $x$从这个区间中删除，你要维护一个集合 $S$
如果 $S$ 为空，你 $\text{rp}$ 减 $1$。
如果 $S$ 中有一个元素不小于 $x$，则你 $\text{rp}$ 减 $1$，清空 $S$。
之后将 $x$ 插入 $S$。
由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少 $\text{rp}$ ？ $\text{rp}$ 初始为 $0$。
询问之间不互相影响~
### 输入格式
第一行两个数 $n$ ，$m$ ，表示字符串长度与询问次数。
之后一行 $n$ 个数，表示字符串，
由于你是大爷，所以字符集 $10^9$。
之后 $m$ 行每行两个数，表示询问的左右区间。
### 输出格式
$m$ 行，每行一个数表示答案
### 说明/提示
前 $4$ 个点 $1$s，后面的点 $4$s。
对于 $10\%$ 的数据，是样例。
对于另外 $10\%$ 的数据，$n,m \le 10^2$，
对于另外 $10\%$ 的数据，$n,m \le 10^3$，
对于另外 $10\%$ 的数据，$n,m \le 10^4$，
对于另外 $10\%$ 的数据，$n,m \le 10^5$，
对于 $100\%$ 的数据，$n,m \le 2 \times10^5$，
保证数据向某省省选 $\text{day1T2}$ 一样 $\text{sb}$ ，大家尽情用暴力水过题吧！
没事，你只要在一个好学校，就算这题只能拿到 $10$ 分，也可以进队了。在那遥远的西南有一所学校
/被和谐部分/
然后去参加该省省选虐场
然后某蒟蒻不会做，所以也出了一个字符串题：
给你一个字符串
贡献定义：
每次从这个区间中随机拿出一个字符
如果
如果
之后将
由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少
询问之间不互相影响~
第一行两个数
之后一行
由于你是大爷，所以字符集
之后
by u2004 @ 2020-02-03 13:31:59
@mrsrz
by u2004 @ 2020-02-03 13:39:08
类型：题面修改
题目：P1357 花园
### 题目描述
小 $\text{L}$ 有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为 $1$ ~ $N$ ( $2 \le N \le 10^{15}$ )。
他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则，任意相邻 $M$ ( $2 \le M \le 5$ , $M \le N$ )个花圃中有不超过 $K$ ($1 \le K < M$ )个 $\text{C}$ 形的花圃，其余花圃均为 $\text{P}$ 形的花圃。
例如，$N=10$ , $M=5$ , $K=3$ 。则
$\text{CCPCPPPPCC}$ 是一种不符合规则的花圃；
$\text{CCPPPPCPCP}$ 是一种符合规则的花圃。
请帮小L求出符合规则的花园种数$\mod 1000000007$
请您编写一个程序解决此题。
### 输入格式
一行，三个数 $N,M,K$ 。
### 输出格式
花园种数$\mod 1000000007$
### 说明/提示
【数据规模】
$40\%$ 的数据中，$N \le 20$；
$60\%$ 的数据中，$M=2$；
$80\%$ 的数据中，$N \le 10^5$。
$100\%$ 的数据中，$N \le 10^{15}$。小
他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则，任意相邻
例如，
请您编写一个程序解决此题。
一行，三个数
花园种数
【数据规模】
by Alarm5854 @ 2020-02-03 13:48:33
问一下基数排序的模板题可不可以，P4604的基数排序过于卡常。
by u2004 @ 2020-02-03 16:41:15
类型：题面修改
题目：P2045 方格取数加强版
### 题目描述
给出一个 $n \times n$ 的矩阵,每一格有一个非负整数 $A_{i,j}$ ,( $A_{i,j} \le 10^3$ )现在从 $(1,1)$ 出发,可以往右或者往下走,最后到达 $(n,n)$ ,每达到一格,把该格子的数取出来,该格子的数就变成 $0$ ,这样一共走 $k$ 次,现在要求 $k$ 次所达到的方格的数的和最大。
### 输入格式
第一行两个数 $n$ , $k$ （$1 \le n \le 50$, $0 \le k \le 10$）。
接下来 $n$ 行,每行 $n$ 个数,分别表示矩阵的每个格子的数。
### 输出格式
一个数,为最大和
### 说明/提示
每个格子中的数不超过 $1000$。给出一个
第一行两个数
接下来
一个数,为最大和
每个格子中的数不超过
by u2004 @ 2020-02-03 16:44:26
类型：题面修改
题目：P2043 质因子分解
### 题目描述
对 $N!$ 进行质因子分解。
### 输入格式
输入数据仅有一行包含一个正整数 $N$ ，$N \le 10000$ 。
### 输出格式
输出数据包含若干行，每行两个正整数 $p$ , $a$ ，中间用一个空格隔开。表示 $N!$ 包含 $a$ 个质因子 $p$ ,要求按 $p$ 的值从小到大输出。
### 说明/提示
$10!=3628800=(2^8) \times (3^4) \times (5^2) \times 7$对
输入数据仅有一行包含一个正整数
输出数据包含若干行，每行两个正整数