算法 - Page 74 - hzwer.com

「BZOJ1673」[Usaco2005 Dec] Scales 天平
DescriptionFarmerJohnhasabalanceforweighingthecows.HealsohasasetofN(1<=N<=1000)weightswithknownmasses(allofwhichfitin31bits)foruseononesideofthebalance.Heplacesacowononesideofthebalanceandthenaddsweightstotheothersideuntiltheybalance.(FJcannotputweightsonthesamesideofthebalanceasthecow,becausecowstendtokickweightsinhisfacewhenevertheycan.)Thebalancehasamaximummassratingandwillbreak...
02014年7月29日3,799深度搜索

「BZOJ2015」[Usaco2010 Feb] Chocolate Giving
DescriptionFarmerJohn有B头奶牛(1<=B<=25000)，有N(2*B<=N<=50000)个农场，编号1-N，有M(N-1<=M<=100000)条双向边，第i条边连接农场R_i和S_i(1<=R_i<=N;1<=S_i<=N)，该边的长度是L_i(1<=L_i<=2000)。居住在农场P_i的奶牛A(1<=P_i<=N)，它想送一份新年礼物给居住在农场Q_i(1<=Q_i<=N)的奶牛B，但是奶牛A必须先到FJ(居住在编号1的农场)那里取礼物，...
02014年7月29日4,664spfa
「BZOJ1684」[Usaco2005 Oct] Close Encounter
DescriptionLackingevenafifthgradeeducation,thecowsarehavingtroublewithafractionproblemfromtheirtextbook.Pleasehelpthem.Theproblemissimple:Givenaproperlyreducedfraction(i.e.,thegreatestcommondivisorofthenumeratoranddenominatoris1,sothefractioncannotbefurtherreduced)findthesmallestproperlyreducedfractionwithnumeratoranddenominatorintherange1..32,767thatisclosest(butnotequal)tothegivenfraction.找...
02014年7月29日2,738模拟
「BZOJ3626」[LNOI2014] LCA
Description给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。有q次询问，每次询问给出lrz，求sigma_{l<=i<=r}dep[LCA(i,z)]。（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）Input第一行2个整数nq。接下来n-1行，分别表示点1到点n-1的父节点编号。接下来q行，每行3个整数lrz。Output输出q行...
102014年7月28日12,195树链剖分,离线处理
「BZOJ1349」[Baltic2006] Squint
DescriptionWriteaprogramtocalculateintegersquareroots.InputTheinputisreadfromatextfilenamedsquint.in.Itsonlylineconsistsofaninteger0<=n<2^63.OutputItsonlylineconsistsofthesmallestnonnegativeintegerqsuchthatq^2>=n.SampleInput122333444455555SampleOutput11060446HINTsqrt(122333444455555)=11060445.038765619.题解直接sqrt(n)真是神题啊[crayon-691107d8dab77043483341/] ...
02014年7月28日3,028模拟
「BZOJ2101」[Usaco2010 Dec] Treasure Chest 藏宝箱
DescriptionBessieandBonniehavefoundatreasurechestfullofmarvelousgoldcoins!Beingcows,though,theycan'tjustwalkintoastoreandbuystuff,soinsteadtheydecidetohavesomefunwiththecoins.TheN(1<=N<=5,000)coins,eachwithsomevalueC_i(1<=C_i<=5,000)areplacedinastraightline.BessieandBonnietaketurns,andforeachcow'sturn,shetakesexactlyonecoinoffofeithertheleftendortherightendoftheline.Thegame...
02014年7月28日4,261递推与动规
「BZOJ2020」[Usaco2010 Jan] Buying Feed, II
Description(buying.pas/buying.in/buying.out128M1S)FarmerJohnneedstotraveltotowntopickupK(1<=K<=100)poundsoffeed.DrivingDmileswithKpoundsoffeedinhistruckcostsD*Kcents.ThecountyfeedlothasN(1<=N<=100)stores(convenientlynumbered1..N)thatsellfeed.EachstoreislocatedonasegmentoftheXaxiswhoselengthisE(1<=E<=350).StoreiisatlocationX_i(0<X_i<E)onthenumberlinea...
02014年7月28日3,571贪心
「BZOJ1622」[Usaco2008 Open] Word Power 名字的能量
Description 约翰想要计算他那N(1≤N≤1000)只奶牛的名字的能量．每只奶牛的名字由不超过1000个字待构成，没有一个名字是空字体串，约翰有一张“能量字符串表”，上面有M(1≤M≤100)个代表能量的字符串．每个字符串由不超过30个字体构成，同样不存在空字符串．一个奶牛的名字蕴含多少个能量字符串，这个名字就有多少能量．所谓“蕴含”，是指某个能量字符串的所有字符都在名字串中按顺序出现（不一定一个紧接着一个...
02014年7月28日3,321模拟
「BZOJ1647」[Usaco2007 Open] Fliptile 翻格子游戏
DescriptionFarmerJohnknowsthatanintellectuallysatisfiedcowisahappycowwhowillgivemoremilk.HehasarrangedabrainyactivityforcowsinwhichtheymanipulateanMxNgrid(1<=M<=15;1<=N<=15)ofsquaretiles,eachofwhichiscoloredblackononesideandwhiteontheotherside.Asonewouldguess,whenasinglewhitetileisflipped,itchangestoblack;whenasingleblacktileisflipped,itchangestowhite.Thecowsarerewardedwhenth...
22014年7月28日7,003模拟
「BZOJ1645」[Usaco2007 Open] City Horizon 城市地平线
DescriptionFarmerJohnhastakenhiscowsonatriptothecity!Asthesunsets,thecowsgazeatthecityhorizonandobservethebeautifulsilhouettesformedbytherectangularbuildings.TheentirehorizonisrepresentedbyanumberlinewithN(1<=N<=40,000)buildings.Buildingi'ssilhouettehasabasethatspanslocationsA_ithroughB_ialongthehorizon(1<=A_i<B_i<=1,000,000,000)andhasheightH_i(1<=H_i<=1,000,000,...
32014年7月28日5,039线段树
「BZOJ1672」[Usaco2005 Dec] Cleaning Shifts 清理牛棚
DescriptionFarmerJohn'scows,pamperedsincebirth,havereachednewheightsoffastidiousness.Theynowrequiretheirbarntobeimmaculate.FarmerJohn,themostobligingoffarmers,hasnochoicebuthiresomeofthecowstocleanthebarn.FarmerJohnhasN(1<=N<=10,000)cowswhoarewillingtodosomecleaning.Becausedustfallscontinuously,thecowsrequirethatthefarmbecontinuouslycleanedduringtheworkday,whichrunsfromsecondnumbe...
02014年7月28日5,285递推与动规,线段树
「BZOJ1664」[Usaco2006 Open] County Fair Events 参加节日庆祝
DescriptionFarmerJohnhasreturnedtotheCountyFairsohecanattendthespecialevents(concerts,rodeos,cookingshows,etc.).HewantstoattendasmanyoftheN(1<=N<=10,000)specialeventsashepossiblycan.He'srentedabicyclesohecanspeedfromoneeventtothenextinabsolutelynotimeatall(0timeunitstogofromoneeventtothenext!).GivenalistoftheeventsthatFJmightwishtoattend,withtheirstarttimes(1<=T<=100,000)a...
02014年7月28日3,704递推与动规