Problem

【CTSC2018】混合果汁

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

Description

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

Input

输入第一行包含两个正整数n,mn,m,表示果汁的种数和小朋友的数量。接下来nn行,每行三个正整数di,pi,lid_i,p_i,l_i,表示ii号果汁的美味度为did_i,每升价格为pip_i,在一瓶果汁中的添加上限为lil_i
接下来mm行依次描述所有小朋友:每行两个数正整数gj,Ljg_j,L_j描述一个小朋友,表示他最多能支付gjg_j元钱,他想要至少LjL_j升果汁。

Output

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

Read more »

Problem

【NOI2008】假面舞会

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

Description

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

Input

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

Output

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

Read more »

Problem

Dynamic Rankings

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

Description

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

Input

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

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

Output

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

Read more »

Problem

【POI2011】Meteors

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

Description

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

Input

第一行输入两个数N,MN,M
第二行有MM个数,第ii个数OiO_i表示第ii段轨道上有第OiO_i个国家的太空站。
第三行有NN个数,第ii个数PiP_i表示第ii个国家希望收集的陨石数量。
第四行有一个数KK,表示预测了接下来的KK场陨石雨。
接下来KK行,每行有三个数Li,Ri,AiL_i,R_i,A_i,表示第KK场陨石雨的发生地点在从LiL_i顺时针到RiR_i的区间中(如果LiRiL_i\le R_i,就是Li,Li+1,,RiL_i,L_i+1,\cdots,R_i,否则就是Ri,Ri+1,,m1,m,1,,LiR_i,R_i+1,\cdots,m-1,m,1,\cdots,L_i),向区间中的每个太空站提供AiA_i单位的陨石样本。

Output

输出共NN行。
ii行的数WiW_i表示第ii个国家在第WiW_i波陨石雨之后能够收集到足够的陨石样本。
如果到第KK波结束后仍然收集不到,输出NIE

Read more »

Problem

【SDOI2017】数字表格

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

Description

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

f[n]={0n=01n=1f[n1]+f[n2]n2f[n]= \begin{cases} 0&n=0\\ 1&n=1\\ f[n-1]+f[n-2]&n\ge2 \end{cases}

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

Input

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

Output

输出TT行,第ii行的数是第ii组数据的结果。

Read more »

Problem

【JSOI2008】球形空间产生器

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

Description

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

Input

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

Output

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

Read more »

Problem

最长双回文串

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

Description

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

Input

一行由小写英文字母组成的字符串SS

Output

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

Read more »

Problem

【HNOI2013】游走

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

Description

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

Input

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

Output

仅包含一个实数,表示最小的期望值,保留33位小数。

Read more »

Problem

【NOI2010】超级钢琴

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

Description

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

Input

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

Output

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

Read more »

Problem

树上的路径

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

Description

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

Input

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

Output

MM行,如题所述。

Read more »