算法 - Page 100 - hzwer.com

「CF417A」Elimination
Thefinalistsofthe"RussianCodeCup"competitionin2214willbetheparticipantswhowininoneoftheeliminationrounds.Theeliminationroundsaredividedintomainandadditional.Eachofthemaineliminationroundsconsistsof c problems,thewinnersoftheroundarethefirst n peopleintheratinglist.Eachoftheadditionaleliminationroundsconsistsof d problems.Thewinneroftheadditionalroundisoneperson.Besides, k winnerso...
02014年4月19日2,940背包动规

「BZOJ1671」[Usaco2005 Dec] Knights of Ni 骑士
DescriptionBessieisinCamelotandhasencounteredastickysituation:sheneedstopassthroughtheforestthatisguardedbytheKnightsofNi.Inordertopassthroughsafely,theKnightshavedemandedthatshebringthemasingleshrubbery.Timeisoftheessence,andBessiemustfindandbringthemashrubberyasquicklyaspossible.Bessiehasamapofoftheforest,whichispartitionedintoasquaregridarrayedintheusualmanner,withaxesparalleltotheXa...
02014年4月16日3,493广度搜索
「BZOJ1689」[Usaco2005 Open] Muddy roads 泥泞的路
DescriptionFarmerJohnhasaproblem:thedirtroadfromhisfarmtotownhassufferedintherecentrainstormsandnowcontains(1<=N<=10,000)mudpools.FarmerJohnhasacollectionofwoodenplanksoflengthLthathecanusetobridgethesemudpools.Hecanoverlapplanksandtheendsdonotneedtobeanchoredontheground.However,hemustcovereachpoolcompletely.Giventhemudpools,helpFJfigureouttheminimumnumberofplanksheneedsinorderto...
02014年4月16日3,587贪心
「BZOJ1639」[Usaco2007 Mar] Monthly Expense 月度开支
DescriptionFarmerJohn是一个令人惊讶的会计学天才，他已经明白了他可能会花光他的钱，这些钱本来是要维持农场每个月的正常运转的。他已经计算了他以后N(1<=N<=100,000)个工作日中每一天的花费moneyi(1<=moneyi<=10,000)，他想要为他连续的M(1<=M<=N)个被叫做“清算月”的结帐时期做一个预算，每一个“清算月”包含一个工作日或更多连续的工作日，每一个工作日都仅被包含在一个“清算月”当中。FJ的目...
02014年4月16日4,268二分法
「BZOJ1641」[Usaco2007 Nov] Cow Hurdles 奶牛跨栏
DescriptionFarmerJohn想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。奶牛的训练场中有N(1≤N≤300)个站台，分别标记为1..N。所有站台之间有M(1≤M≤25,000)条单向路径，第i条路经是从站台Si开始，到站台Ei，其中最高的栏的高度为Hi(1≤Hi≤1,000,0...
12014年4月16日3,883floyd
「BZOJ1045 / 1465」[HAOI2008] 糖果传递
Description老师准备了一堆糖果,恰好n个小朋友可以分到数目一样多的糖果.老师要n个小朋友去拿糖果,然后围着圆桌坐好,第1个小朋友的左边是第n个小朋友,其他第i个小朋友左边是第i-1个小朋友.大家坐好后,老师发现,有些小朋友抢了很多的糖果,有的小朋友只得到了一点点糖果,甚至一颗也没有,设第i个小朋友有ai颗糖果.小朋友们可以选择将一些糖果给他左边的或者右边的小朋友,通过”糖果传递”最后使得每个小朋友得到的糖果数是一样多的...
112014年4月15日10,471其它
「BZOJ1816」[CQOI2010] 扑克牌
Description你有n种牌，第i种牌的数目为ci。另外有一种特殊的牌：joker，它的数目是m。你可以用每种牌各一张来组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如，当n=3时，一共有4种合法的套牌：{1,2,3},{J,2,3},{1,J,3},{1,2,J}。给出n,m和ci，你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里（可以有牌不使用）。Input第一行包含两个整数n,m，即牌的种数和joker的个数。第二行包含...
42014年4月15日4,404二分法
「BZOJ1441」Min
Description给出n个数(A1...An)现求一组整数序列(X1...Xn)使得S=A1*X1+...An*Xn>0,且S的值最小Input第一行给出数字N,代表有N个数下面一行给出N个数OutputS的最小值SampleInput24059-1782SampleOutput99题解裴蜀定理[crayon-684dec2a29cbb723731033/] ...
12014年4月15日4,108最大公约数与最小公倍数
「BZOJ1621」[Usaco2008 Open] Roads Around The Farm分岔路口
Description 约翰的N(1≤N≤1,000,000,000)只奶牛要出发去探索牧场四周的土地．她们将沿着一条路走，一直走到三岔路口（可以认为所有的路口都是这样的）．这时候，这一群奶牛可能会分成两群，分别沿着接下来的两条路继续走．如果她们再次走到三岔路口，那么仍有可能继续分裂成两群继续走．奶牛的分裂方式十分古怪：如果这一群奶牛可以精确地分成两部分，这两部分的牛数恰好相差K(1≤K≤1000)，那么在三岔路口牛...
02014年4月15日2,447模拟
「BZOJ2463」[中山市选2009] 谁能赢呢？
Description小明和小红经常玩一个博弈游戏。给定一个n×n的棋盘，一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。假如小明先移动石头，而且两个选手都以最优策略走步，问最后谁能赢？Input 输入文件有多组数据。输入第一行包含一个整数n，表示棋盘的规模。当输入n为0时，表示...
02014年4月15日4,820博弈论
「BZOJ3390」[Usaco2004 Dec] Bad Cowtractors牛的报复
Description 奶牛贝茜被雇去建设N(2≤N≤1000)个牛棚间的互联网．她已经勘探出M(1≤M≤20000)条可建的线路，每条线路连接两个牛棚，而且会苞费C(1≤C≤100000)．农夫约翰吝啬得很，他希望建设费用最少甚至他都不想给贝茜工钱．贝茜得知工钱要告吹，决定报复．她打算选择建一些线路，把所有牛棚连接在一起，让约翰花费最大．但是她不能造出环来，这样约翰就会发现．Input 第1行：N，M. 第2到M+1行：三个整...
02014年4月15日3,727kruskal
「BZOJ3170」[TJOI2013] 松鼠聚会
Description有N个小松鼠，它们的家用一个点x,y表示，两个点的距离定义为：点(x,y)和它周围的8个点即上下左右四个点和对角的四个点，距离为1。现在N个松鼠要走到一个松鼠家去，求走过的最短距离。Input第一行给出数字N，表示有多少只小松鼠。0<=N<=10^5下面N行，每行给出x,y表示其家的坐标。-10^9<=x,y<=10^9Output表示为了聚会走的路程和最小为多少。SampleInput6-4-1-1-22-402035-2SampleOutput20题解对于...
02014年4月15日4,200其它