chen_zhe @ 2020-01-19 19:25:41
洛谷鼓励各位用户将大型比赛的试题或者洛谷上缺乏的模板题，在确认没有版权问题的情况下，提供给洛谷。但是因为此类贴子日益增多，严重影响了讨论版面，而且部分用户所提供的试题并不符合规定，故做出以下说明：
USACO，POI，Baltic OI 等），或者大型的网络公开赛（例如 Codeplus 等），但是不包含例如校内的网络模拟赛之类的试题。spj，则相对较易的部分必须自行完成。若实在有困难才可以征集。具体尺度由管理进行评判。同时，对于已在洛谷主题库中但不符合洛谷主题目题目规范的题目，我们鼓励用户进行更正，但也至少要达到绿勾级别。要求更正后的题面严格遵守规范，同样回复在本讨论下，为了方便管理员，请将题面使用代码框```括起来。
若有发现难度标签明显有问题（即对于普及-以及以下的题目相差两个档次，或者对于提高-以及以上难度相差一个档次），欢迎大家提供建议。请在本楼回复题号和应当修正的难度。
为了提高管理员的审核效率，本贴禁止任何无意义回复，所有无意义回复均会被删除，行为恶劣者将会禁言，但是可以询问说明中的问题。若为修复题目问题，建议带上链接以增加效率。
请不要@管理员，会有管理员不定期来本帖处理。
by Aw顿顿 @ 2020-02-22 16:27:48
类型：修改题面
题目：P1836 数页码
题面更改效果：
一本书的页码是从
一行为
一行，即所有单个数字的和。
源码：
## 题目描述
一本书的页码是从 $1\sim n$ 的连续整数：$1,2,3,\cdots,n$ 。请你求出全部页码中所有单个数字的和。例如第 $123$ 页的数码和即为 $1+2+3=6$ 。
## 输入格式
一行为 $n$ $(1\le n\le 10^9)$ 。
## 输出格式
一行，即所有单个数字的和。by cnyzz @ 2020-02-22 16:32:54
类型：题面修改
题目：[NOI2016]网格
将详细数据范围改成表格：
| 测试点 | ||
|---|---|---|
| $n,m$ | 测试点 | $c$ |
| :----------: | :----------: | :----------: |
| $n*m\leq 4$ | $1$ | $c\leq n*m$ |
| $n*m\leq 8$ | $2$ | $c\leq n*m$ |
| $n*m\leq 15$ | $3$ | $c\leq n*m$ |
| $n*m\leq 30$ | $4$| $c\leq n*m$ |
| $n*m\leq 100$ | $5$ | $c\leq n*m$ |
| $n*m\leq 300$ | $6$ | $c\leq n*m$ |
| $n*m\leq 10^3$ | $7$ | $c\leq n*m$ |
| $n*m\leq 2\times 10^4$ | $8$ | $c\leq 5$ |
| $n*m\leq 2\times 10^4$ | $9$ | $c\leq 15$ |
| $n*m\leq 2\times 10^4$ | $10$ | $c\leq 30$ |
| $n,m\leq 2\times 10^4,n*m\leq2\times 10^4$ | $11$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 2\times 10^4,n*m\leq10^5$ | $12$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 2\times 10^4,n*m\leq3\times 10^5$ | $13$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 2\times 10^4,n*m\leq10^6$ | $14$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 2\times 10^4,n*m\leq 10^9$ | $15$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 10^5$ | $16$ | $\sum c\leq 10^5$ |
| $n,m\leq 10^9$ | $17$ | $c=0$ |
| $n,m\leq 10^9$ | $18$ | $c\leq 1$ |
| $n,m\leq 10^9$ | $19$ | $c\leq 2$ |
| $n,m\leq 10^9$ | $20$ | $c\leq 3$ |
| $n,m\leq 10^9$ | $21$ | $c\leq 10$ |
| $n,m\leq 10^9$ | $22$ | $c\leq 30$ |
| $n,m\leq 10^9$ | $23$ | $c\leq 300$ |
| $n,m\leq 10^9$ | $24$ | $\sum c\leq 2 \times 10^4$ |
| $n,m\leq 10^9$ | $25$ | $\sum c\leq 10^5$ |by Aw顿顿 @ 2020-02-22 16:42:11
类型：修改题面
题目：P2022 有趣的数
关于
定义
输入仅一行，是两个整数
输出仅一行，即最小的
## 题目描述
关于 $1$ 到 $N$ 的正整数集合，可以将集合中的元素按照字典序排列。例如当 $N=11$ 时，其顺序应为：$1,10,11,2,3,4,5,6,7,8,9$ 。
定义 $K$ 在 $N$ 个数中的位置为 $Q(N,K)$ ，例如 $Q(11,2)=4$ 。现在给出整数 $K$ 和 $M$ ，要求找到最小的 $N$ ，使得 $Q(N,K)=M$ 。
## 输入格式
输入仅一行，是两个整数 $K$ 和 $M$ 。
## 输出格式
输出仅一行，即最小的 $N$ ，若不存答案则输出 $0$ 。by Aw顿顿 @ 2020-02-22 17:01:30
类型：修改题面
题目：P2399 non hates math
non习惯将分数化成小数，但在数学中要以分数形式写，不能化成小数,因此non找到了会编程的你，帮助他将小数化回分数。
给出一个小数，将它化成假分数的形式。
小数的类型有
普通小数。
循环小数，会给出循环节。
循环节用半角括号(循环节)表示。
一个小数
输出格式
输出这个小数
数据范围：
by Aw顿顿 @ 2020-02-22 17:02:12
@chen_zhe
大批修改题面等管理员拨冗来处理
by cnyzz @ 2020-02-22 18:03:40
类型：题面修改
题目：[USACO12MAR]Tractor S
经过一天漫长的工作，农场主 John 完全忘记了他的拖拉机还在场地中央。他的奶牛们总喜欢和他搞些恶作剧，它们在场地的不同位置丢下
拖拉机和干草堆都可以看作是二维平面上的点，它们的坐标都是整数，坐标范围在
请你帮助 John 计算一下，最少要移动多少堆干草才能将拖拉机开会坐标原点。
第一行，三个用空格隔开的整数
第
一行一个整数，表示最少要移动多少堆干草 John 才能将拖拉机开回坐标原点。
#### 题目描述
经过一天漫长的工作，农场主 John 完全忘记了他的拖拉机还在场地中央。他的奶牛们总喜欢和他搞些恶作剧，它们在场地的不同位置丢下 $N(1 \leq N \leq 50,000)$ 堆干草。这样 John 就必须先移走一些干草堆才能将拖拉机开走。
拖拉机和干草堆都可以看作是二维平面上的点，它们的坐标都是整数，坐标范围在 $1$ 到$1000$ 之间。没有那堆干草的坐标和拖拉机的初始坐标一致。John 驾驶拖拉机只能沿着坐标轴的方向移动若干单位长度，比如说，他可以先朝北移动 $2$ 个单位长度，再向东移动 $3$ 个单位长度等等。拖拉机不能移动到干草堆所占据的点。
请你帮助 John 计算一下，最少要移动多少堆干草才能将拖拉机开会坐标原点。
#### 输入格式
第一行，三个用空格隔开的整数 $N,x,y$，表示有 $N$ 堆干草和拖拉机的起始坐标。
第 $2$ 行到第 $N+1$ 行，每行两个用空格隔开的整数 $x,y$，表示每堆干草的坐标。
#### 输出格式
一行一个整数，表示最少要移动多少堆干草 John 才能将拖拉机开回坐标原点。by wtyqwq @ 2020-02-22 18:57:00
类型：题面修改
题目：P2257 YY的GCD
给定
第一行一个整数
接下来
输出
对于
## 题目描述
给定 $N,M\in \mathbb{N}^*$，求满足以下条件的数对 $(x,y)$ 的数量：
$$x\in [1,N] \cap y\in [1,M] \cap \gcd(x,y)\in\mathbb{P}$$
## 输入格式
第一行一个整数 $T$，表示数据组数。
接下来 $T$ 行，每行两个正整数 $N,M$。
## 输出格式
输出 $T$ 行，每行一个整数表示每一组数据的答案。
## 说明/提示
对于 $100\%$ 的数据，$T\le 10^4$，$1\le N,M \le 10^7$。@xht37 @chen_zhe @lyx613
by cnyzz @ 2020-02-22 21:52:47
类型：题面修改
题目：[CERC2015]Frightful Formula
新题面：
定义一个矩阵
矩阵的第一列是序列
矩阵的第一行是序列
其他元素使用给定的递归公式进行计算：
现在要求找求出
第一行包含四个整数
输出一个整数的值即
#### 题意翻译：
定义一个矩阵 $F$，其中第一行和第一列是给定的，计算矩阵方法如下：
矩阵的第一列是序列 $l$：
$F_{k,1}=l\times k$
矩阵的第一行是序列 $t$：
$F_{1,k}=t*k$
其他元素使用给定的递归公式进行计算：
$F_{i,j]}=a\times F_{i,j-1}+b\times F_{i-1,j}+c$
现在要求找求出 $F_{n,n}$ 模 $10^6+3$ 的值
#### 输入格式：
第一行包含四个整数 $n,a,b$ 和 $c(2\leq n\leq 2\times 10^5,0\leq a,b,c\leq 10^6)$ 矩阵的大小和递归参数，如问题描述中所述。
下面两行分别包含整数 $l_1,\ldots,l_n$ 和
$t_1,\ldots,t_n(l_1=t_1, 0\leq l_k,t_k\leq10^6)$
#### 输出格式：
输出一个整数的值即 $F_{n,n}$ 模 $10^6+3$ 。by cnyzz @ 2020-02-22 21:54:24
@SuperJvRuo
by cnyzz @ 2020-02-22 22:05:55
类型：题面修改
题目：[CERC2015]Export Estimate
新题面：
Luka 拥有一个地理数据公司保持着详细的城市地图和出口相关的数据。但是通常客户不想要完整的地图。相反，他们更想要一个只包含主要街道的简单地图：
所有优先级小于
对于每一个路口点
(a)如果这个路口没有连接到任何街道，它就会被删除。
(b)如果路口
i.删除道路
ii.删除路口
iii.加入一个连接路口
最初，图中没有环（即一条连接到自身的边）或者平行的边（即在同一对交点之间有一条以上的边），但在收缩的过程中可能会形成环和平行边。
请注意，在步骤2.（b）之前，
给定一个地图和一系列的出口的询问,每个询问找到路口的数量和街道地图出口的数量。
第一行包含两个整数
后面
第
输出包括
@SuperJvRuo
#### 题意翻译：
Luka 拥有一个地理数据公司保持着详细的城市地图和出口相关的数据。但是通常客户不想要完整的地图。相反，他们更想要一个只包含主要街道的简单地图：
1. 所有优先级小于 $p$ 的街道被删除
1. 对于每一个路口点 $i$ 从 $1$ 到 $n$（按照这个顺序处理）：
(a)如果这个路口没有连接到任何街道，它就会被删除。
(b)如果路口 $i$ 正好连接到两个不同的街道 $x$ 和 $y$，导致 $a$ 和 $b$ 两个路口都与路口 $i$ 不同，那么 $i$ 就会根据下面的过程进行收缩：
i.删除道路 $x$ 和道路 $y$；
ii.删除路口 $i$；
iii.加入一个连接路口 $a$ 和 $b$ 的新道路 $z$；
最初，图中没有环（即一条连接到自身的边）或者平行的边（即在同一对交点之间有一条以上的边），但在收缩的过程中可能会形成环和平行边。
请注意，在步骤2.（b）之前，$x$ 和 $y$ 都不能是环（即 $a$ 和 $b$ 必须和 $i$ 不同），但是新增的 $z$ 可以是一个环（即 $a$ 和 $b$ 可能是相同的）。
给定一个地图和一系列的出口的询问,每个询问找到路口的数量和街道地图出口的数量。
#### 输入格式：
第一行包含两个整数 $n(1 \le n\le3\times10^5)$ 和 $m(1\le m\le 3\times10^5)$ 分别是点和边的数量。
后面 $m$ 行包含三个整数分别是 $a,b$ 和 $p(1\le a,b \le n,0\le p\le 3\times10^5)$ 用来描述 $a,b$ 之间边的优先级 $p$，没有一条边只连接一个点，两个点之间最多有一条边。
第 $m+2$ 行包含一个整数 $q(1\le q\le 3\times10^5)$ 表示询问的个数，下一行有 $q$ 个整数，第 $k$ 个整数 $t_k(0\le tk\le 3\times10^5)$ 是第 $k$ 次询问的优先级。
#### 输出格式：
输出包括 $q$ 行。第 $k$ 行包含两个整数，分别是第 $k$ 次询问的点和边的个数。