图论(dfs bfs dijskra 多源最短路、floyd、bellman、spfa)
int dist[N], backup[N], n, m, k;
struct edge
{
int a, b, w;
}edge[N];
void bellman()
{
memset(dist, 0x3f3f3f3f, sizeof dist);
dist[1] = 0;
for(int i = 1; i <= k; i ++)
{
memcpy(backup, dist, sizeof dist);
for(int j = 1; j <= m; j ++)
{
int a = edge[j].a, b = edge[j].b, w = edge[j].w;
dist[b] = min(dist[b], backup[a]+ w);
}
}
}
const int N = 210;
int dist[N][N], n, m, t;
void floyd()
{
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
树状数组、线段树、懒标记线段树
//树状数组
int st[N], n, m;
int lowbit(int x)
{
return x & -x;
}
void add(int x, int v)
{
for(int i = x; i <= n; i += lowbit(i)) st[i] += v;
}
int query(int x)
{
int res = 0;
for(int i = x; i > 0; i -= lowbit(i)) res += st[i];
return res;
}
//线段树
using namespace std;
const int N = 1e5 + 10;
int st[N], n, m;
struct tr
{
int l, r;
int sum;
}tr[4 * N];
void pushup(int u)
{
tr[u].sum = tr[2 * u].sum + tr[2 * u + 1].sum;
}
void build(int u, int l, int r)
{
if(l == r) tr[u] = {l, r, st[l]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(2 * u, l, mid), build(2 * u + 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, int v)
{
if(tr[u].l == tr[u].r) tr[u].sum += v;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u * 2, x, v);
if(x > mid) modify(2 * u + 1, x, v);
pushup(u);
}
}
int query(int u, int l, int r)
{
if(l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
int sums = 0;
int mid = tr[u].r + tr[u].l >> 1;
if(l <= mid) sums += query(2 * u, l ,r);
if(r > mid) sums += query(2 * u + 1, l ,r);
return sums;
}
//懒标记+线段树
using namespace std;
const int N = 1e5 + 10;
int w[N], n, m;
struct tr
{
int l, r;
int sum, add;
}tr[4 * N];
void pushup(int u)
{
tr[u].sum = tr[2 * u].sum + tr[2 * u + 1].sum;
}
void pushdown(int u)
{
if(tr[u].add)
{
int k = tr[u].add;
tr[2 * u].add += k, tr[2 * u].sum += k * (tr[2 * u].r - tr[2 * u]. l + 1);
tr[2 * u + 1].add += k, tr[2 * u + 1].sum += k * (tr[2 * u + 1].r - tr[2 * u + 1]. l + 1);
tr[u].add = 0;
}
}
void build(int u, int l, int r)
{
if(l == r) tr[u] = {l, r, w[l], 0};
else
{
tr[u] = {l, r};
int mid = tr[u].l + tr[u].r >> 1;
build(2 * u, l, mid), build(2 * u + 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int x)
{
if(l <= tr[u].l && r >= tr[u].r)
{
tr[u].sum =tr[u].sum + x * (tr[u].r - tr[u].l + 1);
tr[u].add += x;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(2 * u, l, r ,x);
if(r > mid) modify(2 * u + 1, l, r, x);
pushup(u);
}
}
int query(int u, int l, int r)
{
if(l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
pushdown(u);
int sums = 0;
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) sums += query(2 * u, l , r);
if(r > mid ) sums += query(2 * u + 1, l ,r);
return sums;
}
数论（埃氏筛质数、欧几里得、扩展欧几里得、约数个数约数之和、快速幂、费马小逆元）
哈希、邻接表
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
string s1, s2;
const int N = 35;
int t1[N], t2[N], cnt1, cnt2;
int h[N], e[10 * N], ne[10 * N], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int qmi(int a, int k)
{
int res = 1;
while(k)
{
if(k & 1) res = res * a;
k = k >> 1;
a = a * a;
}
return res;
}
int check(int k)
{
int kk = 2, u = t1[cnt1];
for(int i = cnt1 - 1; i >= 1; i --)
{
u += kk * t1[i];
kk = kk * 2;
}
if(t1[k] == 0)
{
u += qmi(2, cnt1 - k);
return u;
}
else
{
u -= qmi(2, cnt1 - k);
return u;
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> s1 >> s2;
for(int i = 0; i < s1.size(); i ++) t1[++ cnt1] = (int)s1[i] - 48;
for(int i = 0; i < s2.size(); i ++) t2[++ cnt2] = (int)s2[i] - 48;
int kk = 3, u = t2[cnt2];
for(int i = cnt2 - 1; i >= 1; i --)
{
u += kk * t2[i];
kk = kk * 3;
}
int nums = 1;
for(int i = cnt2; i >= 1; i --)
{
if(nums == 1)
{
for(int j = 1; j + t2[cnt2] < 3; j ++)
{
add(nums, u + j);
}
for(int j = 1; t2[cnt2] - j >= 0; j ++)
{
add(nums, u - j);
}
nums ++;
continue;
}
int pp = qmi(3, nums - 1);
for(int j = 1; j + t2[i] < 3; j ++)
{
add(nums, u + (pp * j));
}
for(int j = 1; t2[i] - j >= 0; j ++)
{
add(nums, u - (pp * j));
}
nums ++;
}
if(t1[1] == 0 && t1[2] == 0 && t1[3] == 0 && t1[4] == 0)
{
cout << 8;
return 0;
}
for(int i = cnt1; i >=1; i --)
{
int ans = check(i);
for(int j = 1; j < nums; j ++)
{
for(int f = h[j]; ~f; f = ne[f])
{
if(ans == e[f])
{
cout << e[f];
return 0;
}
}
}
}
}
并查集
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
Trie
3485最大异或和
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 1e6 + 10;
const int M = 31 * N;
int son[M][2], cnt[4 * M], nums[4 * M], st[N], n, k, idx;
void add(int x)
{
int p = 0;
for(int i = 31; i >= 0; i --)
{
int t = x >> i & 1;
if(!son[p][t]) son[p][t] = ++ idx;
p = son[p][t];
cnt[p] ++;
}
nums[p] = x;
}
void delt(int x)
{
int p = 0;
for(int i = 31; i >= 0; i --)
{
int t = x >> i & 1;
if(!son[p][t]) son[p][t] = ++ idx;
p = son[p][t];
cnt[p] --;
}
}
int find(int x)
{
int p = 0;
for(int i = 31; i >= 0; i --)
{
int t = x >> i & 1;
if(cnt[son[p][!t]]) p = son[p][!t];
else p = son[p][t];
}
return nums[p];
}
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i ++)
{
cin >> st[i];
st[i] = st[i] ^ st[i - 1];
}
add(0);
int res = 0;
for(int i = 1; i <= n; i ++)
{
if(i > k) delt(st[i - k - 1]);
res = max(res, find(st[i]) ^ st[i]);
add(st[i]);
}
cout << res;
return 0;
}
常用stl（map、queue、vector、priority_queue）
