NIRVANA

Problem

FRBSUM

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

Description

数集$S$的$\mathrm{Forbidden\;Sum}$定义为无法用$S$的某个子集（可以为空）的和表示的最小的非负整数。
例如，$S={1,1,3,7}$，则它的子集和中包含$0(S'=\emptyset)$，$1(S'={1})$，$2(S'={1,1})$，$3(S'={3})$，$4(S'={1,3})$，$5(S'={1,1,3})$，但是它无法得到$6$。因此$S$的$\mathrm{Forbidden\;Sum}$为$6$。
给定一个序列$A$，你的任务是回答该数列的一些子区间所形成的数集的$\mathrm{Forbidden\;Sum}$是多少。

Input

输入数据的第一行包含一个整数$N$，表示序列的长度。
接下来一行包含$N$个数，表示给定的序列$A$（从$1$标号）。
接下来一行包含一个整数$M$，表示询问的组数。
接下来$M$行，每行一对整数，表示一组询问。

Ouput

对于每组询问，输出一行表示对应的答案。

Problem

【APIO2010】信号覆盖

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

Description

Input

输入第一行包含一个正整数$n$，表示房子的总数。接下来有$n$行，分别表示每一个房子的位置。对于，$i=1,2,\cdots,n$第$i$个房子的坐标用一对整数$x_i$和$y_i$来表示，中间用空格隔开。

Output

输出文件包含一个实数，表示平均有多少个房子被信号所覆盖，需保证输出结果与精确值的绝对误差不超过$0.01$。

Problem

【APIO2015】巴厘岛的雕塑

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

Description

印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。
在这条主干道上一共有$N$座雕塑，为方便起见，我们把这些雕塑从$1$到$N$连续地进行标号，其中第 i 座雕塑的年龄是$Y_i$年。为了使这条路的环境更加优美，政府想把这些雕塑分成若干组，并通过在组与组之间种上一些树，来吸引更多的游客来巴厘岛。
下面是将雕塑分组的规则：
这些雕塑必须被分为恰好$X$组，其中$A\le X\le B$，每组必须含有至少一个雕塑，每个雕塑也必须属于且只属于一个组。同一组中的所有雕塑必须位于这条路的连续一段上。
当雕塑被分好组后，对于每个组，我们首先计算出该组所有雕塑的年龄和。
计算所有年龄和按位取或的结果。我们这个值把称为这一分组的最终优美度。
请问政府能得到的最小的最终优美度是多少?

Input

输入的第一行包含三个用空格分开的整数$N,A,B$。
第二行包含$N$个用空格分开的整数$Y_1,Y_2,\cdots,Y_N$。

Output

输出一行一个数，表示最小的最终优美度。

Problem

【APIO2015】雅加达的摩天楼

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

Description

印尼首都雅加达市有$N$座摩天楼，它们排列成一条直线，我们从左到右依次将它们编号为$0$到$N-1$。除了这$N$座摩天楼外，雅加达市没有其他摩天楼。
有$M$只叫做$\mathrm{doge}$的神秘生物在雅加达市居住，它们的编号依次是$0$到$M-1$。编号为$i$的$\mathrm{doge}$最初居住于编号为$B_i$的摩天楼。每只$\mathrm{doge}$都有一种神秘的力量，使它们能够在摩天楼之间跳跃，编号为$i$的$\mathrm{doge}$的跳跃能力为$P_i\;(P_i>0)$。
在一次跳跃中，位于摩天楼$b$而跳跃能力为$p$的$\mathrm{doge}$可以跳跃到编号为$b-p$（如果$0\le b-p<N$）或$b+p$（如果$0\le b+p<N$）的摩天楼。
编号为$0$的$\mathrm{doge}$是所有$\mathrm{doge}$的首领，它有一条紧急的消息要尽快传送给编号为$1$的$\mathrm{doge}$。
任何一个收到消息的$\mathrm{doge}$有以下两个选择:

• 跳跃到其他摩天楼上
• 将消息传递给它当前所在的摩天楼上的其他$\mathrm{doge}$

请帮助$\mathrm{doge}$们计算将消息从$0$号$\mathrm{doge}$传递到$1$号$\mathrm{doge}$所需要的最少总跳跃步数，或者告诉它们消息永远不可能传递到$1$号$\mathrm{doge}$。

Input

输入的第一行包含两个整数$N$和$M$。
接下来$M$行，每行包含两个整数$B_i$和$P_i$。

Output

输出一行，表示所需要的最少步数。
如果消息永远无法传递到$1$号$\mathrm{doge}$，输出$-1$。

Problem

【APIO2009】会议中心

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

Description

