一些板子

willAK · 2025-09-27 15:54:36 · 算法·理论

本文章记录一些题目板子，考前记得看一看。

1.快速幂

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,p;
int qpow(int a,int b)
{
    int ans=1ll%p;
    while(b!=0)
    {
        if(b&1)
        {
            ans=ans*a%p;
        }
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}
int main()
{
    cin>>a>>b>>p;
    cout<<a<<"^"<<b<<" mod "<<p<<"="<<qpow(a,b);
    return 0;
}

2.排列组合数

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int fact[200010];
int infact[200010]; 
int A(int x,int y){return fact[x]*infact[x-y]%mod;}
int C(int x,int y){return fact[x]*infact[x-y]%mod*infact[y]%mod;}
int qpow(int a,int b){
    int ans=1ll%mod;
    while(b!=0){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans%mod;
}
signed main()
{
    fact[0]=infact[0]=1;
    for(int i=1;i<200001;i++)
    {
        fact[i]=fact[i-1]*i%mod;
        infact[i]=infact[i-1]*qpow(i,mod-2)%mod;
    }
    return 0;
}

3.Dijkstra算法模版

#include<bits/stdc++.h> 
using namespace std;
int from[100010],to[200010],net[200010],v[200010],cnt,d[100010];
bool b[100010];
void add(int x,int y,int w)
{
    to[++cnt]=y;
    v[cnt]=w;
    net[cnt]=from[x];
    from[x]=cnt;
}
priority_queue <pair<int,int> > q;
int main()
{
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    for(int i=1;i<=n;i++)
    {
        d[i]=1e9;
    }
    d[s]=0;
    q.push({0,s});
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop(); 
        if(b[x]) continue;
        b[x]=1;
        for(int i=from[x];i;i=net[i])
        {
            int y=to[i],l=v[i];
            if(d[y]>d[x]+l)
            {
                d[y]=d[x]+l;
                q.push({-d[y],y});
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<d[i]<<" ";
    }
    return 0;
}

4.字典树板子

#include<bits/stdc++.h>
using namespace std;
int t[3000010][75];
int ans[3000010];
int id=0;
int change(char k)
{
    if(k>='A' && k<='Z') return k-'A';
    else if(k>='a' && k<='z') return k-'a'+26;
    else if(k>='0' && k<='9') return k-'0'+52;
}
void insert(string s)
{
    int p=0;
    for(int i=0;i<s.size();i++)
    {
        int c=change(s[i]);
        if(t[p][c]==0) t[p][c]=++id;
        p=t[p][c];
        ans[p]++;
    }
}
int answer(string s)
{
    int p=0;
    for(int i=0;i<s.size();i++)
    {
        int c=change(s[i]);
        if(t[p][c]==0) return 0;
        p=t[p][c]; 
    }
    return ans[p];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        for(int i=0;i<=id;i++)
        {
            for(int j=0;j<=65;j++)
            {
                t[i][j]=0;
            }
        }
        for(int i=0;i<=id;i++)
        {
            ans[i]=0;
        }
        id=0;
        int n,q;
        cin>>n>>q;
        for(int i=1;i<=n;i++)
        {
            string s;
            cin>>s;
            insert(s);
        }
        while(q--)
        {
            string s;
            cin>>s;
            cout<<answer(s)<<"\n";
        }
    }
    return 0;
}