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

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

@krydom2月前

04/19
21:26
spfa 乱搞 暴力 离线

[czyz 2017.04.16 noip- 模拟赛]

A:http://czyzuoj.com/problem/77

B:http://czyzuoj.com/problem/78

C:http://czyzuoj.com/problem/79

 

A:

【防AK好题(???)(雾)】

假·在线,从前往后做应该是不能做的....

因为最后一行解密出来是0,0,0,所以我们先可以直接知道最后一个询问的答案

然后发现如果已经知道了第i个询问的答案,求解第i-1个询问的答案只要接一个一元一次方程就可以了... Read More →

[czyz 2017.04.16 noip- 模拟赛]

@krydom6月前

12/25
09:13
spfa 动态规划

[bzoj 3875] [Ahoi2014]骑士游戏

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

【故事背景】
长期的宅男生活中,JYY又挖掘出了一款RPG游戏。在这个游戏中JYY会扮演一个英勇的骑士,用他手中的长剑去杀死入侵村庄的怪兽。
【问题描述】
在这个游戏中,JYY一共有两种攻击方式,一种是普通攻击,一种是法术攻击。两种攻击方式都会消耗JYY一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死,怪兽的尸体可以变出其他一些新的怪兽,注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽;而采用法术攻击则可以彻底将一个怪兽杀死。当然了,一般来说,相比普通攻击,法术攻击会消耗更多的体力值(但由于游戏系统bug,并不保证这一点)。
游戏世界中一共有N种不同的怪兽,分别由1到N编号,现在1号怪兽入侵村庄了,JYY想知道,最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢?

Read More →

[bzoj 3875] [Ahoi2014]骑士游戏

@krydom11月前

08/5
16:55
spfa 差分约束

[bzoj 2330] [SCOI2011]糖果

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

 幼儿园里有N个小朋友,lxhgww老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候,lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的,lxhgww想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。

Read More →

[bzoj 2330] [SCOI2011]糖果

@krydom1年前

06/11
08:29
spfa

[bzoj 2763] [JLOI2011]飞行路线

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

 Alice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务,设这些城市分别标记为0到n-1,一共有m种航线,每种航线连接两个城市,并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对他们这次旅行也推出优惠,他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少?
[萌漫乡]东方project 166

Read More →

[bzoj 2763] [JLOI2011]飞行路线

@krydom1年前

05/25
10:13
spfa 一般动规与递推

[bzoj 1003] [ZJOI2006]物流运输

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

 物流公司要把一批货物从码头A运到码头B。由于货物量比较大,需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个n天的运输计划,使得总成本尽可能地小。

Read More →

[bzoj 1003] [ZJOI2006]物流运输

@krydom1年前

05/10
08:27
spfa 网络流

[bzoj 1001] BeiJing2006 狼抓兔子

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

现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,
而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:1001
左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路
1:(x,y)<==>(x+1,y)
2:(x,y)<==>(x,y+1)
3:(x,y)<==>(x+1,y+1)
道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的. 左上角和右下角为兔子的两个窝,
开始时所有的兔子都聚集在左上角(1,1)的窝里,现在它们要跑到右下解(N,M)的窝中去,狼王开始伏击
这些兔子.当然为了保险起见,如果一条道路上最多通过的兔子数为K,狼王需要安排同样数量的K只狼,
才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的
狼的数量要最小。因为狼还要去找喜羊羊麻烦.

Read More →

[bzoj 1001] BeiJing2006 狼抓兔子

@krydom1年前

12/27
13:02
spfa

[bzoj 1614] Usaco2007Jan Telephone Lines

00:00/00:00

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

     Farmer John打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务。于是,FJ必须为此向电信公司支付一定的费用。 FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆,任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线,其余的那些由于隔得太远而无法被连接。 第i对电话线杆的两个端点分别为A_i、B_i,它们间的距离为 L_i (1 <= L_i <= 1,000,000)。数据中保证每对{A_i,B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络,整个农场的电话线全都连到了编号为N的电话线杆上。也就是说,FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径,其余的电话线杆并不一定要连入电话网络。 经过谈判,电信公司最终同意免费为FJ连结K(0 <= K < N)对由FJ指定的电话线杆。对于此外的那些电话线,FJ需要为它们付的费用,等于其中最长的电话线的长度(每根电话线仅连结一对电话线杆)。如果需要连结的电话线杆不超过 K对,那么FJ的总支出为0。 请你计算一下,FJ最少需要在电话线上花多少钱。

Read More →

[bzoj 1614] Usaco2007Jan Telephone Lines

@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