$\mathrm{Siruseri}$政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很感兴趣，他们希望能够在里面举行会议。
对于一个客户而言，仅当在开会时能够独自占用整个会堂，他才会租借会堂。会议中心的销售主管认为：最好的策略应该是将会堂租借给尽可能多的客户。
显然，有可能存在不止一种满足要求的策略。 例如下面的例子。总共有$4$个公司。他们对租借会堂发出了请求，并提出了他们所需占用会堂的起止日期（如下表所示）。

上例中，最多将会堂租借给两家公司。租借策略分别是租给$公司1$和$公司3$， 或是$公司2$和$公司3$，也可以是$公司1$和$公司4$。注意会议中心一天最多租借给 一个公司，所以$公司1$和$公司2$不能同时租借会议中心，因为他们在第九天重合 了。
销售主管为了公平起见，决定按照如下的程序来确定选择何种租借策略：首先，将租借给客户数量最多的策略作为候选，将所有的公司按照他们发出请求的 顺序编号。对于候选策略，将策略中的每家公司的编号按升序排列。最后，选出其中字典序最小的候选策略作为最终的策略。
例中，会堂最终将被租借给$公司1$和$公司3$：$3$个候选策略是 $\lbrace(1,3),(2,3),(1,4)\rbrace$，而在字典序中$(1,3)<(1,4)<(2,3)$。
你的任务是帮助销售主管确定应该将会堂租借给哪些公司。

Input

第一行有一个整数$N\;(N\le2\times10^5)$，表示发出租借会堂申请的公司的个数。
第$2$到第$N+1$行每行有$2$个整数。第$i+1$行的整数表示第$i$家公司申请租借的起始和终止日期。
对于每个公司的申请，起始日期为不小于$1$的整数，终止日期为不大于$10^9$的整数。

Output

输出的第一行应有一个整数$M$，表示最多可以租借给多少家公司。
第二行应列出$M$个数，表示最终将会堂租借给哪些公司。

Problem

【APIO2011】方格染色

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

Description

$\mathrm{Sam}$和他的妹妹$\mathrm{Sara}$有一个包含$n\times m$个方格的表格。她们想要将其的每个方格都染成红色或蓝色。
出于个人喜好，他们想要表格中每个$2\times 2$的方形区域都包含奇数个（$1$个或$3$个）红色方格。 可是昨天晚上，有人已经给表格中的一些方格染上了颜色！
现在$\mathrm{Sam}$和$\mathrm{Sara}$非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格仍然满足她们的要求。
如果可能的话，满足他们要求的染色方案数有多少呢？

Input

输入的第一行包含三个整数$n$, $m$和$k$，分别代表表格的行数、列数和已被染色的方格数目。
之后的$k$行描述已被染色的方格。其中第$i$行包含三个整数$x_i$, $y_i$和$c_i$，分别代表第$i$个已被染色的方格的行编号、列编号和颜色。$c_i$为$1$表示方格被染成红色，$c_i$为$0$表示方格被染成蓝色。

Output

输出一个整数，表示可能的染色方案数目$W$模$10^9$得到的值。

Problem

【Baltic2016】Cities

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

Description

给定$n$个点，$m$条双向边的图，其中有$k$个点是重要的，每条边都有一定的长度。
现在要你选定一些边来构成一个图，要使得$k$个重要的点相互连通，求边的长度和的最小值。

Input

共$m+2$行
第$1$行读入$n,k,m$，表示$n$个点，$k$个重要的点，$m$条边
第$2$行读入$k$个重要点的编号
第$3$至第$m+2$行，每行包括$3$个数字$a,b,c$，表示有一条从$a$到$b$长度为$c$的双向路径

Output

共$1$行，即最小长度和

Problem

【APIO2012】Dispatching

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

Description

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。
在这个帮派里，有一名忍者被称之为$\mathrm{Master}$。除了$\mathrm{Master}$以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。
现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，就不需要支付管理者的薪水。你的目标是在预算内使顾客的满意度最大。
这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。
写一个程序，给定每一个忍者$i$的上级$B_i$，薪水$C_i$，领导力$L_i$，以及支付给忍者们的薪水总预算$M$，输出在预算内满足上述要求时顾客满意度的最大值。

Input

从标准输入读入数据。
第一行包含两个整数$N$和$M$，其中$N$表示忍者的个数，$M$表示薪水的总预算。
接下来$N$行描述忍者们的上级、薪水以及领导力。其中的第$i$行包含三个整数$B_i,C_i,L_i$分别表示第$i$个忍者的上级，薪水以及领导力。$\mathrm{Master}$满足$B_i=0$，并且每一个忍者的老板的编号一定小于自己的编号。

Output

输出一个数，表示在预算内顾客的满意度的最大值。

Problem

