Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom7月前

12/6
21:20
计算几何

[bzoj 3170] [Tjoi 2013]松鼠聚会

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

有N个小松鼠,它们的家用一个点x,y表示,两个点的距离定义为:点(x,y)和它周围的8个点即上下左右四个点和对角的四个点,距离为1。现在N个松鼠要走到一个松鼠家去,求走过的最短距离。

Read More →

[bzoj 3170] [Tjoi 2013]松鼠聚会

@krydom7月前

12/6
21:14
并查集

[bzoj 1529] [POI2005]ska Piggy banks

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.

Read More →

[bzoj 1529] [POI2005]ska Piggy banks

@krydom7月前

12/6
21:07
暴力

[bzoj 4143] [AMPPZ2014]The Lawyer

♦♦♦♦♦♦   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]。

Read More →

[bzoj 4143] [AMPPZ2014]The Lawyer

@krydom7月前

12/6
21:04
dijkstra

[bzoj 2662] [BeiJing wc2012]冻结

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 “我要成为魔法少女!”
“那么,以灵魂为代价,你希望得到什么?”
“我要将有关魔法和奇迹的一切,封印于卡片之中„„”

在这个愿望被实现以后的世界里,人们享受着魔法卡片(SpellCard,又名符卡)带来的便捷。

现在,不需要立下契约也可以使用魔法了!你还不来试一试?
比如,我们在魔法百科全书(Encyclopedia  of  Spells)里用“freeze”作为关键字来查询,会有很多有趣的结果。
例如,我们熟知的Cirno,她的冰冻魔法当然会有对应的 SpellCard 了。 当然,更加令人惊讶的是,居然有冻结时间的魔法,Cirno 的冻青蛙比起这些来真是小巫见大巫了。
这说明之前的世界中有很多魔法少女曾许下控制时间的愿望,比如 Akemi Homura、Sakuya Izayoi、„„ 当然,在本题中我们并不是要来研究历史的,而是研究魔法的应用。

我们考虑最简单的旅行问题吧:  现在这个大陆上有 N 个城市,M 条双向的道路。城市编号为 1~N,我们在 1 号城市,需要到 N 号城市,怎样才能最快地到达呢?

这不就是最短路问题吗?我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall等算法来解决。
现在,我们一共有 K 张可以使时间变慢 50%的 SpellCard,也就是说,在通过某条路径时,我们可以选择使用一张卡片,这样,我们通过这一条道路的时间就可以减少到原先的一半。需要注意的是:
1. 在一条道路上最多只能使用一张 SpellCard。
2. 使用一张SpellCard 只在一条道路上起作用。
3. 你不必使用完所有的 SpellCard。

给定以上的信息,你的任务是:求出在可以使用这不超过 K 张时间减速的SpellCard 之情形下,从城市1 到城市N最少需要多长时间。

Read More →

[bzoj 2662] [BeiJing wc2012]冻结

@krydom7月前

12/6
20:58
暴力

[bzoj 1218] [HNOI2003]激光炸弹

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

一种新型的激光炸弹,可以摧毁一个边长为R的正方形内的所有的目标。现在地图上有n(N<=10000)个目标,用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置,每个目标都有一个价值。激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆破范围,即那个边长为R的正方形的边必须和x,y轴平行。若目标位于爆破正方形的边上,该目标将不会被摧毁。

Read More →

[bzoj 1218] [HNOI2003]激光炸弹

@krydom7月前

12/6
20:54
欧拉函数

[bzoj 2190] [SDOI2008]仪仗队

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。
   
现在,C君希望你告诉他队伍整齐时能看到的学生人数。

Read More →

[bzoj 2190] [SDOI2008]仪仗队

@krydom7月前

12/6
20:51
单调栈/队列

[bzoj 1345] [Baltic2007]序列问题Sequence

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

对于一个给定的序列a1, …, an,我们对它进行一个操作reduce(i),该操作将数列中的元素ai和ai+1用一个元素max(ai,ai+1)替代,这样得到一个比原来序列短的新序列。这一操作的代价是max(ai,ai+1)。进行n-1次该操作后,可以得到一个长度为1的序列。我们的任务是计算代价最小的reduce操作步骤,将给定的序列变成长度为1的序列。

Read More →

[bzoj 1345] [Baltic2007]序列问题Sequence