专栏文章

可爱的板子们

江江湖午餐票
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzjhjr
此快照首次捕获于
2025/12/01 18:07
3 个月前
此快照最后确认于
2025/12/01 18:07
3 个月前
查看原文

可爱的板子们

-std=c++14 -O2 -Wshadow -Wall -Wextra

快速幂

C
ll qpow(ll a,ll b,ll p)
{
	ll res = 1;
	while(b)
	{
		if(b&1) res = (res*a)%p;
		a = (a*a)%p; 
		b = b>>1; 
	}
	return res;
}

字符串哈希

本质就是 base 进制数，所以有以下公式：
pref0=0prefi=(prefi−1×base+si−1) mod phash(sl…r)=(prefr+1−prefl×baser−l+1 mod p+p) mod ppref_0 = 0 \newline pref_i = (pref_{i-1} \times base + s_{i-1}) \bmod p \newline hash(s_{l\dots r}) = (pref_{r+1} - pref_{l} \times base^{r-l+1} \bmod p + p) \bmod p
其中 prefipref_i 表示前 ii 个数的哈希值。
C
pair<ull,ull> hashh(const string &s)
{
    const int b = 131;const ull p1 = 1e9+7,p2 = 1e9+9;
   	ull h1 = 0,h2 = 0;
    for(int i=0;i<s.size();i++)
    {
        h1 = ((1ull*h1*b)%p1+(1ull*s[i])%p1)%p1;
        h2 = ((1ull*h2*b)%p2+(1ull*s[i])%p2)%p2;
    }	
    return make_pair(h1,h2);
}

单调队列 单调栈

单调队列
C
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N = 1e6+5;
int n,k,a[N];
deque <pair<int,int> > q;
int main()
{
	cin >> n >> k;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&q.back().first>a[i]) q.pop_back();
		q.push_back(mp(a[i],i));
		while(!q.empty()&&q.front().second<=i-k) q.pop_front();
		if(i >= k) cout << q.front().first << ' ';
	}
	q.clear();
	cout << "\n";
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&q.back().first<a[i]) q.pop_back();
		q.push_back(mp(a[i],i));
		while(!q.empty()&&q.front().second<=i-k) q.pop_front();
		if(i >= k) cout << q.front().first << ' ';
	}
	return 0;	
}
单调栈
C
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N = 3e6+5;
int n,a[N],f[N];
deque <pair<int,int> > q;
int main()
{
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&a[i]>q.back().first)
		{
			f[q.back().second] = i;
			q.pop_back();
		} 
		q.push_back(mp(a[i],i));
	}
	for(int i=1;i<=n;i++) cout << f[i] << ' '; 
	return 0;	
}

最小生成树

考场打过不写了

并查集

MST 要用，所以肯定会（）

LCA

倍增写法
C
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N = 5e5+5;
int n,m,s; 
// Graph
struct Edge
{
	int nxt,to;	
}e[2*N];
int h[N],cnt;
inline void add(int u,int v){ e[++cnt] = Edge{h[u],v}; h[u] = cnt; }
// lca
int f[20][N],d[N]; 
void dfs(int u)
{
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v = e[i].to;
		if(v==f[0][u]) continue;
		f[0][v] = u;
		d[v] = d[u]+1; 
		dfs(v);
	}
}
void init()
{
	for(int j=1;j<=18;j++)
		for(int i=1;i<=n;i++)
			f[j][i] = f[j-1][f[j-1][i]];
}
int lca(int x,int y)
{
	if(d[x]<d[y]) swap(x,y);
	for(int j=18;j>=0;j--) if(d[f[j][x]]>=d[y]) x = f[j][x];
	if(x == y) return x;
	for(int j=18;j>=0;j--)
		if(f[j][x]!=f[j][y]) x=f[j][x],y=f[j][y];
	return f[0][x];
} 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> s;
	for(int i=1,x,y;i<n;i++) 
	{
		cin >> x >> y;
		add(x,y),add(y,x);
	}
	d[s] = 1;
	dfs(s);
	init();
	for(int i=1,x,y;i<=m;i++) 
	{
		cin >> x >> y;
		cout << lca(x,y) << '\n';
	}
	return 0;	
}

Dijistra

C
int dis[N];
void dijistra(int s)
{
	priority_queue <pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
	int vis[N];
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	q.push(mp(0,s));dis[s]=0;
	while(!q.empty())
	{
		int u=q.top().second;q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].to,w=e[i].val;
			dis[v]=min(dis[u]+w,dis[v]);
			q.push(mp(dis[v],v));
		}
	}
}

SPFA

C
bool spfa(int s)
{
	queue <int> q;
	int vis[N],cnt[N];
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	memset(cnt,0,sizeof(cnt));
	dis[s] = 0,vis[s] = 1;q.push(s);cnt[s]++;
	while(!q.empty())
	{
		int u = q.front();q.pop();vis[u] = 0;
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].to,w=e[i].val;
			if(dis[u]+w>=dis[v]) continue;
			dis[v]=dis[u]+w;
			if(vis[v]) continue;
			q.push(v);
			vis[v] = 1; // 这里不要漏了
			if(++cnt[v]>=n) return 1;
		}
	}
	return 0;
}

