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

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

@krydom2年前

09/12
23:56
kruskal

Usaco2004Dec Bad Cowtractors [bzoj 3390 poj 2377]

00:00/00:00

u=3692212660,1094370080&fm=21&gp=0   93d6b72bd40735fa9b8875329e510fb30e24080a

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

    奶牛贝茜被雇去建设N(2≤N≤1000)个牛棚间的互联网.她已经勘探出M(1≤M≤20000)条可建的线路,每条线路连接两个牛棚,而且会苞费C(1≤C≤100000).农夫约翰吝啬得很,他希望建设费用最少甚至他都不想给贝茜工钱. 贝茜得知工钱要告吹,决定报复.她打算选择建一些线路,把所有牛棚连接在一起,让约翰花费最大.但是她不能造出环来,这样约翰就会发现.

Read More →

Usaco2004Dec Bad Cowtractors [bzoj 3390 poj 2377]

@krydom2年前

09/12
19:51
bfs

[bzoj 3392] Usaco2005Feb Part Acquisition 交易

00:00/00:00

20140811133326_yLWWZ   6-121225103Z5

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

     奶牛们接到了寻找一种新型挤奶机的任务,为此它们准备依次经过N(1≤N≤50000)颗行星,在行星上进行交易.为了方便,奶牛们已经给可能出现的K(1≤K≤1000)种货物进行了由1到K的标号.由于这些行星都不是十分发达.没有流通的货币,所以在每个市场里都只能用固定的一种货物去换取另一种货物.    奶牛们带着一种上好的饲料从地球出发,希望进行最少的交易,最终得到所需要的机器.饲料的标号为1,所需要的机器的标号为K.如果任务无法完成,输出-1.

Read More →

[bzoj 3392] Usaco2005Feb Part Acquisition 交易

@krydom2年前

09/6
01:05
贪心

[bzoj 1680] Usaco2005Mar Yogurt factory

00:00/00:00

c788fc759168cab817d66e240f72b1c2   1Z253A33-1

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

The cows have purchased a yogurt factory that makes world-famous Yucky Yogurt. Over the next N (1 <= N <= 10,000) weeks, the price of milk and labor will fluctuate weekly such that it will cost the company C_i (1 <= C_i <= 5,000) cents to produce one unit of yogurt in week i. Yucky's factory, being well-designed, can produce arbitrarily many units of yogurt each week. Yucky Yogurt owns a warehouse that can store unused yogurt at a constant fee of S (1 <= S <= 100) cents per unit of yogurt per week. Read More →

[bzoj 1680] Usaco2005Mar Yogurt factory

@krydom2年前

09/5
23:49
单调栈/队列

[bzoj 1628 1683] Usaco2007Demo City skyline

00:00/00:00

0b1f4be80235c44aa8527d3968465a9df182e4109f8b6c1214dd809df428585b

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

The best part of the day for Farmer John’s cows is when the sun sets. They can see the skyline of the distant city. Bessie wonders how many buildings the city has. Write a program that assists the cows in calculating the minimum number of buildings in the city, given a profile of its skyline. Read More →

[bzoj 1628 1683] Usaco2007Demo City skyline

@krydom2年前

09/5
22:42
一般动规与递推

Usaco2007Jan Running贝茜的晨练计划 [bzoj 1613]

00:00/00:00

10202265372667385350_600x600_220  3020385595298295510_500x707_220  2635113833012388348_500x625_220

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

 奶牛们打算通过锻炼来培养自己的运动细胞,作为其中的一员,贝茜选择的运动方式是每天进行N(1 <= N <= 10,000)分钟的晨跑。在每分钟的开始,贝茜会选择下一分钟是用来跑步还是休息。 贝茜的体力限制了她跑步的距离。更具体地,如果贝茜选择在第i分钟内跑步,她可以在这一分钟内跑D_i(1 <= D_i <= 1,000)米,并且她的疲劳度会增加 1。不过,无论何时贝茜的疲劳度都不能超过M(1 <= M <= 500)。如果贝茜选择休息,那么她的疲劳度就会每分钟减少1,但她必须休息到疲劳度恢复到0为止。

Read More →

Usaco2007Jan Running贝茜的晨练计划 [bzoj 1613]

@krydom2年前

08/25
19:31
spfa

[bzoj 2015] Usaco2010Feb Chocolate Giving

00:00/00:00