【2018多省省队联测】劈配

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

Description

一年一度的综艺节目《中国新代码》又开始了。$\mathrm{Zayid}$从小就梦想成为一名程序员，他觉得这是一个展示自己的舞台，于是他毫不犹豫地报名了。
轻车熟路的$\mathrm{Zayid}$顺利地通过了海选，接下来的环节是导师盲选，这一阶段的规则是这样的：
总共$n$名参赛选手（编号从$1$至$n$）每人写出一份代码并介绍自己的梦想。接着由所有导师对这些选手进行排名。
为了避免后续的麻烦，规定不存在排名并列的情况。
同时，每名选手都将独立地填写一份志愿表，来对总共$m$位导师（编号从$1$至$m$）作出评价。志愿表上包含了共$m$档志愿。对于每一档志愿，选手被允许填写最多$C$位导师，每位导师最多被每位选手填写一次（放弃某些导师也是被允许的）。
在双方的工作都完成后，进行录取工作。每位导师都有自己战队的人数上限，这意味着可能有部分选手的较高志愿、甚至是全部志愿无法得到满足。
节目组对“前$i$名的录取结果最优”作出如下定义：

• 前$1$名的录取结果最优，当且仅当第$1$名被其最高非空志愿录取（特别地，如果第$1$名没有填写志愿表，那么该选手出局）。
• 前$i$名的录取结果最优，当且仅当在前$i-1$名的录取结果最优的情况下：第$i$名被其理论可能的最高志愿录取（特别地，如果第i名没有填写志愿表、或其所有志愿中的导师战队均已满员，那么该选手出局）。

如果一种方案满足“前$n$名的录取结果最优”，那么我们可以简称这种方案是最优的。
举例而言，$2$位导师$T$老师、$F$老师的战队人数上限分别都是$1$人；$2$位选手$\mathrm{Zayid}$、$\mathrm{DuckD}$分列第$1、2$名。那么下面$3$种志愿表及其对应的最优录取结果如表中所示：

可以证明，对于上面的志愿表，对应的方案都是唯一的最优录取结果。
每个人都有一个自己的理想值$s_i$，表示第$i$位同学希望自己被第$s_i$或更高的志愿录取，如果没有，那么他就会非常沮丧。
现在，所有选手的志愿表和排名都已公示。巧合的是，每位选手的排名都恰好与它们的编号相同。
对于每一位选手，$\mathrm{Zayid}$都想知道下面两个问题的答案：

• 在最优的录取方案中，他会被第几志愿录取。
• 在其他选手相对排名不变的情况下，至少上升多少名才能使得他不沮丧。

作为《中国新代码》的实力派代码手，$\mathrm{Zayid}$当然轻松地解决了这个问题。不过他还是想请你再算一遍，来检验自己计算的正确性。

Input

每个测试点包含多组测试数据，第一行$2$个用空格隔开的非负整数$T,C$，分别表示数据组数、每档志愿最多允许填写的导师数目。
接下来依次描述每组数据，对于每组数据：

• 第$1$行两个用空格隔开的正整数$n,m$。$n,m$分别表示选手的数量、导师的数量。
• 第$2$行$m$个用空格隔开的正整数：其中第$i$个整数为$b_i$。$B_i$表示编号为$i$的导师战队人数的上限。
• 第$3$行至第$n+2$行，每行$m$个用空格隔开的非负整数：其中第$i+2$行左起第$j$个数为$a_{i,j}$
  • $a_{i,j}$表示编号为$i$的选手将编号为$j$的导师编排在了第$a_{i,j}$志愿。特别地，如果$a_{i,j}=0$，则表示该选手没有将该导师填入志愿表。
  • 在这一部分，保证每行中不存在某一个正数出现超过$C$次（$0$可能出现超过$C$次），同时保证所有$a_{i,j}\le m$。
• 第$n+3$行$n$个用空格隔开的正整数，其中第$i$个整数为$S_i$
  • $S_i$表示编号为$i$的选手的理想值。
  • 在这一部分，保证$S_i\le m$。

Output

按顺序输出每组数据的答案。对于每组数据，输出$2$行：

• 第$1$行输出$n$个用空格隔开的正整数，其中第$i$个整数的意义为：
  • 在最优的录取方案中，编号为$i$的选手会被该档志愿录取。
  • 特别地，如果该选手出局，则这个数为$m+1$。
• 第$2$行输出$n$个用空格隔开的非负整数，其中第$i$个整数的意义为：
  • 使编号为$i$的选手不沮丧，最少需要让他上升的排名数。
  • 特别地，如果该选手一定会沮丧，则这个数为$i$。

Problem

【APIO2010】特别行动队

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

Description

Input

Output