拓扑排序

C
int ru[N];
void topo()
{
	queue <int> q;
	for(int i=1;i<=n;i++) if(!ru[i]) q.push(i);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			// dp
			if(!(--ru[v])) q.push(v);
		}
	}
}

差分约束

建模而已，记得超级源点即可。

ST 表

C
void init()
{
	lg2[1] = 0;
	for(int i=2;i<=100000;i++) lg2[i] = lg2[i>>1]+1;
	for(int i=1;i<=n;i++) f[0][i] = a[i];
	for(int j=1;j<=lg2[n];j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			f[j][i] = max(f[j-1][i],f[j-1][i+(1<<(j-1))]);
}
max⁡{x∈R:l≤x≤r}=\max\{x \in \mathbb{R} : l \leq x \leq r\} = max(f[k][l],f[k][r-(1<<k)+1])，其中 k = lg2[r-l+1]。

树状数组

单点加 区间和
最基础的树状数组，build 用 add 代替。
C
int c[N],n;
inline void add(int x,int k) { for(;x<=n;x+=(x&(-x))) c[x] += k; }
inline int qry(int x) { int res = 0; for(;x;x-=(x&(-x))) res += c[x]; return res;}
区间加 单点值
维护差分数组即可。
C
inline void add_range(int x,int y,int k) { add(x,k); add(y+1,-k); }
inline int qry_node(int x) { return qry(x); }

离线二维数点

题面
一个长为 nn 的序列 aa，有 mm 次询问，每次询问给定 l,r,xl,r,x，求 [l,r][l,r] 区间中小于等于 xx 的元素个数。
解法
将所有查询 [l,r][l,r] 离线并差分 [1,l−1][1,l-1] 和 [1,r][1,r]，值域树状数组维护当前满足条件的元素个数。
C
const int N = 2e6+5,M = 2e6+5;
int n,m,a[N],ans[M];
// BIT
int c[N];
void add(int x) { for(;x<N;x+=(x&(-x))) c[x] += 1; } // 注意：一直修改到值域最大范围！！！
int qry(int x) { int res = 0; for(;x;x-=(x&(-x))) res += c[x]; return res; }
// line
struct line
{
	int u,x,i,f;
	// [1,u] <= x ans[i]+=f*____
	friend bool operator < (const line &L,const line &R) { return L.u < R.u;}
}l[2*M];
int main()
{
	cin >> n >> m;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=m;i++) 
	{
		int _l,_r,_x;
		cin >> _l >> _r >> _x;
		l[i] = line{_l-1,_x,i,-1};l[i+m] = line{_r,_x,i,1};
	}
	sort(l+1,l+1+2*m);
	int j = 0;
	for(int i=1;i<=2*m;i++)
	{
		while(j<l[i].u) add(a[++j]);
		ans[l[i].i] += qry(l[i].x)*l[i].f;
	}
	for(int i=1;i<=m;i++) cout << ans[i] << "\n";
	return 0;
}

组合数学

预处理阶乘及其逆元、组合数、排列数。
C
void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    inv_fact[n] = qpow(fact[n], MOD - 2);
    for (int i = n-1; i >= 0; i--) {
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    }
}

ll C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * inv_fact[m] % MOD * inv_fact[n-m] % MOD;
}

ll A(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * inv_fact[n-m] % MOD;
}

树链剖分

优先跳 depth[top[x]] 小的。

KMP

这个太熟悉了，可以现场推。

AC 自动机

C
struct trie_node
{
	int son[26],cnt,fail;	
}trie[N];
int trie_tot = 0;
void insert(string x)
{
	int u = 0;
	for(int i=0;i<x.size();i++)
	{
		if(!trie[u].son[x[i]-'a']) trie[u].son[x[i]-'a'] = ++trie_tot;
		u = trie[u].son[x[i]-'a'];
	}
	trie[u].cnt ++;
}
void build()
{
	queue <int> q;
	for(int i=0;i<26;i++)
		if(trie[0].son[i]) q.push(trie[0].son[i]);
	while(!q.empty())
	{
		int u = q.front();q.pop();
		for(int i=0;i<26;i++)
		{
			int v = trie[u].son[i];
			if(v)
			{
				trie[v].fail = trie[trie[u].fail].son[i];
				q.push(v);
			}else trie[u].son[i] = trie[trie[u].fail].son[i];
		}
	}
}
int query(string x)
{
	int u = 0,res = 0;
	for(int i=0;i<x.size();i++)
	{
		u = trie[u].son[x[i]-'a'];
		for(int v=u;v&&trie[v].cnt!=-1;v=trie[v].fail)
		{
			res += trie[v].cnt;
			trie[v].cnt = -1;
		}
	}
	return res;
}

Trie 树

看上面的也能看会了吧。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...