2017年11月

POJ 1185: 炮兵阵地

Description司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: 如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵- 阅读剩余部分 -

BZOJ 3891: [Usaco2014 Dec]Piggy Back

题目描述给定一个N个点M条边的无向图,其中Bessie在1号点,Elsie在2号点,它们的目的地为N号点。Bessie每经过一条边需要消耗B点能量,Elsie每经过一条边需要消耗E点能量。当它们相遇时,它们可以一起行走,此时它们每经过一条边需要消耗P点能量。求它们两个到达N号点时最少消耗多少能量?输入The first line of input contains the positive integers B, E, P, N, and M. All of these are at most 40,000. B, E, and P are described abov- 阅读剩余部分 -

BZOJ 3299: [USACO2011 Open]Corn Maze玉米迷宫

Description今年秋天,约翰带着奶牛们去玩玉米迷宫。迷宫可分成NxM个格子,有些格子种了玉 米,种宥玉米的格子无法通行。 迷宫的四条边界上都是种了玉米的格子,其屮只有一个格子 没种,那就是出口。 在这个迷宫里,有一些神奇的传送点6每个传送点由一对点组成,一旦 走入传送点的某个结点, 机器就会强制把你送到传送点的另一头去。所有的传送点都是双向 的,如果你定到了另一头,机器也会把你送回来。 奶牛在一个单位的时间内只能向相邻的四个方向移动一格,不过传送机传送是瞬间完成 的。 现在W西在迷宫里迷路了,她只知道目前的位罝在哪里,请你帮助她用最短的时间走出 迷宫吧。Input第- 阅读剩余部分 -

BZOJ 3300: [USACO2011 Feb]Best Parenthesis

