DS
+++
1.单调栈
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int stk[N], tt;
int n;
int main()
{
scanf("%d", &n);
int x;
for (int i = 0; i < n; i ++ )
{
scanf("%d", &x);
while(tt && stk[tt] >= x) tt -- ;
if(tt) printf("%d ", stk[tt]);
else printf("-1 ");
stk[ ++ tt ] = x;
}
cout << endl;
return 0;
}
2.滑动窗口
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N], hh, tt = -1;
int m, n;
int main()
{
scanf("%d%d", &m, &n);
for (int i = 0; i < m; i ++ ) scanf("%d", a + i);
for (int i = 0; i < m; i ++ )
{
if(hh <= tt && i - n + 1 > q[hh]) hh ++ ;
while(hh <= tt && a[q[tt]] >= a[i]) tt -- ;
q[ ++ tt ] = i;
if(i >= n - 1) printf("%d ", a[q[hh]]);
}
puts("");
for (int i = 0; i < m; i ++ )
{
if(hh <= tt && i - n + 1 > q[hh]) hh ++ ;
while(hh <= tt && a[q[tt]] <= a[i]) tt -- ;
q[ ++ tt ] = i;
if(i >= n - 1) printf("%d ", a[q[hh]]);
}
puts("");
return 0;
}
3.KMP
#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1;
for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
for (int i = 1, j = 0; i <= m; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == n)
{
printf("%d ", i - n);
j = ne[j];
}
}
return 0;
}
4.Trie树
#include <iostream>
using namespace std;
const int N = 2e4 + 10;
int son[N][26], cnt[N], idx;
char str[N];
void insert(char str[])
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;
}
int query(char str[])
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if(!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
int main()
{
int n;
scanf("%d", &n);
char op[2];
while ( n -- )
{
scanf("%s%s", op, str);
if(op[0] == 'I') insert(str);
else printf("%d
", query(str));
}
return 0;
}
5.合并集合
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int m, n, p[N];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
while(m -- )
{
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
if(op[0] == 'M') p[find(a)] = find(b);
else
{
if(find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
6.堆排序
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int h[N], idx;
int m, n;
void down(int u)
{
int t = u;
if(u * 2 <= idx && h[u * 2] < h[t]) t = u * 2;
if(u * 2 + 1 <= idx && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if(u != t)
{
swap(h[t], h[u]);
down(t);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", h + i);
idx = n;
for (int i = n / 2; i; i -- ) down(i);//O(n)
while (m -- )
{
printf("%d ", h[1]);
h[1] = h[idx -- ];
down(1);
}
puts("");
return 0;
}
7.模拟散列表
拉链法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100003;
int h[N], e[N], ne[N], idx;
int n;
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x, ne[idx] = h[k], h[k] = idx ++ ;
}
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if(e[i] == x)
return true;
return false;
}
int main()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
while (n -- )
{
int t;
char op[2];
scanf("%s%d", op, &t);
if(op[0] == 'I') insert(t);
else
if(find(t)) puts("Yes");
else puts("No");
}
return 0;
}
开放寻址法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200003, null = 0x3f3f3f3f;
int h[N];
int n;
int find(int x)
{
int k = (x % N + N) % N;
while(h[k] != null && h[k] != x)
{
k ++ ;
if( k == N) k = 0;
}
return k;
}
int main()
{
scanf("%d", &n);
memset(h, 0x3f, sizeof h);
while (n -- )
{
int t;
char op[2];
scanf("%s%d", op, &t);
if(*op == 'I') h[find(t)] = t;
else
if(h[find(t)] != null) puts("Yes");
else puts("No");
}
return 0;
}
8.字符串哈希
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;
int n, m;
char str[N];
ULL h[N], p[N];
int get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
scanf("%d%d%s", &n, &m, str + 1);
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + str[i];
}
while (m -- )
{
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if(get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}
STL
//vector
vector<int> v(10, 3);//10个vector 每个元素都是3
vector<int> v[10];
v.size()//O(1)
v.empty()//if empty return 1
v.clear()
front()/back()
push_back()/pop_back()
begin()/end()//迭代器 迭代器的++ -- 复杂度是O(logn)
vector<int>::iterator i = v.begin()//访问
//vector支持比较运算，按照字典序比较
//pair
pair<int, string> p;
p = make_pair(10, "abc");
p = {10, "abc"};
//string
string a;
size() == length()
a.substr(A, B);//A起始下标，B字串长度。如果省略B，那么直接输出到a串最后一位
printf("%s", a.c_str());
//queue
front()/back()
push()/pop()
queue<int> q;
q = queue<int>();//清空queue
//priority_queue
push()/top()/pop()
priority_queue<int> heap;//默认大根堆
priority_queue<int, vector<int>, greater<int>> heap;//小根堆
//set multiset
//set无重复元素，multiset有重复元素
insert()//O(logn)
find()//如果不存在返回end迭代器
count()//返回某一个值的数量
erase()//(1)输入一个x，删除所有x O(k + logn)(2)输入一个迭代器，删除迭代器
lower_bound(x)//返回大于等于x的最小的数的迭代器
upper_bound(x)//返回大于x的最小的数的迭代器
//map multimap
insert()//插入的是pair
erase()//输入的参数是pair或者迭代器
map<string, int> a;
a["abc"] = 1;//O(logn)
lower_bound(x)//返回大于等于x的最小的数的迭代器
upper_bound(x)//返回大于x的最小的数的迭代器
//unordered_set ...
//和上面类似，增删改查复杂度O(1)
//不支持lower_bound(x)，upper_bound(x)，迭代器++ --
+++
+++
1.最大异或对(Trie tree)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3100000, M = 1e5 + 10;
int son[N][2], a[M];
int n, idx;
void insert(int x)
{
int p = 0;
for (int i = 30; i >= 0; i -- )
{
int u = x >> i & 1;
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
}
int query(int x)
{
int p = 0, res = 0;
for (int i = 30; i >= 0; i -- )
{
int u = x >> i & 1;
if(son[p][!u])
{
p = son[p][!u];
res = res * 2 + !u;
}
else
{
p = son[p][u];
res = res * 2 + u;
}
}
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
int res = 0;
for (int i = 0; i < n; i ++ )
{
insert(a[i]);
int t = query(a[i]);
res = max(res, a[i] ^ t);
}
printf("%d
", res);
return 0;
}