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

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

@krydom5月前

05/17
20:42
kruskal

[bzoj 4883] [Lydsy2017年5月月赛]棋盘上的守卫

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

在一个n*m的棋盘上要放置若干个守卫。对于n行来说,每行必须恰好放置一个横向守卫;同理对于m列来说,每列必须恰好放置一个纵向守卫。每个位置放置守卫的代价是不一样的,且每个位置最多只能放置一个守卫,一个守卫不能同时兼顾行列的防御。请计算控制整个棋盘的最小代价。

Read More →

[bzoj 4883] [Lydsy2017年5月月赛]棋盘上的守卫

@krydom6月前

04/20
07:53
kruskal

[CF 472D] Design Tutorial: Inverse the Problem

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

There is an easy way to obtain a new task from an old one called "Inverse the problem": we give an output of the original task, and ask to generate an input, such that solution to the original problem will produce the output we provided. The hard task of Topcoder Open 2014 Round 2C, InverseRMQ, is a good example.

Now let's create a task this way. We will use the task: you are given a tree, please calculate the distance between any pair of its nodes. Yes, it is very easy, but the inverse version is a bit harder: you are given an n × n distance matrix. Determine if it is the distance matrix of a weighted tree (all weights must be positive integers).

Read More →

[CF 472D] Design Tutorial: Inverse the Problem

@krydom11月前

12/6
20:49
kruskal LCA

[bzoj 3732] Network

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

给你N个点的无向图 (1 <= N <= 15,000),记为:1…N。
图中有M条边 (1 <= M <= 30,000) ,第j条边的长度为: d_j ( 1 < = d_j < = 1,000,000,000).

现在有 K个询问 (1 < = K < = 15,000)。
每个询问的格式是:A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少?

Read More →

[bzoj 3732] Network

@krydom1年前

08/6
17:41
kruskal

[bzoj 1050] [HAOI2006]旅行comf

00:00/00:00

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

 给你一个无向图,N(N<=500)个顶点, M(M<=5000)条边,每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T,求一条路径,使得路径上最大边和最小边的比值最小。如果S和T之间没有路径,输出”IMPOSSIBLE”,否则输出这个比值,如果需要,表示成一个既约分数。 备注: 两个顶点之间可能有多条路径。

Read More →

[bzoj 1050] [HAOI2006]旅行comf

@krydom1年前

08/5
21:58
kruskal

[bzoj 2429] [HAOI2006]聪明的猴子

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

在一个热带雨林中生存着一群猴子,它们以树上的果子为生。昨天下了一场大雨,现在雨过天晴,但整个雨林的地表还是被大水淹没着,部分植物的树冠露在水面上。猴子不会游泳,但跳跃能力比较强,它们仍然可以在露出水面的不同树冠上来回穿梭,以找到喜欢吃的果实。
现在,在这个地区露出水面的有N棵树,假设每棵树本身的直径都很小,可以忽略不计。我们在这块区域上建立直角坐标系,则每一棵树的位置由其所对应的坐标表示(任意两棵树的坐标都不相同)。
在这个地区住着的猴子有M个,下雨时,它们都躲到了茂密高大的树冠中,没有被大水冲走。由于各个猴子的年龄不同、身体素质不同,它们跳跃的能力不同。有的猴子跳跃的距离比较远(当然也可以跳到较近的树上),而有些猴子跳跃的距离就比较近。这些猴子非常聪明,它们通过目测就可以准确地判断出自己能否跳到对面的树上。
【问题】 现已知猴子的数量及每一个猴子的最大跳跃距离,还知道露出水面的每一棵树的坐标,你的任务是统计有多少个猴子可以在这个地区露出水面的所有树冠上觅食。

Read More →

[bzoj 2429] [HAOI2006]聪明的猴子

@krydom1年前

06/2
19:26
kruskal

[bzoj 3390] [Usaco2004 Dec]Bad Cowtractors牛的报复

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

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

Read More →

[bzoj 3390] [Usaco2004 Dec]Bad Cowtractors牛的报复

@krydom1年前

05/12
08:15
kruskal

[bzoj 1626] Usaco2007Dec Building Roads 修建道路

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

 Farmer John最近得到了一些新的农场,他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达(也就是说,从任一个农场都可以经过一些首尾相连道路到达剩下的所有农场)。有些农场之间原本就有道路相连。 所有N(1 <= N <= 1,000)个农场(用1..N顺次编号)在地图上都表示为坐标为(X_i, Y_i)的点(0 <= X_i <= 1,000,000;0 <= Y_i <= 1,000,000),两个农场间道路的长度自然就是代表它们的点之间的距离。现在Farmer John也告诉了你农场间原有的M(1 <= M <= 1,000)条路分别连接了哪两个农场,他希望你计算一下,为了使得所有农场连通,他所需建造道路的最小总长是多少。

Read More →

[bzoj 1626] Usaco2007Dec Building Roads 修建道路

@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/10
20:05
kruskal

[bzoj 1601] Usaco2008Oct 灌水

00:00/00:00

20120108195044_vn52e.thumb.700_0   21a4462309f79052b6d67d4d0cf3d7ca7acbd5f3

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

 Farmer John已经决定把水灌到他的n(1<=n<=300)块农田,农田被数字1到n标记。把一块土地进行灌水有两种方法,从其他农田饮水,或者这块土地建造水库。 建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0). 计算Farmer John所需的最少代价。

Read More →

[bzoj 1601] Usaco2008Oct 灌水

@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]