赞
踩
- //定义
- int head=-1,e[N],ne[N],idx=0;
- //头插
- void add(int x)
- {
- e[idx]=x;
- ne[idx]=head;
- head=idx++;
- }
- //在第k位后插入
- void insert(int k,int x)
- {
- e[idx]=x;
- ne[idx]=ne[k];
- ne[k]=idx++;
- }
- //删除第k位
- void del(int k)
- {
- ne[k]=ne[ne[k]];
- }
后进先出
- //定义
- int q[N],tt;
- //入栈
- q[tt++]=x;
- //取栈顶元素
- q[tt]
- //出栈
- tt--;
先进先出
- //定义
- int q[N],hh=0,tt=-1;
- //入队
- q[++tt]=x;
- //出队
- q[hh++]
- //判断是否为空
- tt-hh>=0
字典树:高效地存储字符串
- //定义
- int son[N][26],idx=0,cnt[N];
- //插入
- void insert(char str[])
- {
- int p=0;
- for(int i=0;str[i];i++)
- {
- int x=str[i]-'a';
- if(!son[p][x]) son[p][x]=++idx;
- p=son[p][x];
- }
- }
- //查询
- int query(char str[])
- {
- int p=0;
- for(int i=0;str[i];i++)
- {
- int x=str[i]-'a';
- if(!son[p][x]) return 0;
- p=son[p][x];
- }
- return cnt[p];
- }
并查集的主要操作是合并和查找,这两个操作的核心是find根节点。
合并是将一个集合的根节点直接指向另一个集合的根节点。
查找是从当前结点开始往上,判断父节点是否为根节点,查找过程中进行路径压缩,将当前遍历到的结点直接指向根节点。
- //初始化
- for(int i=1;i<=n;i++) p[i]=i;
-
- //find(带路径压缩)
- int find(int x)
- {
- if(p[x]!=x) p[x]=find(p[x]);
- return p[x];
- }
-
- //合并
- int pu=find(u),pv=find(v);
- if(pu!=pv) p[pu]=pv;
以小根堆为例。
每插入一个数,需要堆堆进行down或up,down表示使大数往下,up表示使小数往上,通过这两个操作,可以维持小根堆堆顶元素最大的性质。
需要注意的是,当我们要删除堆中的某个元素时,并不是直接删去,因为删去数组中特定位置的数是非常困难的,而删去数组末尾的数非常容易,因此采用的方式是先将元素和堆尾元素互换,删去堆尾元素,再执行down或up。
- //插入元素
- heap[++idx]=x;
- up(idx);
-
- //删除元素
- swap(heap[1],heap[idx--]);
- down(1);
-
- void down(int u)
- {
- int t=u;
- if(2*u<=idx&&heap[2*u]<heap[t]) t=2*u;
- if(2*u+1<=idx&&heap[2*u+1]<heap[t]) t=2*u+1;
- if(u!=t)
- {
- swap(heap[t],heap[u]);
- down(t);
- }
- }
-
- void up(int u)
- {
- while(u/2&&heap[u/2]>heap[u])
- {
- swap(heap[u/2],heap[u]);
- u/=2;
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。