• 【NOIP模拟赛】大逃亡

    【NOIP模拟赛】大逃亡

    给出数字N(1<=N<=10000),X(1<=x<=1000),Y(1<=Y<=1000),代表有N个敌人分布一个X行Y列的矩阵上,矩形的行号从0到X-1,列号从0到Y-1再给出四个数字x1,y1,x2,y2,代表你要从点(x1,y1)移到(x2,y2)。在移动的过程中你当然希望离敌人的距离的最小值最大化,现在请求出这个值最大可以为多少,以及在这个前提下,你最少要走多少步才可以回到目标点。注意这里距离的定义为两点的曼哈顿距离,即某两个点的坐...

    12014年10月4日1,250二分法,广度搜索
  • 【bzoj1098】[POI2007]办公楼biu

    【bzoj1098】[POI2007]办公楼biu

    DescriptionFGD开办了一家电话公司。他雇用了N个职员,给了每个职员一部手机。每个职员的手机里都存储有一些同事的电话号码。由于FGD的公司规模不断扩大,旧的办公楼已经显得十分狭窄,FGD决定将公司迁至一些新的办公楼。FGD希望职员被安置在尽量多的办公楼当中,这样对于每个职员来说都会有一个相对更好的工作环境。但是,为了联系方便起见,如果两个职员被安置在两个不同的办公楼之内,他们必须拥有彼此的电话号码...

    02014年10月3日1,885深度搜索,链表,广度搜索
  • 【bzoj1632】[Usaco2007 Feb]Lilypad Pond

    【bzoj1632】[Usaco2007 Feb]Lilypad Pond

    DescriptionFarmerJohn建造了一个美丽的池塘,用于让他的牛们审美和锻炼。这个长方形的池子被分割成了M行和N列(1≤M≤30;1≤N≤30)正方形格子的。某些格子上有惊人的坚固的莲花,还有一些岩石,其余的只是美丽,纯净,湛蓝的水。贝茜正在练习芭蕾舞,她从一个莲花跳跃到另一个莲花,当前位于一个莲花。她希望在莲花上一个一个的跳,目标是另一个给定莲花。她能跳既不入水,也不到一个岩石上。令门外汉惊讶的是,贝茜的每次的...

    02014年10月3日1,405广度搜索
  • 【NOIP模拟赛】栅栏迷宫

    【NOIP模拟赛】栅栏迷宫

    田野上搭建了一个黄金大神专用的栅栏围成的迷宫。幸运的是,在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是,所建造的迷宫是一个“完美的”迷宫:即你能从迷宫中的任意一点找到一条走出迷宫的路。给定迷宫的宽W(1<=W<=38)及长H(1<=H<=100)。2*H+1行,每行2*W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数(就是从最“糟糕”的一点,走出迷宫的最少步...

    02014年9月27日1,034广度搜索
  • 【bzoj3299】[USACO2011 Open]Corn Maze玉米迷宫

    【bzoj3299】[USACO2011 Open]Corn Maze玉米迷宫

    Description今年秋天,约翰带着奶牛们去玩玉米迷宫。迷宫可分成NxM个格子,有些格子种了玉米,种宥玉米的格子无法通行。迷宫的四条边界上都是种了玉米的格子,其屮只有一个格子没种,那就是出口。在这个迷宫里,有一些神奇的传送点6每个传送点由一对点组成,一旦走入传送点的某个结点,机器就会强制把你送到传送点的另一头去。所有的传送点都是双向的,如果你定到了另一头,机器也会把你送回来。奶牛在一个单位的时间内只能向相...

    02014年8月30日1,448广度搜索
  • 【bzoj1644】[Usaco2007 Oct]Obstacle Course 障碍训练课

    【bzoj1644】[Usaco2007 Oct]Obstacle Course 障碍训练课

    Description考虑一个NxN(1<=N<=100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的,它们被标记为了'x'。例如下图:..Bx..xxA....x..x.....x.. 贝茜发现自己恰好在点A处,她想去B处的盐块舔盐。缓慢而且笨拙的动物,比如奶牛,十分讨厌转弯。尽管如此,当然在必要的时候她们还是会转弯的。对于一个给定的牧场,请你计算从A到B最少的转弯次数。开始的时候,贝茜可以使面对任意一个方向。贝茜知道...

    02014年7月27日1,010广度搜索
  • 【tyvj1577】泥泞的道路

    【tyvj1577】泥泞的道路

    描述Description公园中有n个景点,编号1~n,并由m条双向道路相连。由于昨天下雨,导致公园中的马路泥泞不堪,每条道路都有一个泥泞程度w。现有Q个游客依次向你求助,想从景点X走到景点Y,他希望找到一条道路,使得经过道路泥泞程度的最大值尽量小。你能设计一个在线算法,帮他们找到方案吗?输入格式InputFormat第一行两个正整数n和m,表示景点数和道路数。随后m行每行三个正整数x、y、w,用来描述一条道路,它连接x和y景点并...

    02014年7月26日1,709广度搜索,树上倍增
  • 【bzoj1615】[Usaco2008 Mar]The Loathesome Hay Baler麻烦的干草打包机

    【bzoj1615】[Usaco2008 Mar]The Loathesome Hay Baler麻烦的干草打包机

    DescriptionFarmerJohn新买的干草打包机的内部结构大概算世界上最混乱的了,它不象普通的机器一样有明确的内部传动装置,而是,N(2<=N<=1050)个齿轮互相作用,每个齿轮都可能驱动着多个齿轮。FJ记录了对于每个齿轮i,记录了它的3个参数:X_i,Y_i表示齿轮中心的位置坐标(-5000<=X_i<=5000;-5000<=Y_i<=5000);R_i表示该齿轮的半径(3<=R_i<=800)。驱动齿轮的位置为0,0,并且FJ也知道最终的工...

    02014年7月23日1,378广度搜索
  • 【NOIP模拟赛】聪明的打字员

    【NOIP模拟赛】聪明的打字员

    聪明的打字员(typer)阿兰是某机密部门的打字员,她现在接到一个任务:需要在一天之内输入几百个长度固定为6的密码。当然,她希望输入的过程中敲击键盘的总次数越少越好。不幸的是,出于保密的需要,该部门用于输入密码的键盘是特殊设计的,键盘上没有数字键,而只有以下六个键:Swap0,Swap1,Up,Down,Left,Right。为了说明这6个键的用,我们先定义录入区的6个位置的编号,从左至右依次为l,2,3,4,5,6。下面列出每个键...

    32014年7月8日1,106广度搜索
  • 【bzoj1656】[Usaco2006 Jan]The Grove 树木

    【bzoj1656】[Usaco2006 Jan]The Grove 树木

    DescriptionThepasturecontainsasmall,contiguousgroveoftreesthathasno'holes'inthemiddleoftheit.Bessiewonders:howfarisittowalkaroundthatgroveandgetbacktomystartingposition?She'sjustsurethereisawaytodoitbygoingfromherstartlocationtosuccessivelocationsbywalkinghorizontally,vertically,ordiagonallyandcountingeachmoveasasinglestep.Justlookingatit,shedoesn'tthinkyoucouldpass'through'thegroveonatrickyd...

    02014年7月5日978广度搜索
  • 【NOIP模拟赛】密码锁

    【NOIP模拟赛】密码锁

    题目描述hzwer有一把密码锁,由N个开关组成。一开始的时候,所有开关都是关上的。当且仅当开关x1,x2,x3,...xk为开,其他开关为关时,密码锁才会打开。他可以进行M种的操作,每种操作有一个size[i],表示,假如他选择了第i种的操作的话,他可以任意选择连续的size[i]个格子,把它们全部取反。(注意,由于黄金大神非常的神,所以操作次数可以无限>_<)本来这是一个无关紧要的问题,但是,黄金大神不小心他的钱丢进去了,没有...

  • 【NOIP模拟赛】水灾

    【NOIP模拟赛】水灾

    http://218.5.5.242:9018/JudgeOnline/problem.php?id=1452题目描述大雨应经下了几天雨,却还是没有停的样子。土豪CCY刚从外地赚完1e元回来,知道不久除了自己别墅,其他的地方都将会被洪水淹没。CCY所在的城市可以用一个N*M(N,M<=50)的地图表示,地图上有五种符号:“.*XDS”。其中“X”表示石头,水和人都不能从上面经过。“.”表示平原,CCY和洪水都可以经过。“*”表示洪水开始地方(可能有多个地方开始...

    02014年6月1日1,324广度搜索
  • 【bzoj1627】[Usaco2007 Dec]穿越泥地

    【bzoj1627】[Usaco2007 Dec]穿越泥地

    Description清早6:00,FarmerJohn就离开了他的屋子,开始了他的例行工作:为贝茜挤奶。前一天晚上,整个农场刚经受过一场瓢泼大雨的洗礼,于是不难想见,FJ现在面对的是一大片泥泞的土地。FJ的屋子在平面坐标(0,0)的位置,贝茜所在的牛棚则位于坐标(X,Y)(-500<=X<=500;-500<=Y<=500)处。当然咯,FJ也看到了地上的所有N(1<=N<=10,000)个泥塘,第i个泥塘的坐标为(A_i,B_i)(-500<=A_i<=50...

    02014年5月23日1,055广度搜索