板子整理

434天前 · 题解 · 全部文章 · 504次阅读

算法竞赛用到的某些模板

板子整理

[x-link url="https://wwp.lanzouq.com/iaFYB1q4dlgh" title="pdf版本链接" /]

字符串

KMP算法

#include <bits/stdc++.h>
using namespace std;
string s1,s2;
int ne[1000010];
int main(){
    cin>>s1>>s2;
    int len1=s1.size();
    int len2=s2.size();
    s1=' '+s1;
    s2=' '+s2;
    ne[1]=0;
    int j=0;
    for(int i=2;i<=len2;i++){
        while(j!=0&&s2[j+1]!=s2[i]) j=ne[j];
        if(s2[j+1]==s2[i])j++;
        ne[i]=j;
    }
    j=0;
    for(int i=1;i<=len1;i++){
        while(j!=0&&s2[j+1]!=s1[i])j=ne[j];
        if(s2[j+1]==s1[i])j++;
        if(j==len2){
            cout<<i-len2+1<<'\n';
            j=ne[j];
        }
    }
    for(int i=1;i<=len2;i++)cout<<ne[i]<<" ";
}

字典树

int n,m,tot,tag[(int)(3e6+10)];
map<char,int>mp;
int trie[(int)(3e6+10)][63];
void insert(char *s){
    int len=strlen(s+1),p=0;
    for(int i=1;i<=len;i++){
        if(!trie[p][mp[s[i]]]) trie[p][mp[s[i]]]=++tot;
        p=trie[p][mp[s[i]]]; 
        tag[p]++;
    }
}
int query(char *s){
    int len=strlen(s+1),p=0;
    for(int i=1;i<=len;i++){
        if(!trie[p][mp[s[i]]]) return 0;
        p=trie[p][mp[s[i]]]; 
    }
    return tag[p];
}
char s[(int)(3e6+10)];
signed main(){
    int t,id=0;cin>>t;
    for(char i='a';i<='z';i++) mp[i]=++id;
    for(char i='A';i<='Z';i++) mp[i]=++id;
    for(char i='0';i<='9';i++) mp[i]=++id;
    while(t--){
        cin>>n>>m;
        for(int i=0;i<=tot;i++){
            tag[i]=0;
            for(int j=0;j<=62;j++){
                trie[i][j]=0;
            }
        }
        tot=0;
        for(int i=1;i<=n;i++){
            cin>>(s+1);
            insert(s);
        }
        for(int i=1;i<=m;i++){
            cin>>(s+1);
            cout<<query(s)<<"\n";
        }
    }
    system("pause > null");
}

杂

ST表

int lg[1000100];
int f[1000100][22];
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>f[i][0];
    }
    for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(int j=1;(1 << j) <= n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    while(m--){
        int l,r;cin>>l>>r;
        int len=lg[r-l+1];
        cout<<max(f[l][len],f[r-(1<<len)+1][len])<<'\n';
    }

逆序对

void add(int c,int x){
    for(int i=c;i<=500008;i+=lowbit(i)){
        tr[i]+=x;
    }
}
int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)){
        res+=tr[i];
    }
    return res;
}
void init(){
    sort(q.begin(),q.end());
    q.erase(unique(q.begin(),q.end()),q.end());
    for(int i=1;i<=q.size();i++){
        weizhi[q[i-1]]=i;
    }
}
signed main(){
    cin>>n;
    int a;
    for(int i=1;i<=n;i++){
        cin>>a;
        q.push_back(a);
        q1.push_back(a);
    }
    init();
    int res=0;
    int cnt=1;
    for(auto i:q1){
        add(weizhi[i],1);
        res+=cnt-query(weizhi[i]);
        cnt++;
    }
    cout<<res;

博弈论

巴什博弈(Bash Game)

一堆n个物品，两个人从轮流中取出(1~m)个；最后取光者胜(不能继续取的人输)。

同余定理 : n = K (m + 1) + r；先取者拿走r个，那么后者无论拿走(1~m)个先者只要拿的数目的和为m + 1那么先手就必赢。反之若n = k (m + 1), 那么先者不论怎样都会输。

if (n % (m + 1) return false;
else return true;

威佐夫博弈(Wythoff Game)

有两堆琟各若干个物品，两个人轮流从任意一堆琟中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。

黄金分割比；首先求出差值，差值 * 黄金分割比 = 最小值 的话后手嬴，否则先手赢。

double r = (sqrt(5.0) + 1) / 2;
int d = abs(a - b) * r;
if (d != min(a, b))return true;
else return false;

尼姆博弈(Nimm Game)

n堆物品，两人轮流取，每次取某堆中不少于1个，最后取完者胜。

结论 : 将n堆琟物品数量全部异或后结果为0则必败，否则必胜。

尼姆博弈的结论是很重要的，但是证明过程较为繁琐。

int res = 0;
for (int i = 1; i = n; i++)
res = res ^ arr[i];
if (res) return true;
else return false;

栈与队列

滑动窗口

int d[1001000];
deque < pair<int,int> >q;
signed main(){
    int n,k;cin>>n>>k;
    int t=1;
    for(int i=1;i<=n;i++){
        cin>>d[i];
    }
    //找最小
    for(int i=1;i<=n;i++){
        while(!q.empty()&&q.back().xx>=d[i]){
            q.pop_back();
        }
        q.push_back({d[i],i});
        if(!q.empty()&&i-q.front().yy+1>k)q.pop_front();
        if(i>=k){
            cout<<d[q.front().yy]<<" ";
        }
    }

最大矩形面积

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            cin >> g[i][j]; 
            if (g[i][j] == 'Q')
                h[i][j] = h[i - 1][j] + 1;   

        }
    }
    stack<PII> st;
    int ans = 0;

    for (int i = 1; i <= n; i ++)
    {
        st.push({h[i][1], 1});
        for (int j = 2; j <= m+1; j ++)
        {
            int len = 0;
            while(st.size() && h[i][j] <= st.top().first)
            {
                len += st.top().second;   // 长度累加
                ans = max(ans, len * st.top().first);  // 计算当前能构成最大矩形面积
                st.pop();
            }
            a[i][j] = {h[i][j], len + 1};   //高度比他高的合并起来，底的长度为所有高于它的长度 + 1(它本身)
            st.push(a[i][j]);  // 入栈
        }
    }
    cout << ans;

树状数组

单点修改 区间查询

int tr[500010];
int n;

void add(int x, int c){
    for (int i = x; i <= n; i += lowbit(i)){
        tr[i] += c;
    }
}

int search(int m){
    int res = 0;
    for (int i = m; i > 0; i -= lowbit(i)){
        res += tr[i];
    }
    return res;
}
add(b, c);
search(c) - search(b - 1)

区间修改 单点查询

void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i))
    {
        tr[i] += c;
    }
}

