hzwer.com - Page 75

「BZOJ1684」[Usaco2005 Oct] Close Encounter
DescriptionLackingevenafifthgradeeducation,thecowsarehavingtroublewithafractionproblemfromtheirtextbook.Pleasehelpthem.Theproblemissimple:Givenaproperlyreducedfraction(i.e.,thegreatestcommondivisorofthenumeratoranddenominatoris1,sothefractioncannotbefurtherreduced)findthesmallestproperlyreducedfractionwithnumeratoranddenominatorintherange1..32,767thatisclosest(butnotequal)tothegivenfraction.找...
02014年7月29日2,572模拟

「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日11,923树链剖分,离线处理
「BZOJ1349」[Baltic2006] Squint
DescriptionWriteaprogramtocalculateintegersquareroots.InputTheinputisreadfromatextfilenamedsquint.in.Itsonlylineconsistsofaninteger0<=n<2^63.OutputItsonlylineconsistsofthesmallestnonnegativeintegerqsuchthatq^2>=n.SampleInput122333444455555SampleOutput11060446HINTsqrt(122333444455555)=11060445.038765619.题解直接sqrt(n)真是神题啊[crayon-67ab8717764bf883108296/] ...
02014年7月28日2,893模拟
「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日3,863递推与动规
「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,437贪心
「BZOJ1622」[Usaco2008 Open] Word Power 名字的能量
Description 约翰想要计算他那N(1≤N≤1000)只奶牛的名字的能量．每只奶牛的名字由不超过1000个字待构成，没有一个名字是空字体串，约翰有一张“能量字符串表”，上面有M(1≤M≤100)个代表能量的字符串．每个字符串由不超过30个字体构成，同样不存在空字符串．一个奶牛的名字蕴含多少个能量字符串，这个名字就有多少能量．所谓“蕴含”，是指某个能量字符串的所有字符都在名字串中按顺序出现（不一定一个紧接着一个...
02014年7月28日3,103模拟
「BZOJ1647」[Usaco2007 Open] Fliptile 翻格子游戏
DescriptionFarmerJohnknowsthatanintellectuallysatisfiedcowisahappycowwhowillgivemoremilk.HehasarrangedabrainyactivityforcowsinwhichtheymanipulateanMxNgrid(1<=M<=15;1<=N<=15)ofsquaretiles,eachofwhichiscoloredblackononesideandwhiteontheotherside.Asonewouldguess,whenasinglewhitetileisflipped,itchangestoblack;whenasingleblacktileisflipped,itchangestowhite.Thecowsarerewardedwhenth...
22014年7月28日6,603模拟
「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日4,819线段树
「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,120递推与动规,线段树
「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,570递推与动规
「BZOJ1683」[Usaco2005 Nov] City skyline 城市地平线
DescriptionInput第1行：2个用空格隔开的整数N和W.第2到N+1行：每行包括2个用空格隔开的整数x,y，其意义如题中所述．输入中的x严格递增，并且第一个z总是x．Output输出一个整数，表示城市中最少包含的建筑物数量．SampleInput10261122516381110152173202221INPUTDETAILS:ThecasementionedaboveSampleOutput6题解同1628[crayon-67ab87177885a185409555/] ...
02014年7月28日3,534单调栈
「CF444C」DZY Loves Colors
DZYlovescolors,andheenjoyspainting.Onacolorfulday,DZYgetsacolorfulribbon,whichconsistsof n units(theyarenumberedfrom 1 to n fromlefttoright).Thecolorofthe i-thunitoftheribbonis i atfirst.Itiscolorfulenough,butwestillconsiderthatthecolorfulnessofeachunitis 0 atfirst.DZYlovespainting,weknow.Hetakesupapaintbrushwithcolor x andusesittodrawalineontheribbon.Insuchacasesomecont...
02014年7月28日4,293线段树