BZOJ1913【APIO2010】信号覆盖 <极角排序+双指针>
BZOJ4069【APIO2015】巴厘岛的雕塑 < DP >
Problem
【APIO2015】巴厘岛的雕塑
TimeLimit:10Sec
MemoryLimit:64MB
Description
印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。
在这条主干道上一共有N座雕塑,为方便起见,我们把这些雕塑从1到N连续地进行标号,其中第 i 座雕塑的年龄是Yi年。为了使这条路的环境更加优美,政府想把这些雕塑分成若干组,并通过在组与组之间种上一些树,来吸引更多的游客来巴厘岛。
下面是将雕塑分组的规则:
这些雕塑必须被分为恰好X组,其中A≤X≤B,每组必须含有至少一个雕塑,每个雕塑也必须属于且只属于一个组。同一组中的所有雕塑必须位于这条路的连续一段上。
当雕塑被分好组后,对于每个组,我们首先计算出该组所有雕塑的年龄和。
计算所有年龄和按位取或的结果。我们这个值把称为这一分组的最终优美度。
请问政府能得到的最小的最终优美度是多少?
Input
输入的第一行包含三个用空格分开的整数N,A,B。
第二行包含N个用空格分开的整数Y1,Y2,⋯,YN。
Output
输出一行一个数,表示最小的最终优美度。
BZOJ4070【APIO2015】雅加达的摩天楼 <分块+最短路>
Problem
【APIO2015】雅加达的摩天楼
TimeLimit:10Sec
MemoryLimit:256MB
Description
印尼首都雅加达市有N座摩天楼,它们排列成一条直线,我们从左到右依次将它们编号为0到N−1。除了这N座摩天楼外,雅加达市没有其他摩天楼。
有M只叫做doge的神秘生物在雅加达市居住,它们的编号依次是0到M−1。编号为i的doge最初居住于编号为Bi的摩天楼。每只doge都有一种神秘的力量,使它们能够在摩天楼之间跳跃,编号为i的doge的跳跃能力为Pi(Pi>0)。
在一次跳跃中,位于摩天楼b而跳跃能力为p的doge可以跳跃到编号为b−p(如果0≤b−p<N)或b+p(如果0≤b+p<N)的摩天楼。
编号为0的doge是所有doge的首领,它有一条紧急的消息要尽快传送给编号为1的doge。
任何一个收到消息的doge有以下两个选择:
- 跳跃到其他摩天楼上
- 将消息传递给它当前所在的摩天楼上的其他doge
请帮助doge们计算将消息从0号doge传递到1号doge所需要的最少总跳跃步数,或者告诉它们消息永远不可能传递到1号doge。
Input
输入的第一行包含两个整数N和M。
接下来M行,每行包含两个整数Bi和Pi。
Output
输出一行,表示所需要的最少步数。
如果消息永远无法传递到1号doge,输出−1。
BZOJ1178【APIO2009】会议中心 <贪心+倍增>
Problem
【APIO2009】会议中心
TimeLimit:15Sec
MemoryLimit:162MB
Description
Siruseri政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很感兴趣,他们希望能够在里面举行会议。
对于一个客户而言,仅当在开会时能够独自占用整个会堂,他才会租借会堂。会议中心的销售主管认为:最好的策略应该是将会堂租借给尽可能多的客户。
显然,有可能存在不止一种满足要求的策略。 例如下面的例子。总共有4个公司。他们对租借会堂发出了请求,并提出了他们所需占用会堂的起止日期(如下表所示)。
公司 | 开始日期 | 结束日期 |
---|---|---|
公司1 | 4 | 9 |
公司2 | 9 | 11 |
公司3 | 13 | 19 |
公司4 | 10 | 17 |
上例中,最多将会堂租借给两家公司。租借策略分别是租给公司1和公司3, 或是公司2和公司3,也可以是公司1和公司4。注意会议中心一天最多租借给 一个公司,所以公司1和公司2不能同时租借会议中心,因为他们在第九天重合 了。
销售主管为了公平起见,决定按照如下的程序来确定选择何种租借策略:首先,将租借给客户数量最多的策略作为候选,将所有的公司按照他们发出请求的 顺序编号。对于候选策略,将策略中的每家公司的编号按升序排列。最后,选出其中字典序最小的候选策略作为最终的策略。
例中,会堂最终将被租借给公司1和公司3:3个候选策略是 {(1,3),(2,3),(1,4)},而在字典序中(1,3)<(1,4)<(2,3)。
你的任务是帮助销售主管确定应该将会堂租借给哪些公司。
Input
第一行有一个整数N(N≤2×105),表示发出租借会堂申请的公司的个数。
第2到第N+1行每行有2个整数。第i+1行的整数表示第i家公司申请租借的起始和终止日期。
对于每个公司的申请,起始日期为不小于1的整数,终止日期为不大于109的整数。
Output
输出的第一行应有一个整数M,表示最多可以租借给多少家公司。
第二行应列出M个数,表示最终将会堂租借给哪些公司。
【APIO2011】方格染色 <带权并查集>
Problem
【APIO2011】方格染色
TimeLimit:20Sec
MemoryLimit:256MB
Description
Sam和他的妹妹Sara有一个包含n×m个方格的表格。她们想要将其的每个方格都染成红色或蓝色。
出于个人喜好,他们想要表格中每个2×2的方形区域都包含奇数个(1个或3个)红色方格。 可是昨天晚上,有人已经给表格中的一些方格染上了颜色!
现在Sam和Sara非常生气。不过,他们想要知道是否可能给剩下的方格染上颜色,使得整个表格仍然满足她们的要求。
如果可能的话,满足他们要求的染色方案数有多少呢?
Input
输入的第一行包含三个整数n, m和k,分别代表表格的行数、列数和已被染色的方格数目。
之后的k行描述已被染色的方格。其中第i行包含三个整数xi, yi和ci,分别代表第i个已被染色的方格的行编号、列编号和颜色。ci为1表示方格被染成红色,ci为0表示方格被染成蓝色。
Output
输出一个整数,表示可能的染色方案数目W模109得到的值。
BZOJ5180【Baltic2016】Cities <斯坦纳树>
BZOJ2809【APIO2012】Dispatching <可并堆>
Problem
【APIO2012】Dispatching
TimeLimit:10Sec
MemoryLimit:128MB
Description
在一个忍者的帮派里,一些忍者们被选中派遣给顾客,然后依据自己的工作获取报偿。
在这个帮派里,有一名忍者被称之为Master。除了Master以外,每名忍者都有且仅有一个上级。为保密,同时增强忍者们的领导力,所有与他们工作相关的指令总是由上级发送给他的直接下属,而不允许通过其他的方式发送。
现在你要招募一批忍者,并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水,同时使得支付的薪水总额不超过你的预算。另外,为了发送指令,你需要选择一名忍者作为管理者,要求这个管理者可以向所有被派遣的忍者发送指令,在发送指令时,任何忍者(不管是否被派遣)都可以作为消息的传递人。管理者自己可以被派遣,也可以不被派遣。当然,如果管理者没有被排遣,就不需要支付管理者的薪水。你的目标是在预算内使顾客的满意度最大。
这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平,其中每个忍者的领导力水平也是一定的。
写一个程序,给定每一个忍者i的上级Bi,薪水Ci,领导力Li,以及支付给忍者们的薪水总预算M,输出在预算内满足上述要求时顾客满意度的最大值。
Input
从标准输入读入数据。
第一行包含两个整数N和M,其中N表示忍者的个数,M表示薪水的总预算。
接下来N行描述忍者们的上级、薪水以及领导力。其中的第i行包含三个整数Bi,Ci,Li分别表示第i个忍者的上级,薪水以及领导力。Master满足Bi=0,并且每一个忍者的老板的编号一定小于自己的编号。
Output
输出一个数,表示在预算内顾客的满意度的最大值。
BZOJ5251【2018多省省队联测】劈配 <网络流>
Problem
【2018多省省队联测】劈配
TimeLimit:10Sec
MemoryLimit:512MB
Description
一年一度的综艺节目《中国新代码》又开始了。Zayid从小就梦想成为一名程序员,他觉得这是一个展示自己的舞台,于是他毫不犹豫地报名了。
轻车熟路的Zayid顺利地通过了海选,接下来的环节是导师盲选,这一阶段的规则是这样的:
总共n名参赛选手(编号从1至n)每人写出一份代码并介绍自己的梦想。接着由所有导师对这些选手进行排名。
为了避免后续的麻烦,规定不存在排名并列的情况。
同时,每名选手都将独立地填写一份志愿表,来对总共m位导师(编号从1至m)作出评价。志愿表上包含了共m档志愿。对于每一档志愿,选手被允许填写最多C位导师,每位导师最多被每位选手填写一次(放弃某些导师也是被允许的)。
在双方的工作都完成后,进行录取工作。每位导师都有自己战队的人数上限,这意味着可能有部分选手的较高志愿、甚至是全部志愿无法得到满足。
节目组对“前i名的录取结果最优”作出如下定义:
- 前1名的录取结果最优,当且仅当第1名被其最高非空志愿录取(特别地,如果第1名没有填写志愿表,那么该选手出局)。
- 前i名的录取结果最优,当且仅当在前i−1名的录取结果最优的情况下:第i名被其理论可能的最高志愿录取(特别地,如果第i名没有填写志愿表、或其所有志愿中的导师战队均已满员,那么该选手出局)。
如果一种方案满足“前n名的录取结果最优”,那么我们可以简称这种方案是最优的。
举例而言,2位导师T老师、F老师的战队人数上限分别都是1人;2位选手Zayid、DuckD分列第1、2名。那么下面3种志愿表及其对应的最优录取结果如表中所示:
可以证明,对于上面的志愿表,对应的方案都是唯一的最优录取结果。
每个人都有一个自己的理想值si,表示第i位同学希望自己被第si或更高的志愿录取,如果没有,那么他就会非常沮丧。
现在,所有选手的志愿表和排名都已公示。巧合的是,每位选手的排名都恰好与它们的编号相同。
对于每一位选手,Zayid都想知道下面两个问题的答案:
- 在最优的录取方案中,他会被第几志愿录取。
- 在其他选手相对排名不变的情况下,至少上升多少名才能使得他不沮丧。
作为《中国新代码》的实力派代码手,Zayid当然轻松地解决了这个问题。不过他还是想请你再算一遍,来检验自己计算的正确性。
Input
每个测试点包含多组测试数据,第一行2个用空格隔开的非负整数T,C,分别表示数据组数、每档志愿最多允许填写的导师数目。
接下来依次描述每组数据,对于每组数据:
- 第1行两个用空格隔开的正整数n,m。n,m分别表示选手的数量、导师的数量。
- 第2行m个用空格隔开的正整数:其中第i个整数为bi。Bi表示编号为i的导师战队人数的上限。
- 第3行至第n+2行,每行m个用空格隔开的非负整数:其中第i+2行左起第j个数为ai,j
- ai,j表示编号为i的选手将编号为j的导师编排在了第ai,j志愿。特别地,如果ai,j=0,则表示该选手没有将该导师填入志愿表。
- 在这一部分,保证每行中不存在某一个正数出现超过C次(0可能出现超过C次),同时保证所有ai,j≤m。
- 第n+3行n个用空格隔开的正整数,其中第i个整数为Si
- Si表示编号为i的选手的理想值。
- 在这一部分,保证Si≤m。
Output
按顺序输出每组数据的答案。对于每组数据,输出2行:
- 第1行输出n个用空格隔开的正整数,其中第i个整数的意义为:
- 在最优的录取方案中,编号为i的选手会被该档志愿录取。
- 特别地,如果该选手出局,则这个数为m+1。
- 第2行输出n个用空格隔开的非负整数,其中第i个整数的意义为:
- 使编号为i的选手不沮丧,最少需要让他上升的排名数。
- 特别地,如果该选手一定会沮丧,则这个数为i。