Problem

巡游

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

Description

Tar\mathrm{Tar}国正在准备每年一次的巡游活动。国王将会在一个城市SS里召集人群,沿着城市间的道路进行游览,最终在一个城市TT里发表他每年一次的著名演讲。
Tar\mathrm{Tar}国有NN个城市,由于国家的特殊要求,每两个城市之间存在一条唯一的简单通路。国王希望借着这个机会视察Tar\mathrm{Tar}国的城市建设,因此他提出SSTT的距离不能少于LL条道路。
同时,国王的私人医生检查了他的身体情况后,断定国王的身体不适合做长途旅行,因此他要求SSTT的距离不能多于RR条道路。
另外,政府希望跟随国王的人民沿途不仅能看到城市风景,还能看到城市外的美丽乡村。因此每条道路定义了一个魅力值CiC_i,一条路径的魅力值定义为这条路径的中位数。更详细的说法是这样的:将路径上所有边的魅力值排序,得到序列{Ai}\lbrace A_i\rbrace。假设i=2k+c  (0c1)i=2k+c\;(0\le c\le 1),中位数就是Ak+1A_{k+1}
你的任务就是求出魅力值最大的路径,并输出这个魅力值。

Input

第一行是三个整数N,L,RN,L,R,表示Tar\mathrm{Tar}国的城市个数、路径的最小和最大长度。
接下来N1N-1行,每行33个整数Ai,Bi,CiA_i,B_i,C_i,表示有一条连接AiA_iBiB_i且魅力值CiC_i的道路。

Output

仅一行,表示最大的魅力值。如果不存在这样的路径,输出1-1

Read more »

Problem

采药人的路径

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

Description

采药人的药田是一个树状结构,每条路径上都种植着同种药材。
采药人以自己对药材独到的见解,对每种药材进行了分类。大致分为两类,一种是阴性的,一种是阳性的。
采药人每天都要进行采药活动。他选择的路径是很有讲究的,他认为阴阳平衡是很重要的,所以他走的一定是两种药材数目相等的路径。
采药工作是很辛苦的,所以他希望他选出的路径中有一个可以作为休息站的节点(不包括起点和终点),满足起点到休息站和休息站到终点的路径也是阴阳平衡的。
他想知道他一共可以选择多少种不同的路径。

Input

11行包含一个整数NN
接下来N1N-1行,每行包含三个整数ai,bi,tia_i,b_i,t_i,表示aia_ibib_i这条路上药材的类型为tit_i

Output

输出符合采药人要求的路径数目。

Read more »

Problem

【Lydsy1708月赛】字符串大师

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

Description

一个串TTSS的循环节,当且仅当存在正整数kk,使得SSTT重复kk次的前缀,比如abcdabcdabcdab的循环节。
给定一个长度为nn的仅由小写字符构成的字符串SS,请对于每个k  (1kn)k\;(1\le k\le n),求出SS长度为kk的前缀的最短循环节的长度periper_i
字符串大师Q\mathrm{小Q}觉得这个问题过于简单,于是花了一分钟将其AC\mathrm{AC}了,他想检验你是否也是字符串大师。
Q\mathrm{小Q}告诉你nn以及per1,per2,,pernper_1,per_2,\cdots,per_n,请找到一个长度为nn的小写字符串SS,使得SS能对应上perper

Input

第一行包含一个正整数n  (1n105)n\;(1\le n\le10^5),表示字符串的长度。
第二行包含nn个正整数per1,per2,,pern  (1perii)per_1,per_2,\cdots,per_n\;(1\le per_i\le i),表示每个前缀的最短循环节长度。
输入数据保证至少存在一组可行解。

Output

输出一行一个长度为nn的小写字符串SS,即某个满足条件的SS
若有多个可行的SS,输出字典序最小的那一个。

Read more »

Problem

tty的求助

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

Description

n=1Nm=1Mk=0m1nk+xm\sum_{n=1}^{N}\sum_{m=1}^{M}\sum_{k=0}^{m-1}\lfloor\frac{nk+x}{m}\rfloor,其中xx为实数。

Input

输入仅有一行。
第一行仅有两个正整数N,MN,M和一个实数xx

Output

输出共一行,由于结果过大,所以请输出上式对998244353998244353取模的结果。

Read more »

Problem

【SDOI2015】约数个数和

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

Description

d(x)d(x)xx的约数个数,给定N,MN,M,求i=1nj=1md(ij)\sum_{i=1}^{n}\sum_{j=1}^{m}d(i\cdot j)

Input

输入文件包含多组测试数据。
第一行,一个整数TT,表示测试数据的组数。
接下来的TT行,每行两个整数N,MN,M

Output

TT行,每行一个整数,表示你所求的答案。

Read more »

Problem

小M的作物

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

Description

