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

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

@krydom2年前

11/27
22:48
暴力

[bzoj 1603] Usaco2008Oct 打谷机

00:00/00:00

20150819214702_3Vmty  48-151023162303-50

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

 Farmer John有一个过时的打谷机(收割小麦),它需要带子来带动。发动机驱动轮1总是顺时针旋转的,用来带动转轮2,转轮2来带动转轮3,等等。一共有n(2<=n<=1000)个转轮(n-1条带子)。上面的图解描述了转轮的两种连接方式,第一种方式使得两个轮子旋转的方向相同,第二种则相反。 给出一串带子的信息: *Si—驱动轮 *Di—被动轮 *Ci—连接的类型(0=直接连接,1=交叉连接) 不幸的是,列出的信息是随即的。 作为样例,考虑上面的图解,n=4,转轮1是驱动轮,可以得知最后转轮4是逆时针旋转的。

Read More →

[bzoj 1603] Usaco2008Oct 打谷机

@krydom2年前

11/27
21:55
贪心

[bzoj 1620] Usaco2008Nov Time Management 时间管理

00:00/00:00

58ee3d6d55fbb2fb0844860c4f4a20a44623dc45  622762d0f703918f89bd0b9d533d269759eec47c

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

Ever the maturing businessman, Farmer John realizes that he must manage his time effectively. He has N jobs conveniently numbered 1..N (1 <= N <= 1,000) to accomplish (like milking the cows, cleaning the barn, mending the fences, and so on). To manage his time effectively, he has created a list of the jobs that must be finished. Job i requires a certain amount of time T_i (1 <= T_i <= 1,000) to complete and furthermore must be finished by time S_i (1 <= S_i <= 1,000,000). Farmer John starts his day at time t=0 and can only work on one job at a time until it is finished. Even a maturing businessman likes to sleep late; help Farmer John determine the latest he can start working and still finish all the jobs on time.

N个工作,每个工作其所需时间,及完成的Deadline,问要完成所有工作,最迟要什么时候开始.

Read More →

[bzoj 1620] Usaco2008Nov Time Management 时间管理

@krydom2年前

11/27
21:21
一般动规与递推 未分类

[bzoj 1600] [Usaco2008 Oct]建造栅栏

00:00/00:00

d1160924ab18972bf0868ff9e4cd7b899e510a40  a8773912b31bb051b7e33f1b347adab44aede03a (1)

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

 勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n(4<=n<=2500)的木板,他想把这块本板切成4块。这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意: *只要大木板的切割点不同就当成是不同的方案(像全排列那样),不要担心另外的特殊情况,go ahead。 *栅栏的面积要大于0. *输出保证答案在longint范围内。 *整块木板都要用完。

Read More →

[bzoj 1600] [Usaco2008 Oct]建造栅栏

@krydom2年前

10/31
21:24
一般动规与递推

[bzoj 1616] Usaco2008 Mar Cow Travelling游荡的奶牛

00:00/00:00

20130323081435407  20120201140317_JxWFX  5e2853143f1e650225c27bd865741cee

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

 奶牛们在被划分成N行M列(2 <= N <= 100; 2 <= M <= 100)的草地上游走,试图找到整块草地中最美味的牧草。Farmer John在某个时刻看见贝茜在位置 (R1, C1),恰好T (0 < T <= 15)秒后,FJ又在位置(R2, C2)与贝茜撞了正着。 FJ并不知道在这T秒内贝茜是否曾经到过(R2, C2),他能确定的只是,现在贝茜在那里。 设S为奶牛在T秒内从(R1, C1)走到(R2, C2)所能选择的路径总数,FJ希望有一个程序来帮他计算这个值。每一秒内,奶牛会水平或垂直地移动1单位距离(奶牛总是在移动,不会在某秒内停在它上一秒所在的点)。草地上的某些地方有树,自然,奶牛不能走到树所在的位置,也不会走出草地。 现在你拿到了一张整块草地的地形图,其中'.'表示平坦的草地,'*'表示挡路的树。你的任务是计算出,一头在T秒内从(R1, C1)移动到(R2, C2)的奶牛可能经过的路径有哪些。

Read More →

[bzoj 1616] Usaco2008 Mar Cow Travelling游荡的奶牛

@krydom2年前

10/31
20:30
kruskal

[bzoj 1083] SCOI2005 繁忙的都市

00:00/00:00

4175113141417511314  2903810210855431  36461786_1414432544_48Uo

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

 城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的要求: 1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来。 2. 在满足要求1的情况下,改造的道路尽量少。 3. 在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。任务:作为市规划局的你,应当作出最佳的决策,选择那些道路应当被修建。

Read More →

[bzoj 1083] SCOI2005 繁忙的都市

@krydom2年前

10/26
20:45
组合数/lucas

[bzoj 1008] HNOI2008 越狱

00:00/00:00

1-1510161I123   df60d1d243b6732156a9928a46df25db

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

 监狱有连续编号为1...N的N个房间,每个房间关押一个犯人,有M种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱

Read More →

[bzoj 1008] HNOI2008 越狱