8609fe1f3a292df53e1a0e37bf315c6035a8731a   e1fe9925bc315c604b48427d8db1cb1348547746

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

 Farmer John有B头奶牛(1<=B<=25000),有N(2*B<=N<=50000)个农场,编号1-N,有M(N-1<=M<=100000)条双向边,第i条边连接农场R_i和S_i(1<=R_i<=N;1<=S_i<=N),该边的长度是L_i(1<=L_i<=2000)。居住在农场P_i的奶牛A(1<=P_i<=N),它想送一份新年礼物给居住在农场Q_i(1<=Q_i<=N)的奶牛B,但是奶牛A必须先到FJ(居住在编号1的农场)那里取礼物,然后再送给奶牛B。你的任务是:奶牛A至少需要走多远的路程?

Read More →

[bzoj 2015] Usaco2010Feb Chocolate Giving

@krydom2年前

08/25
18:00
其他算法

[bzoj 1637] Usaco2007Mar Balanced Lineup

00:00/00:00

e8d9ad2b44f89fb3023bf68f   0cf26a92127176702f9c77b69b2e025f

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

 Farmer John 决定给他的奶牛们照一张合影,他让 N (1 ≤ N ≤ 50,000) 头奶牛站成一条直线,每头牛都有它的坐标(范围: 0..1,000,000,000)和种族(0或1)。 一直以来 Farmer John 总是喜欢做一些非凡的事,当然这次照相也不例外。他只给一部分牛照相,并且这一组牛的阵容必须是“平衡的”。平衡的阵容,指的是在一组牛中,种族0和种族1的牛的数量相等。 请算出最广阔的区间,使这个区间内的牛阵容平衡。区间的大小为区间内最右边的牛的坐标减去最做边的牛的坐标。 输入中,每个种族至少有一头牛,没有两头牛的坐标相同。

Read More →

[bzoj 1637] Usaco2007Mar Balanced Lineup

@krydom2年前

08/25
07:15
贪心

[bzoj 1634] Usaco2007Jan Protecting the Flowers 护花

00:00/00:00

20131108114159_WCLFP.thumb.600_0   cefc1e178a82b90131d67351708da9773912ef5d

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

Farmer John went to cut some wood and left N (2 <= N <= 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cows were in his garden eating his beautiful flowers. Wanting to minimize the subsequent damage, FJ decided to take immediate action and transport the cows back to their barn. Each cow i is at a location that is Ti minutes (1 <= Ti <= 2,000,000) away from the barn. Read More →

[bzoj 1634] Usaco2007Jan Protecting the Flowers 护花

@krydom2年前

08/24
03:55
贪心

[bzoj 1623] Usaco2008Open Cow Cars 奶牛飞车

00:00/00:00

同伴让我放点魔法科高校的劣等生的图QAQ 可是我并没有找到特别好的QAQ 对不起啊=w=

1388748607   3230965

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

编号为1到N的N只奶牛正各自驾着车打算在牛德比亚的高速公路上飞驰.高速公路有M(1≤M≤N)条车道.奶牛i有一个自己的车速上限Si(l≤Si≤1,000,000).在经历过糟糕的驾驶事故之后,奶牛们变得十分小心,避免碰撞的发生.每条车道上,如果某一只奶牛i的前面有K只奶牛驾车行驶,那奶牛i的速度上限就会下降K*D个单位,也就是说,她的速度不会超过Si - kD(O≤D≤5000),当然如果这个数是负的,那她的速度将是0.牛德比亚的高速会路法规定,在高速公路上行驶的车辆时速不得低于/(1≤L≤1,000,000).那么,请你计算有多少奶牛可以在高速公路上行驶呢?

Read More →

[bzoj 1623] Usaco2008Open Cow Cars 奶牛飞车

@krydom2年前

08/23
02:32
kruskal

[bzoj 1682] Usaco2005Mar Out of Hay 干草危机

00:00/00:00

64380cd7912397dd02a16bb95b82b2b7d1a287b7   20130213133739_A43nA.thumb.600_0

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

The cows have run out of hay, a horrible event that must be remedied immediately. Bessie intends to visit the other farms to survey their hay situation. There are N (2 <= N <= 2,000) farms (numbered 1..N); Bessie starts at Farm 1. She'll traverse some or all of the M (1 <= M <= 10,000) two-way roads whose length does not exceed 1,000,000,000 that connect the farms. Some farms may be multiply connected with different length roads. All farms are connected one way or another to Farm 1. Read More →

[bzoj 1682] Usaco2005Mar Out of Hay 干草危机