可爱的板子们

· · 个人记录

可爱的板子们

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

快速幂

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 进制数，所以有以下公式：

pref_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

其中 pref_i 表示前 i 个数的哈希值。

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);
}

单调队列 单调栈

单调队列

#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;   
}

单调栈

#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

倍增写法

#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

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

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;
}

拓扑排序

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 表

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))]);
}
## 树状数组 **单点加 区间和** 最基础的树状数组，`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); } ``` ## 离线二维数点 **题面** 一个长为 $n$ 的序列 $a$，有 $m$ 次询问，每次询问给定 $l,r,x$，求 $[l,r]$ 区间中小于等于 $x$ 的元素个数。 **解法** 将所有查询 $[l,r]$ 离线并差分 $[1,l-1]$ 和 $[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 树 看上面的也能看会了吧。