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

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

@krydom7月前

12/11
16:36
线段树

[bzoj 3747] [POI2015]Kinoman

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

共有m部电影,编号为1~m,第i部电影的好看值为w[i]。
在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第f[i]部。
你可以选择l,r(1<=l<=r<=n),并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次,你会感到无聊,于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。

Read More →

[bzoj 3747] [POI2015]Kinoman

@krydom7月前

12/11
15:19
状压动规

[bzoj 4057] [Cerc2012]Kingdoms

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

有一些王国陷入了一系列的经济危机。在很多年以前,他们私底下互相借了许多钱。现在,随着他们的负债被揭发,王国的崩溃不可避免地发生了……现在有n个王国,对于每对王国A和B,A欠B的钱被记为d_AB(我们假设有d_BA=-d_AB成立)。如果一个王国入不敷出(即需要支付超过所能获得的钱),它就可能破产。每当一个王国破产,与它相关的所有债务关系都会被去除,无论是正是负。而王国们的破产不是一瞬间完成的,而是第一个王国破产后,接下来可能破产的王国再继续破产,直到剩下的王国经济都是稳定的。不同的结局将取决于谁先破产,尤其是有的结局只会留下一个王国。请你计算,对于每个王国,是否存在一种结局使得该王国是唯一的幸存者。

Read More →

[bzoj 4057] [Cerc2012]Kingdoms

@krydom7月前

12/11
14:35
暴力

[bzoj 4063] [Cerc2012]Darts

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

考虑一个扔飞镖的游戏。板子由十个环组成,半径分别为20, 40, 60, 80, 100, 120, 140, 160, 180和200(单位:mm),均以原点为中心。每次投掷的得分取决于飞镖所击中的位置。如果包含飞镖的最小环(可以在圆上)的半径是20 * (11 - p),则得分是p。不在最外环以内的点不得分。你的任务是计算n次投掷之后的得分。

Read More →

[bzoj 4063] [Cerc2012]Darts

@krydom7月前

12/11
13:44
暴力

[bzoj 4059] [Cerc2012]Non-boring sequences

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

 我们害怕把这道题题面搞得太无聊了,所以我们决定让这题超短。一个序列被称为是不无聊的,仅当它的每个连续子序列存在一个独一无二的数字,即每个子序列里至少存在一个数字只出现一次。给定一个整数序列,请你判断它是不是不无聊的。

Read More →

[bzoj 4059] [Cerc2012]Non-boring sequences

@krydom7月前

12/11
11:18
背包动规

[bzoj 4247] 挂饰

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

JOI君有N个装在手机上的挂饰,编号为1...N。 JOI君可以将其中的一些装在手机上。
JOI君的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上,要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有1个。
此外,每个挂件有一个安装时会获得的喜悦值,用一个整数来表示。如果JOI君很讨厌某个挂饰,那么这个挂饰的喜悦值就是一个负数。
JOI君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰,而且一个都不挂也是可以的。

Read More →

[bzoj 4247] 挂饰

@krydom7月前

12/9
20:41
并查集

[bzoj 4320] ShangHai2006 Homework

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

1:在人物集合 S 中加入一个新的程序员,其代号为 X,保证 X 在当前集合中不存在。
  2:在当前的人物集合中询问程序员的mod Y 最小的值。 (为什么统计这个?因为拯救
过世界的人太多了,只能取模)

Read More →

[bzoj 4320] ShangHai2006 Homework

@krydom7月前

12/7
18:24
一般动规与递推

[bzoj 3892] [Usaco2014 Dec]Marathon

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

Unhappy with the poor health of his cows, Farmer John enrolls them in an assortment of different physical fitness activities. His prize cow Bessie is enrolled in a running class, where she is eventually expected to run a marathon through the downtown area of the city near Farmer John's farm! The marathon course consists of N checkpoints (3 <= N <= 500) to be visited in sequence, where checkpoint 1 is the starting location and checkpoint N is the finish. Bessie is supposed to visit all of these checkpoints one by one, but being the lazy cow she is, she decides that she will skip up to K checkpoints (K < N) in order to shorten her total journey. She cannot skip checkpoints 1 or N, however, since that would be too noticeable. Please help Bessie find the minimum distance that she has to run if she can skip up to K checkpoints. Since the course is set in a downtown area with a grid of streets, the distance between two checkpoints at locations (x1, y1) and (x2, y2) is given by |x1-x2| + |y1-y2|.

在二维平面上有N个点,从(x1,y1)到(x2,y2)的代价为|x1-x2|+|y1-y2|。
求从1号点出发,按从1到N的顺序依次到达每个点的最小总代价。
你有K次机会可以跳过某个点,不允许跳过1号点或N号点。

Read More →

[bzoj 3892] [Usaco2014 Dec]Marathon