• NOIP2002子串变换

    NOIP2002子串变换

    描述已知有两个字串A$,B$及一组字串变换的规则(至多6个规则):A1$->B1$A2$->B2$规则的含义为:在A$中的子串A1$可以变换为B1$、A2$可以变换为B2$…。例如:A$='abcd' B$='xyz'变换规则为:‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’则此时,A$可以经过一系列的变换变为B$,其变换的过程为:‘abcd’->‘xud’->‘xy’->‘xyz’共进行了三次变换,使得A$变换为B$。格式输入格式第...

    02014年10月21日1,454广度搜索
  • 「BZOJ1102」[POI2007] 山峰和山谷Grz

    「BZOJ1102」[POI2007] 山峰和山谷Grz

    DescriptionFGD小朋友特别喜欢爬山,在爬山的时候他就在研究山峰和山谷。为了能够让他对他的旅程有一个安排,他想知道山峰和山谷的数量。给定一个地图,为FGD想要旅行的区域,地图被分为n*n的网格,每个格子(i,j)的高度w(i,j)是给定的。若两个格子有公共顶点,那么他们就是相邻的格子。(所以与(i,j)相邻的格子有(i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1))。我们定义一个格子的集合...

    12014年10月18日1,862广度搜索
  • 「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,648二分法,广度搜索
  • 「BZOJ1098」[POI2007] 办公楼biu

    「BZOJ1098」[POI2007] 办公楼biu

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

    02014年10月3日2,396深度搜索,链表,广度搜索
  • 「BZOJ1632」[Usaco2007 Feb] Lilypad Pond

    「BZOJ1632」[Usaco2007 Feb] Lilypad Pond

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

    02014年10月3日1,697广度搜索
  • 「NOIP模拟赛」栅栏迷宫

    「NOIP模拟赛」栅栏迷宫

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

    02014年9月27日1,190广度搜索
  • 「BZOJ3299」[USACO2011 Open] Corn Maze玉米迷宫

    「BZOJ3299」[USACO2011 Open] Corn Maze玉米迷宫

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

    02014年8月30日1,763广度搜索
  • 「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,185广度搜索
  • 「JoyOI1577」泥泞的道路

    「JoyOI1577」泥泞的道路

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

    02014年7月26日1,952广度搜索,树上倍增
  • 「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,643广度搜索
  • 「NOIP模拟赛」聪明的打字员

    「NOIP模拟赛」聪明的打字员

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

    32014年7月8日1,281广度搜索
  • 「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日1,190广度搜索