int search(int m)
{
    int res = 0;
    for (int i = m; i > 0; i -= lowbit(i))
    {
        res += tr[i];
    }
    return res;
}
add(b,d);
add(c+1,-d);
cout << search(b) +q[b] << '\n';

数论

位运算基础

运算运算符
与&
或\
异或^

快速幂

int qmi(int a, int b){
    a %= M;
    int res = 1;
    while (b){
        if (b&1) res = res * a % M;
        a = a * a % M;
        b >>= 1;
    }
    return res;
}

欧拉函数

1 ∼ n 中与 n 互质的数的个数被称为欧拉函数

若 i 为质数，φ(i) = i − 1

当 p | i 时，由于 p 已经是 i 的最小质因子，所以 φ(i × p) = φ(i) × p 当 p ∤ i 时，此时 p 是 i × p 的一个新的最小质因子，所以 φ(i × p) = φ(i) × (p − 1)

int primes[N],phi[N];
bool st[N];
void get_eulers(int n){
 phi[1] = 1;//特殊规定
 int cnt = 0;
 for(int i = 2;i<=n;i++){
 if(!st[i]){
  primes[cnt++] = i;
  phi[i] = i-1;
 }
 for(int j = 0;primes[j]<=n/i;j++){
  st[primes[j]*i] = true;
  if(i%primes[j]==0){
  phi[primes[j]*i] = phi[i]+primes[j];
  break;
  }
  phi[primes[j]*i] = phi[i]*(primes[j]-1);
 }
 }
}

模意义下的乘法逆元

这里 a 模 p 的乘法逆元定义为 ax≡1(mod p) 的解。

ll inv[maxn]={0,1};
   for(int i=2;i<=n;i++)
       inv[i]=(ll)p-(p/i)*inv[p%i]%p,printf("%d\n",inv[i]);

树

树形dp

void dfs(int no,int fa){
    for(auto i:q[no]){
        if(i==fa) continue;
        dfs(i,no);
        g[no]+=fmax(0,g[i]);
    }
}

for(int i=1;i<=n;i++){
    ans=max(g[i],ans);
}

线段树

