`
Coco_young
  • 浏览: 125707 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论
文章列表
区间翻转:由于以root为根的树的中序遍历表示该区间,那么翻转只要递归的交换左右子树即可,加入lazy思想,降低时间复杂度。 Tips:做区间翻转的时候rev[rt]的含义是——以rt为根的子树所表示的区间是否将要被翻转,目前并没有执行翻转操作,如果改成先翻转,再标记,就会出现大问题。 Code:没用的push_down写多了。 /*http://acm.hdu.edu.cn/showproblem.php?pid=3487*/ /*splay区间切割+翻转*/ #include<iostream> #include<cstdio> #include< ...
/*http://poj.org/problem?id=3468*/ /*区间更新,区间求和*/ /*注意各种编码细节,特别是splay buildTree和 rotateTo*/ /*仔细体会与线段树解决区间问题的不同点,如结点记录的信息是不同的*/ /*lazy思想*/ #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 111111; class SplayTree{ #define l(x) (ch[x][0]) ...
/*http://acm.hdu.edu.cn/showproblem.php?pid=1754*/ /*单点更新,区间询问 splay实现*/ /*注意写rotateTo的时候。。*/ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 222222; class SplayTree{ #define l(x) (ch[x][0]) #define r(x) ( ...
(1) template<class DataType> class SplayTree{ #define MAXN 1000010 private: int ch[MAXN][2],pre[MAXN],pool[MAXN]; DataType key[MAXN]; int top,root,tot; int malloc(DataType dt){ int x; if(top!=0) x = pool[--top]; else x = ++tot; key[x] = dt; ...
template<class DataType> class SplayTree{ #define null 0 private: int MAXSIZE; int *l,*r,*p,*pool,*depth; int top,root,tot; DataType *key; int malloc(DataType k){ int node; if(top!=0){ node = pool[--top]; }else{ node = ++tot; ...
传送门:http://codeforces.com/contest/266/problem/E 代码: #include<iostream> #include<cstdio> #include<cmath> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define mid(x,y) (x+y)>>1 #define mod 1000000007 typedef long long LL; const int ...
本博客之前所有的求和符号都写成了segma。。。。。。。。。。 英语巨烂的弱菜表示错的深刻。。 所以如果有人看到segma什么的,就自动转型成sigma吧。。。 求和==sigma
如果不了解next数组前缀后缀特性的请看我以前写的一道题:http://blog.csdn.net/airarts_/article/details/7686441 传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2594 题目大意:给定字符串s1,s2要求出s1的最长前缀,同时还是s2的最长后缀,输出该字符串和其长度. 解题思路:利用前缀后缀特性,把两个字符串接起来,按照前面那题的方法,来求前缀后缀子串,注意其终止条件的变化,这里前缀后缀子串的长度必须小于s1,s2长度的最小值。 代码: #include<iostream&g ...
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1358 题目大意:给定一个字符串,求出所有循环的前缀串,输出前缀串的长度和循环的次数(大于一才算循环串) 思路:同上一道题一样,也是求循环节,这里,枚举长度为2-N的所有前缀串(next数组可以一次预处理求出),求出其最小循环节,判断前缀串长度是否可以整除循环节长度整除,并且前缀串长度不等于循环节长度,满足条件就输出。 代码: #include<iostream> using namespace std; const int MAXN = 1111111; int N,next[M ...
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3746 题目大意:给定一个字符串,求出最少在末尾添加几个字符使得字符串成为循环串。 解题思路:先求出最小循环节,如果最小循环节长度等于字符串长度,则添加的字符数为字符串的长度,否则用字符串的长度模循环节的长度,如果为0,说明已经是循环串,如果非0,说明还要添加字符串长度减去该值个字符. 代码: #include<iostream> using namespace std; const int MAXN = 111111; int T,next[MAXN]; char s[MAXN] ...
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3336 题目大意:给定一个字符串(1-200000),求出其所有前缀在自身中匹配成功的次数之和(模10007) 解题思路:利用next数组的特性,next[pos]在主串指针在pos位置失配时,子串指针应该调整到next[pos]与pos进行比较,这意味着0-(next[pos]-1)的字符串应该和(pos-next[pos])-(pos-1)字符串相同,而0-(next[pos]-1)的字符串正好是该字符串的前缀,解法就很自然了,在获得字符串0-N的next值,枚举i属于[1,N],记录pos = ...
传送门:http://acm.hnu.cn/online/?action=problem&type=show&id=12307 题目大意:给定一个联通图,求出能有多少种不同的方式去除两个不同的点使得原图变的不联通。 关于解题:这道是上次校赛的一道题,比赛当时没仔细想,也没仔细看数据,压根就没想枚举割点,后来听解题报告的时候恍然大悟,这道题可以先用tarjan求一次割点,然后对于此次求出的割点,剩下任意的点都可以与割点构成一对(注意判重),对于非割点,那么考虑去除它,再求一次割点,这次出现的那么被去除的点与这次求出的割点同样构成一组(注意去重),那么累加起来就是结果。(PS:我 ...
传送门:http://poj.org/problem?id=3450 题目大意:前面那道题类似,求多个字符串的最长且字典序最小的公共子串,还是枚举子串,然后拿去和剩余主串匹配,保存最优解。 代码: #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 222,MAXM = 4444; char s[MAXM][MAXN],temp[MAXN],res[MAXN]; int next[MAXN],n; void makenex ...
传送门:http://acm.hnu.cn/online/?action=problem&type=show&id=10069&courseid=0 题目描述:给定若干个二维平面上 的点,如果a.x<=b.x&&a.y>=b.y则说a的等级比b高(如果a==b,则他们等级相同),要求对于每个点,输出比他等级高的点的总数。 解题思路:把星星按照y的递减序和x的递增序排序,然后对x轴建立树状数组,依次将每个星星插入树状数组(在插入前统计出1-当前坐标和区间和,记录下来),然后再把相同的星星的记录下来的数据换成他们之中第一个被插入树状数组的星星的 ...
转自:http://blog.csdn.net/badboyfind/article/details/1816189 自己的话:由于要做软件二的实验,很多同学问我为什么自己的VC6.0老是不能正常编译,所以贴过来,免得屡次回答,以下是原文。 可能很多人在安装VC 6.0后有过点击“Compile”或者“Build”后被出现的 “Compiling... ,Error spawning cl.exe”错误提示给郁闷过。很多人的 选择是重装,实际上这个问题很多情况下是由于路径设置的问题引起的, “CL.exe”是VC使用真正的编译器(编译程序),其路径在“VC根目录/VC98/Bi ...
Global site tag (gtag.js) - Google Analytics