基础数据结构 - Page 7

「BZOJ2141」排队
Description排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为：满足ihj的(i,j)数量。幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方...
42014年7月26日18,456分块

「BZOJ1628」[Usaco2007 Demo] City skyline
DescriptionThebestpartofthedayforFarmerJohn'scowsiswhenthesunsets.Theycanseetheskylineofthedistantcity.Bessiewondershowmanybuildingsthecityhas.Writeaprogramthatassiststhecowsincalculatingtheminimumnumberofbuildingsinthecity,givenaprofileofitsskyline.Thecityinprofileisquitedullarchitecturally,featuringonlybox-shapedbuildings.Theskylineofacityonthehorizonissomewherebetween1andWunitswide(1&...
02014年7月23日3,690单调栈
「czy系列赛」czy的后宫3
czy的后宫3「题目描述」上次czy在机房妥善安排了他的后宫之后，他发现可以将他的妹子分为c种，他经常会考虑这样一个问题：在[l,r]的妹子中间，能挑选出多少不同类型的妹子呢？注意：由于czy非常丧尸，所以他要求在所挑选的妹子类型在[l,r]中出现次数为正偶数，你懂得。问题简述:n个数，m次询问，每次问[l,r]区间有多少个数恰好出现正偶数次「输入格式」第一行3个整数，表示n,c,m第二行n个数，每个数Ai在[1,c]之间，表示一个Ai类型...
42014年7月19日11,014树状数组,离线处理,莫队算法
「BZOJ2821」作诗(Poetize)
Description神犇SJY虐完HEOI之后给傻×LYD出了一题：SHY是T国的公主，平时的一大爱好是作诗。由于时间紧迫，SHY作完诗之后还要虐OI，于是SHY找来一篇长度为N的文章，阅读M次，每次只阅读其中连续的一段[l,r]，从这一段中选出一些汉字构成诗。因为SHY喜欢对偶，所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数（两个一样的汉字称为同一种）越多越好...
32014年7月19日8,771分块
「BZOJ2724」[Violet 6] 蒲公英
Description Input修正一下l=(l_0+x-1)modn+1,r=(r_0+x-1)modn+1OutputHINT修正下：n<=40000,m<=50000题解在线区间众数的分块做法比较多，这里提供一个思路：首先离散化一下比较方便。最初可能会有一个想法，是不是众数只可能是完整的块的众数，或者不完整的块出现的数呢？显然很容易得出反例。应该是完整的所有块的众数，和不完整块中出现的数。所以我们可以预处理f(i,j)表示第i块到第j块的众数（枚举i开个桶扫...
32014年7月6日13,636分块
「BZOJ1012」[JSOI2008] 最大数maxnumber
Description现在请求你维护一个数列，要求提供以下两种操作：1、查询操作。语法：QL功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、插入操作。语法：An功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有...
42014年6月15日12,823线段树,单调栈,单调队列
「BZOJ2388」旅行规划
DescriptionOIVillage是一个风景秀美的乡村，为了更好的利用当地的旅游资源，吸引游客，推动经济发展，xkszltl决定修建了一条铁路将当地n个最著名的经典连接起来，让游客可以通过火车从铁路起点（1号景点）出发，依次游览每个景区。为了更好的评价这条铁路，xkszltl为每一个景区都哦赋予了一个美观度，而一条旅行路径的价值就是它所经过的景区的美观度之和。不过，随着天气与季节的变化，某些景点的美观度也会发生变化。xkszlt...
42014年5月29日6,135分块,二分法
「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日4,396离线处理
「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日7,399递推与动规,单调队列
「CF433C」Ryouko’s Memory Note
Ryoukoisanextremelyforgetfulgirl,shecouldevenforgetsomethingthathasjusthappened.Soinordertoremember,shetakesanotebookwithher,called Ryouko'sMemoryNote.Shewriteswhatsheseesandwhatshehearsonthenotebook,andthenotebookbecamehermemory.ThoughRyoukoisforgetful,sheisalsobornwithsuperbanalyzingabilities.However,analyzingdependsgreatlyongatheredinformation,inotherwords,memory.Soshehastoshufflethr...
02014年5月24日4,241链表
「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,594递推与动规,单调队列
「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日7,906线段树,离线处理