int n,m,a[1000005],mod;
struct node{
    ll sum,l,r,mu,add;
}t[1000005];
ll read(){
    ll x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
void build(ll p,ll l,ll r){
    t[p].l=l,t[p].r=r;t[p].mu=1;
    if(l==r){t[p].sum=a[l]%mod;return ;}
    ll mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
void spread(ll p){
    t[p*2].sum=(ll)(t[p].mu*t[p*2].sum+((t[p*2].r-t[p*2].l+1)*t[p].add)%mod)%mod;
    t[p*2+1].sum=(ll)(t[p].mu*t[p*2+1].sum+(t[p].add*(t[p*2+1].r-t[p*2+1].l+1))%mod)%mod;//add已经乘过mu啦
    
    t[p*2].mu=(ll)(t[p*2].mu*t[p].mu)%mod;
    t[p*2+1].mu=(ll)(t[p*2+1].mu*t[p].mu)%mod;

    t[p*2].add=(ll)(t[p*2].add*t[p].mu+t[p].add)%mod;
    t[p*2+1].add=(ll)(t[p*2+1].add*t[p].mu+t[p].add)%mod;
    
    t[p].mu=1,t[p].add=0;
}
void add(ll p,ll l,ll r,ll k){
    if(t[p].l>=l&&t[p].r<=r){
        t[p].add=(t[p].add+k)%mod;
        t[p].sum=(ll)(t[p].sum+k*(t[p].r-t[p].l+1))%mod;//只要加上增加的就好
        return ;
    }
    spread(p);
    t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
    ll mid=(t[p].l+t[p].r)>>1;
    if(l<=mid)add(p*2,l,r,k);
    if(mid<r)add(p*2+1,l,r,k);
    t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
    
}
void mu(ll p,ll l,ll r,ll k){
    if(t[p].l>=l&&t[p].r<=r){
        t[p].add=(t[p].add*k)%mod;//比较重要的一步,add要在这里乘上k,因为后面可能要加其他的数而那些数其实是不用乘k的
        t[p].mu=(t[p].mu*k)%mod;
        t[p].sum=(t[p].sum*k)%mod;
        return ;
    }
    spread(p);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
    ll mid=(t[p].l+t[p].r)>>1;
    if(l<=mid)mu(p*2,l,r,k);
    if(mid<r)mu(p*2+1,l,r,k);
    t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
ll ask(ll p,ll l,ll r){
    if(t[p].l>=l&&t[p].r<=r){
        return t[p].sum;
    }
    spread(p);
    ll val=0;
    ll mid=(t[p].l+t[p].r)>>1;
    if(l<=mid)val=(val+ask(p*2,l,r))%mod;
    if(mid<r)val=(val+ask(p*2+1,l,r))%mod;
    return val;
}
int main(){
    cin>>n>>m>>mod;
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int ty=read();
        if(ty==1){
            ll cn=read(),cm=read(),cw=read();
            mu(1,cn,cm,cw);
        }else if(ty==2){
            ll cn=read(),cm=read(),cw=read();
            add(1,cn,cm,cw);
        }else {
            ll cn=read(),cm=read();
            cout<<ask(1,cn,cm)<<endl;
        }
    }
}

图论

最短路dij

int dis[200010];
bool st[100100];
priority_queue<PII,vector<PII> ,greater<PII>> q;
vector<PII> num[100010];
void dd(int s){
    memset(dis,0x3f,sizeof dis);
    memset(st, 0, sizeof st);
    q.push({0,s});
    dis[s]=0;
    while(q.size()){
        auto no=q.top();
        q.pop();
        int npos=no.second,nw=no.first;
        if(st[no.second])continue;
        st[npos]=1;
        for(auto u:num[npos]){
            auto upos=u.second,uw=u.first;
            if(dis[upos]>dis[npos]+uw){
                dis[upos]=dis[npos]+uw;
                q.push({dis[upos],upos});
            }
        }
    }
}

二分图匹配

const int N = 1010, M = 50010;
int matched[N], ans;
set<int> t[N];
bool st[N];
bool find(int x){
    for (auto i : t[x]){
        if (!st[i]){
            st[i] = true;
            if (!matched[i] || find(matched[i]))
            {
                matched[i] = x;
                return true;
            }
        }
    }
    return false;
}
for (int i = 1; i <= n; i++){
        memset(st, 0, sizeof st);
        if (find(i))
            ans++;
    }

拓扑排序

    for (int i = 1; i <= n; i++) {
        int x;
        while (cin >> x && x) {
            t[i].push_back(x);
            out[x]++;
        }
    }
    queue<int> ans;
    for (int i = 1; i <= n; i++) {
        if (out[i] == 0) {
            ans.push(i);
    }
    }
    while (!ans.empty()) {
        int u = ans.front();
        ans.pop();
        cout << u << ' ';
        for (int v : t[u]) {
            out[v]--;
            if (out[v] == 0) {
                ans.push(v);
            }
        }
    }

并查集&&最小生成树

int find(int x){
    if(p[x]==x) return x;
    return p[x]=find(p[x]);
}
struct node
{
    int x,y,l;
    bool operator<(node a){
        return l<a.l;
    }
} node[200010];
int ss=1;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>node[i].x>>node[i].y>>node[i].l;
    }
    sort(node+1,node+m+1);
    long long ans=0;
    int idx=1;
    for(int i=1;i<=n;i++)p[i]=i;
    while(idx<=m){
        if(find(node[idx].x)!=find(node[idx].y)){
            p[find(node[idx].x)]=find(node[idx].y);
            ans=ans+node[idx].l;
            ss++;
        }
        idx++;
    }

    if(ss==n)cout<<ans<<'\n';
    else cout<<"orz";
}
👍 3

none

最后修改于338天前

评论

目录

avatar

coolarec

你好，未曾谋面的陌生人

31

文章数

16

评论数

5

分类

那就出发吧！

❤ 99

  • 赛事游记
  • 日常
  • coding
  • 全部