数据结构 - Page 28

「BZOJ1067」[SCOI2007] 降雨量
Description我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意Y＜Z＜X，Z年的降雨量严格小于X年。例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890，则可以说“2005年是自2003年以来最多的”，但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。Input输入仅一行包含一个正整数n，为已知的数据。...
32014年2月19日9,099线段树

「CODEVS1690」开关灯
题目描述Description YYX家门前的街上有N(2<=N<=100000)盏路灯，在晚上六点之前，这些路灯全是关着的，六点之后，会有M(2<=m<=100000)个人陆续按下开关，这些开关可以改变从第i盏灯到第j盏灯的状态，现在YYX想知道，从第x盏灯到第y盏灯中有多少是亮着的(1<=i,j,x,y<=N)输入描述InputDescription第1行:用空格隔开的两个整数N和M第2..M+1行:每行表示一个操作,有三个用空格分开的整数:指令号(0代...
02014年2月15日3,309线段树
「CODEVS1191」数轴染色
题目描述Description在一条数轴上有N个点，分别是1～N。一开始所有的点都被染成黑色。接着我们进行M次操作，第i次操作将[Li,Ri]这些点染成白色。请输出每个操作执行后剩余黑色点的个数。输入描述InputDescription输入一行为N和M。下面M行每行两个数Li、Ri输出描述OutputDescription输出M行，为每次操作后剩余黑色点的个数。样例输入SampleInput103335728样例输出SampleOutput963数据范围及提示DataSize&...
82014年2月15日3,502线段树
「CF295B」Greg and Graph
Greghasaweigheddirectedgraph,consistingof n vertices.Inthisgraphanypairofdistinctverticeshasanedgebetweentheminbothdirections.Greglovesplayingwiththegraphandnowhehasinventedanewgame:Thegameconsistsof n steps.Onthe i-thstepGregremovesvertexnumber xi fromthegraph.AsGregremovesavertex,healsoremovesalltheedgesthatgoinandoutofthisvertex.Beforeexecutingeachstep,Gregwantstoknowthesumofle...
02014年2月14日4,287floyd,离线处理
「CODEVS1553」互斥的数
题目描述 Description有这样的一个集合，集合中的元素个数由给定的N决定，集合的元素为N个不同的正整数，一旦集合中的两个数x,y满足y = P*x，那么就认为x,y这两个数是互斥的，现在想知道给定的一个集合的最大子集满足两两之间不互斥。输入描述 InputDescription输入有多组数据，每组第一行给定两个数N和P（1<=N<=10^5, 1<=P<=10^9）。接下来一行包含N个不同正整数ai（1<=ai<=10^9）。输出描述 ...
02014年2月13日4,034哈希表
「CODEVS1229」数字游戏
题目描述DescriptionLele 最近上课的时候都很无聊，所以他发明了一个数字游戏来打发时间。这个游戏是这样的，首先，他拿出几张纸片，分别写上0到9之间的任意数字(可重复写某个数字)，然后，他叫同学随便写两个数字X和K。Lele要做的事情就是重新拼这些纸牌，组成数字 T ，并且 T + X 是 K 的正整数倍。有时候，当纸片很多的时候，Lele经常不能在一节课之内拼出来，但是他又想知道答案，所以，他想请你帮忙写...
22014年2月13日3,712深度搜索,哈希表
「fzyzoj1969」无敌的妹子2
Descriptionhttp://110.90.118.124/OnlineJudge/problem_show.php?id=1969 土豪无敌有很多相机，因为需要秀相机，所以需要拍很多妹纸，现在，无敌招募了n只妹纸，从1到n编号摆在架子上。现在无敌要给妹纸穿各种衣服来增加妹纸的美丽值（由于无敌很正直，他懒得把妹纸的衣服卸下来，只会不停地给妹纸穿衣服（妹纸：热出翔）他经常会把某个让他很不爽的区间内的妹纸全部替换掉；或者给某个区间内的妹纸都穿上某种...
02014年2月12日4,607线段树
「usaco2002.4」Power Hungry Cows
题目描述农夫约翰的奶牛可以很快地计算整数的次方，但是需要你的帮助。因为他们将要计算很大的数的次方（还是数的很大次方……我英语，悲剧），他们只能使用两个工作变量来处存临时结果。第一个动作变量被赋值为底数（用X表示）；另一个赋值为1.牛们既能把两个变量相乘也能相除，并存储在任一工作变量中，但是所有结果都被存为整数（只能存为整数？我按这个做的AC）。例如，他们想计算X^31，一种方法是这样的[crayon-674334b12...
02014年2月5日3,450哈希表,广度搜索
无聊写的A+B问题。。。
输入A,B输出A+B[crayon-674334b123779898546636/]
42014年2月3日8,993kruskal,spfa,最小割,背包动规,线段树,floyd,树状数组
「BZOJ3038」上帝造题的七分钟2
DescriptionXLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。"第一分钟，X说，要有数列，于是便给定了一个正整数数列。第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。第三分钟，k说，要能查询，于是便有了求一段数的和的操作。第四分钟，彩虹喵说，要是NOIP难度，于是便有了数据范围。第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。第六分钟，和雪说，要省点事，于是...
02014年1月26日6,023线段树
「CODEVS1299」切水果
题目描述 Description简单的说,一共N个水果排成一排,切M次,每次切[L,R]区间的所有水果(可能有的水果被重复切),每切完一次输出剩下水果数量输入描述 InputDescription第1行共包括2个正整数，分别为N,M。接下来m行每行两个正整数L,R输出描述 OutputDescription一共输出M行,每行输出切完之后剩下水果数量样例输入 SampleInput103352815样例输出 SampleOutput732数据范围及提示 DataSize&Hint30%的数据...
02014年1月25日3,400线段树
「SWUST0433」高精度整数去位去最小问题
Description键盘输入一个高精度的正整数N，去掉其中任意M个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和M寻找一种方案使得剩下的数字组成的新数最小。输出组成的新的正整数。(不超过240位)输入数据均不需判错。如果去掉了某几个位后得到的新整数开头为0，保留0。Input本题有多组测试数据，每组测试数据占一行。一个高精度正整数N（N不超过240位）一个正整数M。(M为不大于N的长度的正整数)N,M由...
02014年1月21日3,512链表