• 【bzoj2282】[Sdoi2011]消防

    【bzoj2282】[Sdoi2011]消防

    Description某个国家有n个城市,这n个城市中任意两个都连通且有唯一一条路径,每条连通两个城市的道路的长度为zi(zi<=1000)。这个国家的人对火焰有超越宇宙的热情,所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍(大量的消防经费开销)可是却又无可奈何(总统竞选的国民支持率),所以只能想尽方法提高消防能力。现在这个国家的经费足以在一条边长度和不超过s的路径(两端都是城市)上建立消防枢纽,为了尽...

    62014年12月22日1,628二分法,广度搜索
  • NOIP2014寻找道路

    NOIP2014寻找道路

     题目描述Description在有向图G中,每条边的长度均为1,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件:1.路径上的所有点的出边所指向的点都直接或间接与终点连通。2.在满足条件1的情况下使路径最短。注意:图G中可能存在重边和自环,题目保证终点没有出边。请你输出符合条件的路径的长度。 输入输出格式Input/output输入格式:输入文件名为road.in。第一行有两个用一个空格隔开的整数n和m,...

    32014年11月22日2,530广度搜索
  • 【bzoj1193】[HNOI2006]马步距离

    【bzoj1193】[HNOI2006]马步距离

    DescriptionInput只包含4个整数,它们彼此用空格隔开,分别为xp,yp,xs,ys。并且它们的都小于10000000。Output含一个整数,表示从点p到点s至少需要经过的马步移动次数。SampleInput1279SampleOutput5题解 大范围贪心,然后小范围暴力[crayon-58afad27833b3638995126/]  ...

    22014年11月13日1,813贪心,广度搜索
  • NOIP2010引水入城

    NOIP2010引水入城

    题目描述Description 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个N行M列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此,只有与湖泊毗邻的第1行的...

    02014年11月6日2,693贪心,广度搜索
  • 【NOIP模拟赛】密室逃脱

    【NOIP模拟赛】密室逃脱

    即使czhou没有派出最强篮球阵容,机房篮球队还是暴虐了校篮球队。为了不打击校篮球队信心,czhou决定改变训练后的活动。近来,江大掌门的徒弟徒孙们纷纷事业有成,回到母校为机房捐钱捐物。财大气粗的机房组收回了五层六层的所有教室。Czhou决定将六层的教室改造为智能密室逃脱活动室。每天傍晚,神牛们可以依次逐个进入游玩。我们简单的将教室分割为n*n个房间,K是你初始所在房间,T是你最终逃脱的房间。如果你想要逃脱房间,你...

    02014年11月5日935深度搜索,广度搜索
  • 【NOIP模拟赛】藏宝图

    【NOIP模拟赛】藏宝图

    背景Czy爬上黑红树,到达了一个奇怪的地方……题目描述Czy发现了一张奇怪的藏宝图。图上有n个点,m条无向边。已经标出了图中两两之间距离dist。但是czy知道,只有当图中的各个点刚好又是一颗树的节点的时候,这张藏宝图才是真的。如果藏宝图是真的,那么经过点x的边的边权平均数最大的那个x是藏着宝物的地方。请计算这是不是真的藏宝图,如果是真的藏宝之处在哪里。格式输入数据第一行一个数T,表示T组数据。对于每组数据,第一...

    12014年10月31日1,048STL,prim,广度搜索
  • 【NOIP模拟赛】Graph

    【NOIP模拟赛】Graph

    【题目描述】给出N个点,M条边的有向图,对于每个点v,求A(v)表示从点v出发,能到达的编号最大的点。【输入格式】第1行,2个整数N,M。接下来M行,每行2个整数Ui,Vi,表示边⟨Ui,Vi⟩。点用1,2,...,N编号。【输出格式】N个整数A(1),A(2),...,A(N)。【样例输入】43122443【样例输出】4434【数据范围】对于60%的数据,1≤N,K≤10^3对于100%的数据,1≤N,M≤10^5。题解反建图bfs[crayon-58afad2785142923585144/]&...

    02014年10月30日573广度搜索
  • 【bzoj3417】Poi2013 Tales of seafaring

    【bzoj3417】Poi2013 Tales of seafaring

    DescriptionYoungBytenssonlovestohangoutintheporttavern,whereheoftenlistenstotheseadogstellingtheirtalesofseafaring.Initially,hebelievedthemall,howeverincredibletheysounded.Overtimethough,hebecamesuspicious.Hehasdecidedtowriteaprogramthatwillverifyiftheremaybeanygrainoftruthinthosetallstories.Bytenssonreasonedthatwhilehecannottellifthesailorsindeedweatheredallthosestorms,hecanatleastfindouti...

    362014年10月29日1,109广度搜索,离线处理
  • 【vijos1876】小岛的标号

    【vijos1876】小岛的标号

    描述Xiaodao是一位喜欢参加ACM比赛的孩子.所谓ACM比赛,是一种团队比赛.每一次比赛,每队需要由恰好三位选手组成.现在,Xiaodao希望组建一支新的队伍,在这之前,他需要知道每一位朋友有多少可能成为自己的好队友.他计划给每一位朋友做出一个等级标号.Xiaodao本人的等级标号为0.如果一位朋友曾经和Xiaodao组队参加过比赛,那么就标号为1.如果一位朋友并没有与Xiaodao组队参加过比赛,但是曾经与一位"与Xiaodao一起参加过比赛的...

    12014年10月29日856广度搜索
  • 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日990广度搜索
  • 【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,154广度搜索
  • 【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日992二分法,广度搜索
  • 【bzoj1098】[POI2007]办公楼biu

    【bzoj1098】[POI2007]办公楼biu

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

    02014年10月3日1,465链表,深度搜索,广度搜索