10
7
2015
0

3073: [Pa2011]Journeys

3073: [Pa2011]Journeys

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 32  Solved: 17
[Submit][Status][Discuss]

Description

 
 
Seter建造了一个很大的星球,他准备建造N个国家和无数双向道路。N个国家很快建造好了,用1..N编号,但是他发现道路实在太多了,他要一条条建简直是不可能的!于是他以如下方式建造道路:(a,b),(c,d)表示,对于任意两个国家x,y,如果a<=x<=b,c<=y<=d,那么在xy之间建造一条道路。Seter保证一条道路不会修建两次,也保证不会有一个国家与自己之间有道路。
Seter好不容易建好了所有道路,他现在在位于P号的首都。Seter想知道P号国家到任意一个国家最少需要经过几条道路。当然,Seter保证P号国家能到任意一个国家。
 
 

	
注意:可能有重边

Category: BZOJ题解 | Tags:
9
29
2015
0

4151: [AMPPZ2014]The Cave

4151: [AMPPZ2014]The Cave

Time Limit: 5 Sec  Memory Limit: 256 MBSec  Special Judge
Submit: 101  Solved: 45
[Submit][Status][Discuss]

Description

给定一棵有n个节点的树,相邻两点之间的距离为1。
请找到一个点x,使其满足所有m条限制,其中第i条限制为dist(x,a[i])+dist(x,b[i])<=d[i]。
 

 

Category: BZOJ题解 | Tags:
9
29
2015
0

4149: [AMPPZ2014]Global Warming

4149: [AMPPZ2014]Global Warming

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 112  Solved: 38
[Submit][Status][Discuss]

Description

给定一个序列a[1],a[2],...,a[n]。请从中选出一段连续子序列,使得该区间最小值唯一、最大值也唯一。
输出选出的子序列的长度的最大值以及取到最大值时左端点的最小值。
 

 

Category: BZOJ题解 | Tags:
9
28
2015
0

4144: [AMPPZ2014]Petrol

4144: [AMPPZ2014]Petrol

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 266  Solved: 99
[Submit][Status][Discuss]

Description

给定一个n个点、m条边的带权无向图,其中有s个点是加油站。
每辆车都有一个油量上限b,即每次行走距离不能超过b,但在加油站可以补满。
q次询问,每次给出x,y,b,表示出发点是x,终点是y,油量上限为b,且保证x点和y点都是加油站,请回答能否从x走到y。
 

 

Category: BZOJ题解 | Tags:
9
28
2015
0

4145: [AMPPZ2014]The Prices

4145: [AMPPZ2014]The Prices

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 175  Solved: 117
[Submit][Status][Discuss]

Description

你要购买m种物品各一件,一共有n家商店,你到第i家商店的路费为d[i],在第i家商店购买第j种物品的费用为c[i][j],
求最小总费用。
 
 
 

 

Category: BZOJ题解 | Tags:
9
28
2015
0

4152: [AMPPZ2014]The Captain

4152: [AMPPZ2014]The Captain

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 342  Solved: 128
[Submit][Status][Discuss]

Description

给定平面上的n个点,定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|),求从1号点走到n号点的最小费用。

 

Category: BZOJ题解 | Tags:
9
27
2015
0

4143: [AMPPZ2014]The Lawyer

4143: [AMPPZ2014]The Lawyer

Time Limit: 10 Sec  Memory Limit: 256 MBSec  Special Judge
Submit: 345  Solved: 189
[Submit][Status][Discuss]

Description

Byteasar要制订m天的会议计划,一共有n场会议,第i场会议开始于第d[i]天的第a[i]秒,结束于第d[i]天的第b[i]秒。
对于每一天,请找出这一天的两场会议i,j,使得它们不冲突,即不存在一个数k同时满足a[i]<=k<=b[i]以及a[j]<=k<=b[j]。
 

 

Category: BZOJ题解 | Tags:
9
25
2015
4

4260: Codechef REBXOR

4260: Codechef REBXOR

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 89  Solved: 36
[Submit][Status][Discuss]

Description

 

Category: BZOJ题解 | Tags:
9
24
2015
0

3709: [PA2014]Bohater

3709: [PA2014]Bohater

Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 648  Solved: 218
[Submit][Status][Discuss]

Description

在一款电脑游戏中,你需要打败n只怪物(从1到n编号)。为了打败第i只怪物,你需要消耗d[i]点生命值,但怪物死后会掉落血药,使你恢复a[i]点生命值。任何时候你的生命值都不能降到0(或0以下)。请问是否存在一种打怪顺序,使得你可以打完这n只怪物而不死掉

Category: BZOJ题解 | Tags:
9
23
2015
0

3670: [Noi2014]动物园

3670: [Noi2014]动物园

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 1206  Solved: 646
[Submit][Status][Discuss]

Description

近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决定开设算法班,让动物们学习算法。

某天,园长给动物们讲解KMP算法。

园长:“对于一个字符串S,它的长度为L。我们可以在O(L)的时间内,求出一个名为next的数组。有谁预习了next数组的含义吗?”

熊猫:“对于字符串S的前i个字符构成的子串,既是它的后缀又是它的前缀的字符串中(它本身除外),最长的长度记作next[i]。”

园长:“非常好!那你能举个例子吗?”

熊猫:“例S为abcababc,则next[5]=2。因为S的前5个字符为abcabab既是它的后缀又是它的前缀,并且找不到一个更长的字符串满足这个性质。同理,还可得出next[1] = next[2] = next[3] = 0,next[4] = next[6] = 1,next[7] = 2,next[8] = 3。”

园长表扬了认真预习的熊猫同学。随后,他详细讲解了如何在O(L)的时间内求出next数组。

下课前,园长提出了一个问题:“KMP算法只能求出next数组。我现在希望求出一个更强大num数组一一对于字符串S的前i个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作num[i]。例如S为aaaaa,则num[4] = 2。这是因为S的前4个字符为aaaa,其中aaa都满足性质‘既是后缀又是前缀’,同时保证这个后缀与这个前缀不重叠。而aaa虽然满足性质‘既是后缀又是前缀’,但遗憾的是这个后缀与这个前缀重叠了,所以不能计算在内。同理,num[1] = 0,num[2] = num[3] = 1,num[5] = 2。”

最后,园长给出了奖励条件,第一个做对的同学奖励巧克力一盒。听了这句话,睡了一节课的企鹅立刻就醒过来了!但企鹅并不会做这道题,于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出num数组呢?

特别地,为了避免大量的输出,你不需要输出num[i]分别是多少,你只需要输出对1,000,000,007取模的结果即可。

Category: BZOJ题解 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com