NIRVANA

Problem

【CTSC2018】混合果汁

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

Description

$\mathrm{小R}$热衷于做黑暗料理，尤其是混合果汁。
商店里有$n$种果汁，编号为$0,1,2,\cdots,n-1$。$i$号果汁的美味度是$d_i$每升价格为$p_i$。$\mathrm{小R}$在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中，$i$号果汁最多只能添加$l_i$升。
现在有$m$个小朋友过来找$\mathrm{小R}$要混合果汁喝，他们都希望$\mathrm{小R}$用商店里的果汁制作成一瓶混合果汁。其中，第$j$个小朋友希望他得到的混合果汁总价格不大于$g_j$，体积不小于$L_j$。
在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。

Input

输入第一行包含两个正整数$n,m$，表示果汁的种数和小朋友的数量。接下来$n$行，每行三个正整数$d_i,p_i,l_i$，表示$i$号果汁的美味度为$d_i$，每升价格为$p_i$，在一瓶果汁中的添加上限为$l_i$。
接下来$m$行依次描述所有小朋友：每行两个数正整数$g_j,L_j$描述一个小朋友，表示他最多能支付$g_j$元钱，他想要至少$L_j$升果汁。

Output

对于每个小朋友，输出一行，包含一个整数，表示他能喝到的最美味的混合果汁的美味度。如果无法满足他的需求，则输出$-1$。

Problem

【NOI2008】假面舞会

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

Description

一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。
今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一 个自己喜欢的面具。
每个面具都有一个编号，主办方会把此编号告诉拿该面具的人。为了使舞会更有神秘感，主办方把面具分为$k\;(k\ge3)$类，并使用特殊的技术将每个面具的编号标在了面具上，只有戴第$i$类面具的人才能看到戴第$i+1$类面具的人的编号，戴第$k$类面具的人能看到戴第$1$类面具的人的编号。
参加舞会的人并不知道有多少类面具，但是栋栋对此却特别好奇，他想自己算出有多少类面具，于是他开始在人群中收集信息。 栋栋收集的信息都是戴第几号面具的人看到了第几号面具的编号。如戴第$2$号面具的人看到了第$5$号面具的编号。栋栋自己也会看到一些编号，他也会根据自己的面具编号把信息补充进去。由于并不是每个人都能记住自己所看到的全部编号，因此，栋栋收集的信 息不能保证其完整性。现在请你计算，按照栋栋目前得到的信息，至多和至少有多少类面具。由于主办方已经声明了$k\ge3$，所以你必须将这条信息也考虑进去。

Input

第一行包含两个整数$n,m$，用一个空格分隔，$n$表示主办方总共准备了多少个面具，$m$表示栋栋收集了多少条信息。
接下来$m$行，每行为两个用空格分开的整数$a,b$，表示戴第$a$号面具的人看到了第$b$号面具的编号。相同的数对$a,b$在输入文件中可能出现多次。

Output

包含两个数，第一个数为最大可能的面具类数，第二个数为最小可能的面具类数。
如果无法将所有的面具分为至少$3$类，使得这些信息都满足，则认为栋栋收集的信息有错误，输出两个$-1$。

Problem

Dynamic Rankings

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

Description

给定一个含有$n$个数的序列$a[1],a[2],a[3],\cdots,a[n]$。
对于给定的$i,j,k$，请回答在$a[i],a[i+1],a[i+2],\cdots,a[j]$中第$k$小的数是多少$(1\le k\le j-i+1)$。
在询问中会有操作改变一些$a[i]$的值，改变后，需要针对改变后的$a$继续回答上面的问题。

Input

第一行有两个正整数$n,m$。
分别表示序列的长度和指令的个数。
第二行有$n$个数，表示$a[1],a[2]\cdots,a[n]$，这些数都小于$10^9$。
接下来的$m$行描述每条指令，每行的格式是下面两种格式中的一种。

• $Q\;i\;j\;k\;(1\le i\le j\le n,1\le k\le j-i+1)$表示询问指令，询问$a[i],a[i+1],\cdots,a[j]$中第$k$小的数。
• $C\;i\;t\;(1\le i\le n,0\le t\le10^9)$表示把$a[i]$改变成为$t$。

Output

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

Problem

【POI2011】Meteors

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

Description

$\mathrm{Byteotian\;Interstellar\;Union}$有$N$个成员国。
现在它发现了一颗新的星球，这颗星球的轨道被分为$M$份（第$M$份和第$1$份相邻），第$i$份上有第$A_i$个国家的太空站。
这个星球经常会下陨石雨。$\mathrm{BIU}$已经预测了接下来$K$场陨石雨的情况。$\mathrm{BIU}$的第$i$个成员国希望能够收集$P_i$单位的陨石样本。
你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。

Input

第一行输入两个数$N,M$。
第二行有$M$个数，第$i$个数$O_i$表示第$i$段轨道上有第$O_i$个国家的太空站。
第三行有$N$个数，第$i$个数$P_i$表示第$i$个国家希望收集的陨石数量。
第四行有一个数$K$，表示预测了接下来的$K$场陨石雨。
接下来$K$行，每行有三个数$L_i,R_i,A_i$，表示第$K$场陨石雨的发生地点在从$L_i$顺时针到$R_i$的区间中（如果$L_i\le R_i$，就是$L_i,L_i+1,\cdots,R_i$，否则就是$R_i,R_i+1,\cdots,m-1,m,1,\cdots,L_i$），向区间中的每个太空站提供$A_i$单位的陨石样本。