Description计算“平衡字符串”的分数,“平衡字符串”是指由相同数量的‘(’和‘)’组成, 且以‘(’开头,以‘)’结尾的字符串。 计算规则: 字符串“()”的得分是1. 如果,平衡字符串“A”的得分是是S(A),那么字符串“(A)”得分是2*S(A) ; 如果,“A”,“B” 得分分别是S(A)和S(B),那么平衡字符串“AB”得分为S(A)+S(B) 例如:s("(())()") =s("(())")+s("()") = 2s("()")+1 = 21+1 = 3.Input第1行:N,平衡字符串长度 第2至N+1行:Linei+1 整数0或1,0代表字符‘(’- 阅读剩余部分 -

BZOJ 3393: [Usaco2009 Jan]Laserphones 激光通讯

DescriptionInput第1行输入w和H,之后W行H列输入地图,图上符号意义如题目描述.Output最少的对角镜数量.Sample Input7 8 ....... ......C ......* *****.* ....*.. ....*.. .C..*.. .......Sample Output3Solution搜索,类似于最短路,不过要加一维方向,整体类似于 SPFACode#include <bits/stdc++.h> #define long long long using namespace std; inline void read(i- 阅读剩余部分 -

BZOJ 2197: [Usaco2011 Mar]Tree Decoration

Description约翰正在装饰他家的圣诞树。圣诞树上有个 N 个结点,第一个结点是根,其余结点都有唯一的父亲结点,第 i 个结点的父亲是 P i 。由于根没有父亲,所以记 P 1 = −1。约翰可以在每个结点上挂载装饰物,但费用是变化。在第 i 个结点上挂载一个装饰物需要花费 C i元钱。奶牛对这个圣诞树上每个结点都有特殊的装饰需求,对于第 i 个结点,奶牛要求以它为根的子树上必须有 D i 个装饰物。请问约翰在哪些结点上挂载装饰物,才能满足奶牛的要求,并且使得装饰费用最少?Input第一行:单个整数 N,1 ≤ N ≤ 10 5第二行到 N 行:第 i+1 行有三个整- 阅读剩余部分 -

BZOJ 2020: [Usaco2010 Jan]Buying Feed, II

DescriptionFJ开车去买K份食物,如果他的车上有X份食物。每走一里就花费X元。 FJ的城市是一条线,总共E里路,有E+1个地方,标号0~E。 FJ从0开始走,到E结束(不能往回走),要买K份食物。 城里有N个商店,每个商店的位置是X_i(一个点上可能有多个商店),有F_i份食物,每份C_i元。 问到达E并买K份食物的最小花费Input第1行:K,E,N 第2~N+1行:X_i,F_i,C_i.Output一个整数,花费。Sample Input2 5 3 3 1 2 4 1 2 1 1 1Sample Output7Solution由于路程原因,每个物品的单价需要- 阅读剩余部分 -

BZOJ 2097: [Usaco2010 Dec]Exercise 奶牛健美操

DescriptionFarmer John为了保持奶牛们的健康,让可怜的奶牛们不停在牧场之间 的小路上奔跑。这些奶牛的路径集合可以被表示成一个点集和一些连接 两个顶点的双向路,使得每对点之间恰好有一条简单路径。简单的说来, 这些点的布局就是一棵树,且每条边等长,都为1。 对于给定的一个奶牛路径集合,精明的奶牛们会计算出任意点对路径的最大值, 我们称之为这个路径集合的直径。如果直径太大,奶牛们就会拒绝锻炼。 Farmer John把每个点标记为1..V (2 <= V <= 100,000)。为了获得更加短 的直径,他可以选择封锁一些已经存在的道路,这样就可以得- 阅读剩余部分 -

BZOJ 3018: [Usaco2012 Nov]Distant Pastures

Description给定一个n×n的一个网格,每个格子有一个字符,要么是’(‘,要么是’)’。每个格子和它的上下左右的四个格子相邻,对于相邻的两个格子x和y,从x走到y的过程中,如果x和y中的字符相同,消耗A单位时间,如果x和y中字符不同,消耗B单位时间。定义点S到点T的时间为D(S,T),现在想请你求出网格中最大的D(S,T)。Input第一行三个整数n,A,B;接下来n行描述这个n×n的网格。1 <= n <= 30,1 <= A <= 1,000,000,1 <= B <= 1,000,000。Output一个整数,最大的D(S,- 阅读剩余部分 -

BZOJ 1673: [Usaco2005 Dec]Scales 天平

Description约翰有一架用来称牛的体重的天平.与之配套的是N(1≤N≤1000)个已知质量的砝码(所有砝码质量的数值都在31位二进制内).每次称牛时,他都把某头奶牛安置在天平的某一边,然后往天平另一边加砝码,直到天平平衡,于是此时砝码的总质量就是牛的质量(约翰不能把砝码放到奶牛的那边,因为奶牛不喜欢称体重,每当约翰把砝码放到她的蹄子底下,她就会尝试把砝码踢到约翰脸上).天平能承受的物体的质量不是无限的,当天平某一边物体的质量大于C(1≤C<230)时,天平就会被损坏. 砝码按照它们质量的大小被排成一行.并且,这一行中从第3个砝码开始,每个砝码的质量至少等- 阅读剩余部分 -

BZOJ 1774: [Usaco2009 Dec]Toll 过路费

Description跟所有人一样,农夫约翰以着宁教我负天下牛,休叫天下牛负我的伟大精神,日日夜夜苦思生 财之道。为了发财,他设置了一系列的规章制度,使得任何一只奶牛在农场中的道路行走,都 要向农夫约翰上交过路费。 农场中由N(1 <= N <= 250)片草地(标号为1到N),并且有M(1 <= M <= 10000)条 双向道路连接草地A_j和B_j(1 <= A_j <= N; 1 <= B_j <= N)。奶牛们从任意一片草 地出发可以抵达任意一片的草地。FJ已经在连接A_j和B_j的双向道路上设置一个过路费L_j (- 阅读剩余部分 -

BZOJ 3016: [Usaco2012 Nov]Clumsy Cows

Description给定长度为n的一个括号序列,每次修改可以修改一个位置的括号,若这个括号为’(‘,则修改为’)’,若这个括号为’)’,则修改为’(‘,问最少修改多少个使得原括号序列合法。其中:① ()是合法的;② 若A是合法的,则(A)是合法的;③ 若A,B都是合法的,则AB是合法的。Input一个长度为n个括号序列。Output最少的修改次数。Sample Input())(Sample Output2Solution维护一个栈,可以用计数器模拟。一个序列合法的话每个括号的前面所有括号,左括号要大于等于有括号。Code#include <- 阅读剩余部分 -

BZOJ 3433: [Usaco2014 Jan]Recording the Moolympics

Description给出n个区间[a,b).有2个记录器.每个记录器中存放的区间不能重叠.求2个记录器中最多可放多少个区间.InputLine 1: The integer N.Lines 2..1+N: Each line contains the start and end time of a single program (integers in the range 0..1,000,000,000).OutputLine 1: The maximum number of programs FJ can record.Sample Input6 0 3 6 7 3- 阅读剩余部分 -