Trie树
这是一个用来高效存储与查找字符串集合的数据结构注意要标记每个字符串的结尾
[Trie树] [c++]123456789101112131415161718192021222324252627282930313233#include<bit/stdc++.h>using namespace std;const ing N=100010;int sun[N][26],cnt[N],idx; //每一个节点最多26个边 子节点就设置26 cnt表示以当前这个点结尾的词有多少个 idx表示当前用到了哪个下标 下标为0 既是根节点 又是空节点//插入 void insert(char str[]) { int p=0; for(int i=0;str[i];i++) //c++字符串结尾为/0 { int u=str[i]-'a'; 将a-z映射为0-25 if(!son[p][u]) son[p][u]=++idx; //如果遍历到的该字母未出现过，开辟新空间存储该字母 p= ...
kmp字符串
如果是朴素做法 暴力循环
[字符串暴力循环] [c++]12345678910s[N],p[N];for(int i=1;i<=n;i++){ bool flag =true; for(int j=1;j<=m;j++) { if s[i]!=p[i] flag=false; break }}
我们发现匹配慢就是因为回溯的步骤太多了 所以要优化代码不好理解 但是原理简单首先得知道最长前缀和最长后缀怎么求我们发现匹配慢就是因为回溯的步骤太多了
[升级算法] [c++]1234567891011121314151617181920212223242526272829303132333435#include<bits/stdc++.h>using namespace std;const int N=10010，M=10010；int n,m;char p[N],s[M];int ne[N];//定义next[N]概率性报错int main(){ cin>& ...
栈和队列
栈 先进后出 就像一个桶一样 先进的到栈底 最后进的是栈顶队列 先进先出
[模拟栈] [c++]12345678910111213141516略const int N=100010;int stk[N],tt; tt表示栈顶下标//插入stk[++tt] =x;//弹出tt--；//判断栈是否为空if(tt>0) not emptyelse empty//栈顶stk[tt];
单调栈很抽象 类似于删掉逆序的对 最后得到单调的栈单调栈主要解决以下问题：寻找下一个更大元素寻找前一个更大元素寻找下一个更小元素寻找前一个更小元素 诸如此类有点抽象 类似于删掉逆序的对 最后得到单调的栈例 给定一个长为N的整数数列 输入每个数左边第一个比它小的数 不存在则-1
[单调栈] [c++]12345678910111213141516171819202122#include<bits/stdc++.h>using namespace std;const int N=100010;int n,stk[N],tt;int main(){ ios::sync_with_st ...
区间合并
比较简单的一个小算法 直接上代码
[区间合并] [c++]123456789101112131415161718192021222324252627282930313233343536373839#include<bits/stdc++.h>using namespace std;typedef pair<int,int>PII;const int N=100010;int nlvector<PII> segs;void merge(vector<PII> &segs){ vector<PII> res; sort(segs.begin(),segs.end());//由左端点排序 int st=-2e9,ed=-2e9 //初始化左右端点无穷小 for(auto seg:segs) if(ed<seg.first) //如果当前枚举区间在右边 没有任何交集 { if(st!=-2e9) res.push_back(&# ...
离散化
是一种极其特殊的hash方式 必须保序把无限空间中有限的个体映射到有限的空间中去以提高空间效率
[离散化vector] [c++]12345678910111213141516vector<int> a;//用普通数组也不是不行 操作差不多sort(a.begin(),a.end()); //将所有元素排序a.erase(unique(a.begin(),a.end()),a.end()); //去重 unique非重复的元素在数组开头 erase返回下标到最后中间的元素 就是去重int find(int x) //找到第一个大于等于x的位置 当然也可以lower_bound{ int l=0,r=a.size()-1; while(l<r) { int mid=(l+r)>>1; if(a[mid]>=x) r=mid; else l=mid+1; } return l+1； 储存是从0开始的 加1 元素映射到1到n 不加1就是映射到0到n-1 ...
快速幂
普通的函数写循环 时间就寄了 所以需要快速幂已知(ab)%c=((a%c)(b%c))%c 可以初步优化 但是依然不够核心思想就是每一步都把指数分成两半 而相应的底数做平方运算 如3^10=33333333333^10=(33)(33)(33)(33)(33)3^10=(33)^53^10=9^5而当指数为奇数时 指数减一化为偶数9^5=（9^4）（9^1）继续操作9^5=（81^2）*(9^1)9^5=（6561^1）*(9^1)最后(9^1)(6561^1)=96561=59049最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积
求a的b次方取余1000
[快速幂] [c++]1234567891011121314151617long long FastPower(long long base,long long power){ long long result=1; while(power>0) { if ...