Output

输出共$N$行。
第$i$行的数$W_i$表示第$i$个国家在第$W_i$波陨石雨之后能够收集到足够的陨石样本。
如果到第$K$波结束后仍然收集不到，输出NIE。

Problem

【SDOI2017】数字表格

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

Description

$\mathrm{Doris}$刚刚学习了$\mathrm{fibonacci}$数列。用$f[i]$表示数列的第$i$项，那么

$$f[n]= \begin{cases} 0&n=0\\ 1&n=1\\ f[n-1]+f[n-2]&n\ge2 \end{cases}$$

$\mathrm{Doris}$用老师的超级计算机生成了一个$n\times m$的表格，第$i$行第$j$列的格子中的数是$f[\gcd(i,j)]$，其中$\gcd(i,j)$表示$i,j$的最大公约数。
$\mathrm{Doris}$的表格中共有$n\times m$个数，她想知道这些数的乘积是多少。答案对$10^9+7$取模。

Input

有多组测试数据。
第一个一个数$T$，表示数据组数。
接下来$T$行，每行两个数$n,m$。

Output

输出$T$行，第$i$行的数是第$i$组数据的结果。

Problem

【JSOI2008】球形空间产生器

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

Description

有一个球形空间产生器能够在$n$维空间中产生一个坚硬的球体。
现在，你被困在了这个$n$维球体中，你只知道球面上$n+1$个点的坐标，你需要以最快的速度确定这个$n$维球体的球心坐标，以便于摧毁这个球形空间产生器。

Input

第一行是一个整数$n\;(1\le n\le10)$。
接下来的$n+1$行，每行有$n$个实数，表示球面上一点的$n$维坐标。
每一个实数精确到小数点后$6$位，且其绝对值都不超过$20000$。

Output

有且只有一行，依次给出球心的$n$维坐标（$n$个实数），两个实数之间用一个空格隔开。
每个实数精确到小数点后$3$位，数据保证有解，你的答案必须和标准输出一模一样才能够得分。

Problem

最长双回文串

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

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为abc，逆序为cba，不相同）。
输入长度为$n$的串$S$，求$S$的最长双回文子串$T$，即可将$T$分为两部分$X,Y\;(|X|,|Y|\ge1)$且$X$和$Y$都是回文串。

Input

一行由小写英文字母组成的字符串$S$。

Output

一行一个整数，表示最长双回文子串的长度。

Problem

【HNOI2013】游走

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

Description

一个无向连通图，顶点从$1$编号到$N$，边从$1$编号到$M$。
$\mathrm{小Z}$在该图上进行随机游走，初始时$\mathrm{小Z}$在$1$号顶点，每一步$\mathrm{小Z}$以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当$\mathrm{小Z}$到达$N$号顶点时游走结束，总分为所有获得的分数之和。
现在请你对这$M$条边进行编号，使得$\mathrm{小Z}$获得的总分的期望值最小。

Input

第一行是正整数$N$和$M$，分别表示该图的顶点数和边数。
接下来$M$行每行是整数$u,v\;(1\le u,v\le N)$，表示顶点$u$与顶点$v$之间存在一条边。

Output

仅包含一个实数，表示最小的期望值，保留$3$位小数。

Problem

【NOI2010】超级钢琴

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

Description

$\mathrm{小Z}$是一个小有名气的钢琴家，最近$\mathrm{C博士}$送给了$\mathrm{小Z}$一架超级钢琴，$\mathrm{小Z}$希望能够用这架钢琴创作出世界上最美妙的音乐。
这架超级钢琴可以弹奏出$n$个音符，编号为$1\sim n$。第$i$个音符的美妙度为$A_i$，其中$A_i$可正可负。
一个“超级和弦“由若干个编号连续的音符组成，包含的音符个数不少于$L$且不多于$R$。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。
$\mathrm{小Z}$决定创作一首由$k$个超级和弦组成的乐曲，为了使得乐曲更加动听，$\mathrm{小Z}$要求该乐曲由$k$个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。$\mathrm{小Z}$想知道他能够创作出来的乐曲美妙度最大值是多少。

Input

第一行包含四个正整数$n,k,L,R$。其中$n$为音符的个数，$k$为乐曲所包含的超级和弦个数，$L$和$R$分别是超级和弦所包含音符个数的下限和上限。
接下来$n$行，每行包含一个整数$A_i$，表示按编号从小到大每个音符的美妙度。

Output

只有一个整数，表示乐曲美妙度的最大值。

Problem

树上的路径

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

Description

给定一个$N$个结点的树，结点用正整数$1\sim N$编号，每条边有一个正整数权值。
用$d(a,b)$表示从结点$a$到结点$b$路边上经过边的权值，其中要求$a<b$。
将这$\frac{n\times(n-1)}{2}$个距离从大到小排序，输出前$M$个距离值。

Input

第一行两个正整数$N,M$。
下面$N-1$行，每行三个正整数$a,b,c\;(a,b\le N,\;c\le10000)$，表示结点$a$到结点$b$有一条权值为$c$的边。

Output

共$M$行，如题所述。