NIRVANA

Problem

巡游

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

Description

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

Input

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

Output

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

Problem

采药人的路径

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

Description

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

Input

第$1$行包含一个整数$N$。
接下来$N-1$行，每行包含三个整数$a_i,b_i,t_i$，表示$a_i$到$b_i$这条路上药材的类型为$t_i$。

Output

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

Problem

【Lydsy1708月赛】字符串大师

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

Description

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

Input

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

Output

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

Problem

tty的求助

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

Description

求$\sum_{n=1}^{N}\sum_{m=1}^{M}\sum_{k=0}^{m-1}\lfloor\frac{nk+x}{m}\rfloor$，其中$x$为实数。

Input

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

Output

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

Problem

【SDOI2015】约数个数和

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

Description

设$d(x)$为$x$的约数个数，给定$N,M$，求$\sum_{i=1}^{n}\sum_{j=1}^{m}d(i\cdot j)$

Input

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

Output

$T$行，每行一个整数，表示你所求的答案。

Problem

小M的作物

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

Description

$\mathrm{小M}$在$\mathrm{MC}$里开辟了两块巨大的耕地$A$和$B$（你可以认为容量是无穷）。
现在，$\mathrm{小M}$有种$n$作物的种子，每种作物的种子有$1$个（就是可以种一棵作物）（用$1\sim n$编号），第$i$种作物种植在$A$中种植可以获得$a_i$的收益，在$B$中种植可以获得$b_i$的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益。
$\mathrm{小M}$找到了规则中共有$m$种作物组合，第$i$个组合中的作物共同种在$A$中可以获得$c_{i,1}$的额外收益，共同总在$B$中可以获得$c_{i,2}$的额外收益。
$\mathrm{小M}$很快的算出了种植的最大收益，但是他想要考考你，你能回答他这个问题么？

Input

第一行包括一个整数$n$
第二行包括$n$个整数，表示$a_i$
第三行包括$n$个整数，表示$b_i$
第四行包括一个整数$m$
接下来$m$行，第$i$行依次输入：

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

Output

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

Problem

【LNOI2014】LCA

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

Description

给出一个$n$个节点的有根树（编号为$0$到$n-1$，根节点为$0$）。一个点的深度定义为$这个节点到根的距离+1$。设$dep_i$表示点$i$的深度，$lca_{i,j}$表示$i$与$j$的最近公共祖先。
有$q$次询问，每次询问给出$l,r,z$，求$\sum_{l<=i<=r}dep_{lca_{i,z}}$。

Input

第一行$2$个整数$n,q$。
接下来$n-1$行，分别表示点$1$到点$n-1$的父节点编号。
接下来$q$行，每行$3$个整数$l,r,z$。

Output

输出$q$行，每行表示一个询问的答案。每个答案对$201314$取模输出

Problem

【NOI2008】志愿者招募

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

Description

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

Input

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

Output

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

Problem

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

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

Description

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

Input

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

Output

含$T$行，分别对每组数据作出回答。第$i$行输出相应的第$K_i$个不是完全平方数的正整数倍的数。

Problem

【PA2015】Siano

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

Description

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

Input

第一行包含两个正整数$n,m$，分别表示亩数和收割次数。
第二行包含$n$个正整数，其中第$i$个数为$a_i$，依次表示每亩种植的草的生长能力。
接下来$m$行，每行包含两个正整数$d_i,b_i$，依次描述每次收割。

Output

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