M\mathrm{小M}MC\mathrm{MC}里开辟了两块巨大的耕地AABB(你可以认为容量是无穷)。
现在,M\mathrm{小M}有种nn作物的种子,每种作物的种子有11个(就是可以种一棵作物)(用1n1\sim n编号),第ii种作物种植在AA中种植可以获得aia_i的收益,在BB中种植可以获得bib_i的收益,而且,现在还有这么一种神奇的现象,就是某些作物共同种在一块耕地中可以获得额外的收益。
M\mathrm{小M}找到了规则中共有mm种作物组合,第ii个组合中的作物共同种在AA中可以获得ci,1c_{i,1}的额外收益,共同总在BB中可以获得ci,2c_{i,2}的额外收益。
M\mathrm{小M}很快的算出了种植的最大收益,但是他想要考考你,你能回答他这个问题么?

Input

第一行包括一个整数nn
第二行包括nn个整数,表示aia_i
第三行包括nn个整数,表示bib_i
第四行包括一个整数mm
接下来mm行,第ii行依次输入:

  • 一个整数kik_i,表示第ii个作物组合中共有kik_i种作物
  • 两个整数ci,1,ci,2c_{i,1},c_{i,2},表示两种收益分别是多少
  • kik_i个整数,表示该组合中的作物编号

Output

只有一行,包括一个整数,表示最大收益

Read more »

Problem

【LNOI2014】LCA

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

Description

给出一个nn个节点的有根树(编号为00n1n-1,根节点为00)。一个点的深度定义为这个节点到根的距离+1这个节点到根的距离+1。设depidep_i表示点ii的深度,lcai,jlca_{i,j}表示iijj的最近公共祖先。
qq次询问,每次询问给出l,r,zl,r,z,求l<=i<=rdeplcai,z\sum_{l<=i<=r}dep_{lca_{i,z}}

Input

第一行22个整数n,qn,q
接下来n1n-1行,分别表示点11到点n1n-1的父节点编号。
接下来qq行,每行33个整数l,r,zl,r,z

Output

输出qq行,每行表示一个询问的答案。每个答案对201314201314取模输出

Read more »

Problem

【NOI2008】志愿者招募

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

Description

申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。
经过估算,这个项目需要NN天才能完成,其中第ii天至少需要AiA_i个人。布布通过了解得知,一共有MM类志愿者可以招募。其中第ii类可以从第SiS_i天工作到第TiT_i天,招募费用是每人CiC_i元。
新官上任三把火,为了出色地完成自己的工作,布布希望用尽量少的费用招募足够的志愿者,但这并不是他的特长!于是布布找到了你,希望你帮他设计一种最优的招募方案。

Input

第一行包含两个整数N,MN,M,表示完成项目的天数和可以招募的志愿者的种类。
接下来的一行中包含NN个非负整数,表示每天至少需要的志愿者人数。
接下来的MM行中每行包含三个整数Si,Ti,CiS_i,T_i,C_i,含义如上文所述。
为了方便起见,我们可以认为每类志愿者的数量都是无限多的。

Output

仅包含一个整数,表示你所设计的最优方案的总费用。

Read more »

Problem

【中山市选2011】完全平方数

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

Description

X\mathrm{X}自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。
这天是小X\mathrm{X}的生日,小W\mathrm{W}想送一个数给他作为生日礼物。当然他不能送一个小X\mathrm{X}讨厌的数。他列出了所有小X\mathrm{X}不讨厌的数,然后选取了第KK个数送给了小X\mathrm{X}。小X\mathrm{X}很开心地收下了。
然而现在小W\mathrm{W}却记不起送给小X\mathrm{X}的是哪个数了。你能帮他一下吗?

Input

包含多组测试数据。文件第一行有一个整数TT,表示测试数据的组数。
22至第T+1T+1行每行有一个整数KiK_i,描述一组数据,含义如题目中所描述。

Output

TT行,分别对每组数据作出回答。第ii行输出相应的第KiK_i个不是完全平方数的正整数倍的数。

Read more »

Problem

【PA2015】Siano

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

Description

农夫Byteasar\mathrm{Byteasar}买了一片nn亩的土地,他要在这上面种草。
他在每一亩土地上都种植了一种独一无二的草,其中,第ii亩土地的草每天会长高aia_i厘米。
Byteasar\mathrm{Byteasar}一共会进行mm次收割,其中第ii次收割在第did_i天,并把所有高度大于等于bib_i的部分全部割去。
Byteasar\mathrm{Byteasar}想知道,每次收割得到的草的高度总和是多少,你能帮帮他吗?

Input

第一行包含两个正整数n,mn,m,分别表示亩数和收割次数。
第二行包含nn个正整数,其中第ii个数为aia_i,依次表示每亩种植的草的生长能力。
接下来mm行,每行包含两个正整数di,bid_i,b_i,依次描述每次收割。

Output

输出mm行,每行一个整数,依次回答每次收割能得到的草的高度总和。

Read more »