算法 - Page 30 - hzwer.com

「BZOJ3876」[Ahoi2014] 支线剧情
Description「故事背景」宅男JYY非常喜欢玩RPG游戏，比如仙剑，轩辕剑等等。不过JYY喜欢的并不是战斗场景，而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的支线剧情，现在JYY想花费最少的时间看完所有的支线剧情。「问题描述」JYY现在所玩的RPG游戏中，一共有N个剧情点，由1到N编号，第i个剧情点可以根据JYY的不同的选择，而经过不同的支线剧情，前往Ki种不同的新的剧情点。当然如果为0...
92015年1月25日7,152费用流,有上下界网络流

「POJ2187」Beauty Contest
DescriptionBessie,FarmerJohn'sprizecow,hasjustwonfirstplaceinabovinebeautycontest,earningthetitle'MissCowWorld'.Asaresult,BessiewillmakeatourofN(2<=N<=50,000)farmsaroundtheworldinordertospreadgoodwillbetweenfarmersandtheircows.Forsimplicity,theworldwillberepresentedasatwo-dimensionalplane,whereeachfarmislocatedatapairofintegercoordinates(x,y),eachhavingavalueintherange-10,000...1...
12015年1月25日8,310凸包,旋转卡壳
「CF403C」Strictly Positive Matrix
Youhavematrixaofsizen × n.Let'snumbertherowsofthematrixfrom1tonfromtoptobottom,let'snumberthecolumnsfrom1tonfromlefttoright.Let'suseaijtorepresenttheelementontheintersectionofthei-throwandthej-thcolumn.Matrixameetsthefollowingtwoconditions:foranynumbersi, j(1 ≤ i, j ≤ n)thefollowinginequalityholds:aij ≥ 0;.Matrixbisstrictlypositive,ifforanynumbersi, j(1 ≤ i, j ≤ n)theine...
02015年1月24日5,115图的连通
「POJ2362」Square
DescriptionGivenasetofsticksofvariouslengths,isitpossibletojointhemend-to-endtoformasquare?InputThefirstlineofinputcontainsN,thenumberoftestcases.Eachtestcasebeginswithaninteger4<=M<=20,thenumberofsticks.Mintegersfollow;eachgivesthelengthofastick-anintegerbetween1and10,000.OutputForeachcase,outputalinecontaining"yes"ifisispossibletoformasquare;otherwiseoutput"no".SampleInput[cray...
02015年1月22日3,018深度搜索
「BZOJ3813」奇数国
Description在一片美丽的大陆上有100000个国家，记为1到100000。这里经济发达，有数不尽的账房，并且每个国家有一个银行。某大公司的领袖在这100000个银行开户时都存了3大洋，他惜财如命，因此会不时地派小弟GFS清点一些银行的存款或者让GFS改变某个银行的存款。该村子在财产上的求和运算等同于我们的乘法运算，也就是说领袖开户时的存款总和为3100000。这里发行的软妹面额是最小的60个素数（p1=2,p2=3,…,p60=281），任何人...
02015年1月22日5,946线段树,筛法,欧拉函数,乘法逆元
「BZOJ2073」[POI2004] PRZ
Description一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥.桥已经很旧了,所以它不能承受太重的东西.任何时候队伍在桥上的人都不能超过一定的限制.所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过.队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,我们想知道如何分批过桥能使总时间最少.Input第一行两个数:w–桥能承受的最大重量(...
02015年1月22日4,263状压动规
「BZOJ1370」[Baltic2003] Gang团伙
Description在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：1、我朋友的朋友是我的朋友；2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？Input第1行为n和m，N小于1000,M小于5000；以下m行，每行为pxy，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人...
22015年1月20日6,319并查集
「BZOJ3611」[HEOI2014] 大工程
题面和题解见http://www.cnblogs.com/zyfzyf/p/4231356.html[crayon-6804f4b4e9d98599577227/]
22015年1月20日6,564虚树,dfs序,树形动规,最近公共祖先
「BZOJ3856」Monster
DescriptionTeacherMaihasakingdom.Amonsterhasinvadedthiskingdom,andTeacherMaiwantstokillit.MonsterinitiallyhashHP.AnditwilldieifHPislessthan1.TeacherMaiandmonstertaketurnstodotheiraction.Inoneround,TeacherMaicanattackthemonstersothattheHPofthemonsterwillbereducedbya.Attheendofthisround,theHPofmonsterwillbeincreasedbyb.Afterkconsecutiveround'sattack,TeacherMaimusttakearestin...
02015年1月20日2,568模拟
「CF364D」Ghd
JohnDoeofferedhissisterJaneDoefindthegcdofsomesetofnumbersa.Gcdisapositiveintegerg,suchthatallnumberfromthesetareevenlydivisiblebygandthereisn'tsuchg'(g' > g),thatallnumbersofthesetareevenlydivisiblebyg'.UnfortunatelyJanecouldn'tcopewiththetaskandJohnofferedhertofindtheghdofthesamesubsetofnumbers.Ghdisapositiveintegerg,suchthatatleasthalfofnumbersfromthesetareevenlydivisiblebygandthe...
02015年1月20日3,945随机化,最大公约数与最小公倍数
「BZOJ2286」[SDOI2011] 消耗战
Description在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总...
22015年1月20日8,469虚树,树形动规
「CF506B」Mr. Kitayuta’s Technology
ShusekiKingdomistheworld'sleadingnationforinnovationandtechnology.Therearencitiesinthekingdom,numberedfrom1ton.ThankstoMr.Kitayuta'sresearch,ithasfinallybecomepossibletoconstructteleportationpipesbetweentwocities.Ateleportationpipewillconnecttwocitiesunidirectionally,thatis,ateleportationpipefromcityxtocityycannotbeusedtotravelfromcityytocityx.Thetransportationwithineachcityisextremelydeve...
02015年1月19日5,533并查集,图的连通