NIRVANA

Problem

【SCOI2010】传送带

$\mathrm{Time\;Limit:\;1\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description

在一个$2$维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段$AB$和线段$CD$。
$\mathrm{lxhgww}$在$AB$上的移动速度为$P$，在$CD$上的移动速度为$Q$，在平面上的移动速度$R$。
现在$\mathrm{lxhgww}$想从$A$点走到$D$点，他想知道最少需要走多长时间。

Input

输入数据第一行是$4$个整数，表示$A$和$B$的坐标，分别为$A_x,A_y,B_x,B_y$。
第二行是$4$个整数，表示$C$和$D$的坐标，分别为$C_x,C_y,D_x,D_y$。
第三行是$3$个整数，分别是$P,Q,R$。

Output

输出数据为一行，表示$\mathrm{lxhgww}$从$A$点走到$D$点的最短时间，保留到小数点后$2$位。

Problem

【SCOI2014】方伯伯运椰子

$\mathrm{Time\;Limit:\;30\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description

Input

第一行包含二个整数$N$,$M$。
接下来$M$行代表$M$条边，表示这个交通网络。
每行六个整数，表示$U_i,V_i,A_i,B_i,C_i,D_i$。
接下来一行包含一条边，表示连接起点的边。

Output

一个浮点数，保留二位小数。表示答案，数据保证答案大于$0$。

Problem

【SCOI2014】方伯伯的玉米田

$\mathrm{Time\;Limit:\;60\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。
这排玉米一共有$N$株，它们的高度参差不齐。
方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。
方伯伯可以选择一个区间，把这个区间的玉米全部拔高$1$单位高度，他可以进行最多$K$次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。
问能最多剩多少株玉米，来构成一排美丽的玉米。

Input

第$1$行包含$2$个整数$N,K$，分别表示这排玉米的数目以及最多可进行多少次操作。
第$2$行包含$N$个整数，第$i$个数表示这排玉米，从左到右第$i$株玉米的高度$a_i$。

Output

输出$1$个整数，最多剩下的玉米数。

Problem

【SCOI2015】小凸玩矩阵

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

小凸和小方是好朋友，小方给小凸一个$N\times M\;(N\le M)$的矩阵$A$,要求小秃从其中选出$N$个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的$N$个数中第$K$大的数字的最小值是多少。

Input

第一行给出三个整数$N,M,K$
接下来$N$行，每行$M$个数字，用来描述这个矩阵

Output

输出一个整数，表示第$K$大数字的最小值

Problem

【TJOI2015】弦论

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

对于一个给定长度为$N$的字符串，求它的第$K$小子串是什么。

Input

第一行是一个仅由小写英文字母构成的字符串$S$。
第二行为两个整数$T$和$K$，$T$为$0$则表示不同位置的相同子串算作一个，$T=1$则表示不同位置的相同子串算作多个。$K$的意义如题所述。

Output

输出仅一行，为一个数字串，为第$K$小的子串。如果子串数目不足$K$个，则输出$-1$。

Problem

【SHOI2016】生成魔咒

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 $1$,$2$ 拼凑起来形成一个魔咒串 $[1,2]$。
一个魔咒串 $S$ 的非空字串被称为魔咒串 $S$ 的生成魔咒。例如 $S=[1,2,1]$ 时，它的生成魔咒有 $[1]$,$[2]$,$[1,2]$,$[2,1]$,$[1,2,1]$ 五种。$S=[1,1,1]$ 时，它的生成魔咒有 $[1]$,$[1,1]$,$[1,1,1]$ 三种。
最初 $S$ 为空串。共进行 $n$ 次操作，每次操作是在 $S$ 的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串 $S$ 共有多少种生成魔咒。

Input

第一行一个整数 $n$。
第二行 $n$ 个数，第 $i$ 个数表示第 $i$ 次操作加入的魔咒字符
$1\le n\le100000$，用来表示魔咒字符的数字 $x$ 满足 $1\le x\le10^9$

Output

输出 $n$ 行，每行一个数。第 $i$ 行的数表示第 $i$ 次操作后 $S$ 的生成魔咒数量

Problem

【SCOI2016】萌萌哒

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

一个长度为$n$的大数，用$S_1S_2S_3\cdots S_n$表示，其中$S_i$表示数的第$i$位，$S_1$是数的最高位，告诉你一些限制条件，每个条件表示为四个数，$l_1$，$r_1$，$l_2$，$r_2$，即两个长度相同的区间，表示子串$S_{l_1}S_{l_1+1}S_{l_1+2}\cdots S_{r_1}$与$S_{l_2}S_{l_2+1}S_{l_2+2}\cdots S_{r_2}$完全相同。比如$n=6$时，某限制条件$l_1=1$，$r_1=3$，$l_2=4$，$r_2=6$，那么$123123$，$351351$均满足条件，但是$12012$，$131141$不满足条件，前者数的长度不为$6$，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

Input

第一行两个数$n$和$m$，分别表示大数的长度，以及限制条件的个数。接下来$m$行，对于第$i$行，有$4$个数$l_{i_1}$，$r_{i_1}$，$l_{i_2}$，$r_{i_2}$，分别表示该限制条件对应的两个区间。
$1\le n\le 10^5$，$1\le m\le 10^5$，$1\le l_{i_1},r_{i_1},l_{i_2},r_{i_2}\le n$；并且保证$r_{i_1}-l_{i_1}=r_{i_2}-l_{i_2}$。

Output

一个数，表示满足所有条件且长度为$n$的大数的个数，答案可能很大，因此输出答案模$10^9+7$的结果即可。

Problem

于神之怒加强版

$\mathrm{Time\;Limit:\;80\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

给下$N,M,K$，计算$\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)^k\mod(10^9+7)$的值。

Input

输入有多组数据，输入数据的第一行两个正整数$T,K$，代表有$T$组数据，$K$的意义如上所示，下面第$2$行到第$T+1$行，每行为两个正整数$N,M$，其意义如上式所示。

Output

对于每一个询问，输出一行一个数作为回答。

Problem

DZY Loves Math

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

对于正整数$n$，定义$f(n)$为$n$所含质因子的最大幂指数。例如$f(1960)=f(2^3\times5^1\times7\times2)=3$, $f(10007)=1$, $f(1)=0$。
给定正整数$a,b$，求$\sum_{i=1}^{a}\sum_{j=1}^{b}{f(\gcd(i,j))}$。

Input

第一行一个数$T$，表示询问数。
接下来$T$行，每行两个数$a,b$，表示一个询问。

Output

对于每一个询问，输出一行一个非负整数作为回答。

Problem

Crash的数字表格

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;259\;MB}$

Description

今天的数学课上，$\mathrm{Crash}$小朋友学习了最小公倍数$\mathrm{(Least\;Common\;Multiple)}$。对于两个正整数$a$和$b$，$\mathrm{LCM(a, b)}$表示能同时被$a$和$b$整除的最小正整数。例如，$\mathrm{LCM(6, 8)=24}$。回到家后，$\mathrm{Crash}$还在想着课上学的东西，为了研究最小公倍数，他画了一张$N\times M$的表格。每个格子里写了一个数字，其中第$i$行第$j$列的那个格子里写着数为$\mathrm{LCM(i, j)}$。看着这个表格，$\mathrm{Crash}$想到了很多可以思考的问题。不过他最想解决的问题却是一个十分简单的问题：这个表格中所有数的和是多少。当$N$和$M$很大时，$\mathrm{Crash}$就束手无策了，因此他找到了聪明的你用程序帮他解决这个问题。由于最终结果可能会很大，$\mathrm{Crash}$只想知道表格里所有数的和$\mod 20101009\;\;$的值。

Input

输入的第一行包含两个正整数，分别表示$N$和$M$。

Output

输出一个正整数，表示表格中所有数的和$\mod 20101009\;\;$的值。