我不能白给啊啊啊啊啊！！！！！
我会在这里将最近的考到的知识点罗列，也当是快速复习与刷题计划吧。
Part1 数论相关
计数类
Lucas定理
点击查看代码
const int Mod = ?;
int powM(int x, int y = Mod-2) {
int ret = 1;
while (y) {
if (y&1) ret = 1ll*ret*x%Mod;
x = 1ll*x*x%Mod, y >>= 1;
} return ret;
}
int fac[N], ifac[N];
void init() {
fac[1] = ifac[1] = fac[0] = ifac[0] = 1;
for (int i = 2; i < Mod; ++i) fac[i] = 1ll*fac[i-1]*i%Mod;
ifac[Mod-1] = powM(fac[Mod-1]);
for (int i = Mod-2; i; --i) ifac[i] = 1ll*ifac[i+1]*(i+1)%Mod;
}
int C(int x, int y) {
if (x < y) return 0;
if (!x || !y || x == y) return 1;
return 1ll*fac[x]*ifac[x-y]%Mod*ifac[y]%Mod;
}
int luc(int x, int y) {
if (x < y) return 0;
if (!x || !y || x == y) return 1;
return 1ll*C(x%Mod, y%Mod)*luc(x/Mod, y/Mod)%Mod;
}
Part2 数据结构
线段树
标准型（加乘）
点击查看代码
int sum[N<<2], taga[N<<2], tagm[N<<2], a[N];
void pushup(int &x, int y, int z) {x = plu(y, z);}
void build(int now, int L, int R) {
tagm[now] = 1;
if (L == R) {
sum[now] = a[L];
return ;
}
segc;
build(lc, L, mid), build(rc, mid+1, R);
pushup(sum[now], sum[lc], sum[rc]);
}
void pushdown(int now, int L, int R) {
segc;
sum[lc] = plu(mul(sum[lc], tagm[now]), mul(taga[now], mid-L+1));
sum[rc] = plu(mul(sum[rc], tagm[now]), mul(taga[now], R-mid));
tagm[lc] = mul(tagm[lc], tagm[now]);
tagm[rc] = mul(tagm[rc], tagm[now]);
taga[lc] = plu(mul(taga[lc], tagm[now]), taga[now]);
taga[rc] = plu(mul(taga[rc], tagm[now]), taga[now]);
taga[now] = 0, tagm[now] = 1;
}
void modifya(int now, int L, int R, int ql, int qr, ll val) {
if (ql <= L && R <= qr) {
sum[now] += val*(R-L+1);
taga[now] += val;
return ;
}
segc;
pushdown(now, L, R);
if (ql <= mid) modifya(lc, L, mid, ql, qr, val);
if (qr > mid) modifya(rc, mid+1, R, ql, qr, val);
pushup(sum[now], sum[lc], sum[rc]);
}
void modifym(int now, int L, int R, int ql, int qr, ll val) {
if (ql <= L && R <= qr) {
sum[now] = mul(sum[now], val);
taga[now] = mul(taga[now], val);
tagm[now] = mul(tagm[now], val);
return ;
}
segc;
pushdown(now, L, R);
if (ql <= mid) modifym(lc, L, mid, ql, qr, val);
if (qr > mid) modifym(rc, mid+1, R, ql, qr, val);
pushup(sum[now], sum[lc], sum[rc]);
}
ll ask(int now, int L, int R, int ql, int qr) {
if (ql <= L && R <= qr) return sum[now];
segc; int ret = 0;
pushdown(now, L, R);
if (ql <= mid) ret = plu(ret, ask(lc, L, mid, ql, qr));
if (qr > mid) ret = plu(ret, ask(rc, mid+1, R, ql, qr));
return ret;
}
兔队线段树
点击查看代码
int ans[N<<2];
double mx[N<<2];
int query(int now, int L, int R, double Lim) {
if (mx[now] <= Lim) return 0;
if (L == R) return 1;
segc;
if (mx[lc] <= Lim) return query(rc, mid+1, R, Lim);
return query(lc, L, mid, Lim)+ans[now]-ans[lc];
}
void update(int now, int L, int R, int pos, double val) {
if (L == R) {
ans[now] = 1;
mx[now] = val;
return ;
}
segc;
if (pos <= mid) update(lc, L, mid, pos, val);
else update(rc, mid+1, R, pos, val);
mx[now] = max(mx[lc], mx[rc]);
ans[now] = ans[lc]+query(rc, mid+1, R, mx[lc]);
}
Part3 字符串题
Part4 图论相关
最短路
Dijkstra
点击查看代码
int dis[N];
bool vis[N];
void dij(int S) {
for (int i = 1; i <= n; ++i) dis[i] = Inf;
dis[S] = 0;
priority_queue<pair<int, int> > q;
q.push(mp(0, S));
while (!q.empty()) {
int x = q.top().second; q.pop();
if (vis[x]) continue ;
vis[x] = true;
for (int i = head[x]; i; i = e[i].next) {
int y = e[i].to;
if (dis[y] > dis[x]+e[i].w) {
dis[y] = dis[x]+e[i].w;
if (!vis[y]) q.push(mp(-dis[y], y));
}
}
}
}
最小生成树
Kruskal重构树
点击查看代码
int f[N<<1];
void kru() {
sort(e+1, e+1+m, cmp);
for (int i = 1; i <= 2*n; ++i) fa[i] = i;
int ncnt = n;
for (int i = 1; i <= m; ++i) {
int fu = find(e[i].u), fv = find(e[i].to);
if (fu == fv) continue ;
fa[fu] = fa[fv] = ++ncnt;
add(ncnt, fu), add(fu, ncnt);
add(ncnt, fv), add(fv, ncnt);
val[cnt] = e[i].w;
}
}
割点和桥
Ex 码头
点击查看代码
#define ll long long
#define segc int mid = L+R>>1, lc = now<<1, rc = lc|1
int plu(int x, int y) {return (1ll*x+y)%Mod};
int mul(int x, int y) {return 1ll*x*y%Mod};