数据结构 - Page 23

「BZOJ2506」calc
Description 给一个长度为n的非负整数序列A1,A2,…,An。现有m个询问，每次询问给出l,r,p,k，问满足l<=i<=r且Aimodp=k的值i的个数。Input 第一行两个正整数n和m。第二行n个数，表示A1,A2,…,An。以下m行，每行四个数分别表示l,r,p,k。满足1<=l<=r<=n。Output 对于每个询问，输出一行，表示可行值i的个数。SampleInput521...
12014年5月28日3,865离线处理

「BZOJ1651」[Usaco2006 Feb] Stall Reservations 专用牛棚
DescriptionOhthosepickyN(1<=N<=50,000)cows!TheyaresopickythateachonewillonlybemilkedoversomeprecisetimeintervalA..B(1<=A<=B<=1,000,000),whichincludesbothtimesAandB.Obviously,FJmustcreateareservationsystemtodeterminewhichstalleachcowcanbeassignedforhermilkingtime.Ofcourse,nocowwillsharesuchaprivatemomentwithothercows.HelpFJbydetermining:*Theminimumnumberofstallsreq...
02014年5月28日3,829线段树
「BZOJ1828」[Usaco2010 Mar] balloc 农场分配
DescriptionInput第1行：两个用空格隔开的整数：N和M*第2行到N+1行：第i+1行表示一个整数C_i*第N+2到N+M+1行：第i+N+1行表示2个整数A_i和B_iOutput*第一行：一个整数表示最多能够被满足的要求数SampleInput541321313252345SampleOutput3题解贪心，按照右端点排序以后冲突的舍弃[crayon-662ffb2b33983170280698/] ...
02014年5月28日3,807贪心,线段树
「BZOJ1112」[POI2008] 砖块Klo
DescriptionN柱砖,希望有连续K柱的高度是一样的.你可以选择以下两个动作1:从某柱砖的顶端拿一块砖出来,丢掉不要了.2:从仓库中拿出一块砖,放到另一柱.仓库无限大.现在希望用最小次数的动作完成任务.Input第一行给出N,K.(1≤k≤n≤100000),下面N行,每行代表这柱砖的高度.0≤hi≤1000000Output最小的动作次数SampleInput5339231SampleOutput2HINT原题还要求输出结束状态时,每柱砖的高度.本题略去.题解据说有很多做法，...
32014年5月27日5,615treap
「JoyOI1360」Imperishable Shooting
背景Background如果您不想看这个扯淡的背景，可以直接移步Hint，有简洁版。。。一天，蓬莱の魚の形误闯了迷途森林，于是光荣地迷路了。。此时，一个白发红眼的少女出现了。。少女：你迷路了吗？蓬莱の魚の形：。。是。。少女：你叫什么名字？蓬莱の魚の形：蓬莱の魚の形。。少女（仔细打量其一番）：本来还准备帮你的，但是一想到一个妖怪鱼有这个名字。。。就让我看看你有多大本事吧！（突然从背后扇动出熊熊燃烧的翅膀）「Imp...
02014年5月25日4,909treap,几何
「BZOJ2442」[Usaco2011 Open] 修剪草坪
Description在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。FJ有N(1<=N<=100,000)只排成一排的奶牛，编号为1...N。每只奶牛的效率是不同的，奶牛i的效率为E_i(0<=E_i<=1,000,000,000)。靠近的奶牛们很熟悉，因此，如果FJ安排超过K只连续的奶牛，...
92014年5月24日6,385递推与动规,单调队列
「CF433C」Ryouko’s Memory Note
Ryoukoisanextremelyforgetfulgirl,shecouldevenforgetsomethingthathasjusthappened.Soinordertoremember,shetakesanotebookwithher,called Ryouko'sMemoryNote.Shewriteswhatsheseesandwhatshehearsonthenotebook,andthenotebookbecamehermemory.ThoughRyoukoisforgetful,sheisalsobornwithsuperbanalyzingabilities.However,analyzingdependsgreatlyongatheredinformation,inotherwords,memory.Soshehastoshufflethr...
02014年5月24日3,648链表
「BZOJ1636」[Usaco2007 Jan] Balanced Lineup
DescriptionForthedailymilking,FarmerJohn'sNcows(1<=N<=50,000)alwayslineupinthesameorder.OnedayFarmerJohndecidestoorganizeagameofUltimateFrisbeewithsomeofthecows.Tokeepthingssimple,hewilltakeacontiguousrangeofcowsfromthemilkinglineuptoplaythegame.However,forallthecowstohavefuntheyshouldnotdiffertoomuchinheight.FarmerJohnhasmadealistofQ(1<=Q<=200,000)potentialgroupsofcow...
32014年5月23日3,490ST表
「BZOJ1233」[Usaco2009Open] 干草堆tower
Description奶牛们讨厌黑暗。为了调整牛棚顶的电灯的亮度，Bessie必须建一座干草堆使得她能够爬上去够到灯泡。一共有N大包的干草（1<=N<=100000）(从1到N编号)依靠传送带连续的传输进牛棚来。第i包干草有一个宽度W_i(1<=w_i<=10000)。所有的干草包的厚度和高度都为1.Bessie必须利用所有N包干草来建立起干草堆，并且按照他们进牛棚的顺序摆放。她可以相放多少包就放多少包来建立起tower的地基（当然是紧紧的放在...
12014年5月20日5,058递推与动规,单调队列
「BZOJ1782」[Usaco2010 Feb] slowdown慢慢游
Description每天FarmerJohn的N头奶牛(1<=N<=100000，编号1…N)从粮仓走向他的自己的牧场。牧场构成了一棵树，粮仓在1号牧场。恰好有N-1条道路直接连接着牧场，使得牧场之间都恰好有一条路径相连。第i条路连接着A_i，B_i，(1<=A_i<=N;1<=B_i<=N)。奶牛们每人有一个私人牧场P_i(1<=P_i<=N)。粮仓的门每次只能让一只奶牛离开。耐心的奶牛们会等到他们的前面的朋友们到达了自己的私人牧场后才...
02014年5月18日2,753树状数组
「BZOJ3585」mex
Description　　有一个长度为n的数组{a1,a2,...,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。Input　　第一行n,m。第二行为n个数。从第三行开始，每行一个询问l,r。Output　　一行一个数，表示每个询问的答案。SampleInput55210213323241235SampleOutput12303HINT数据规模和约定对于100%的数据：1<=n,m<=2000000<=ai<=1091<=l<=r<=n对于30%的数据：1<=n,m<=1000Source此题为...
02014年5月18日6,772线段树,离线处理
「BZOJ3339」Rmq Problem
DescriptionInputOutputSampleInput7502101321323143627SampleOutput30324HINT题解这一题在线似乎比较麻烦至于离线。。首先按照左端点将询问排序然后一般可以这样考虑首先如何得到1-i的sg值呢这个可以一开始扫一遍完成接着考虑l-r和l+1-r的答案有何不同显然是l-next[l]-1这一段所有sg值大于a[l]的变为a[l]这一步如果暴力修改的话只有30分但是修改区间我们可以想到线段树，这样就能a了[crayon-662ffb2b37d66754214753/]&...
12014年5月17日8,169线段树,离线处理