OI模板-算法

三分法

板子题：P3382 【模板】三分法

时间复杂度 $O(-\log \epsilon)$

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define double long double
#define N ((int)(15))
const double eps = 1e-6;

int n;
double l,r,a[N];
double f(double x)
{
    double ans=0;
    // 秦九韶算法
    for(int i=n; i>=0; i--)
        ans = ans * x + a[i];
    return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(5);
    cin >> n >> l >> r;
    for(int i=n; i>=0; i--) cin >> a[i]; // a1x^n + a2x^n-1 + ...
    while(fabs(r-l) > eps)
    {
        double mid = (l + r) * 0.5;
        if(f(mid-eps) < f(mid+eps)) l=mid;
        else r=mid;
    }
    cout << l << '\n';
    return 0;
}

---

黄金分

其实就是三分的常数优化版，用黄金分割比去分

const double PHI=0.6180339887498948482;
double l,r,d,fl,fr,ml,mr;
l = 0.0001, r = 10000.000, d = (r-l) * PHI;
fl = f(ml = r-d), fr = f(mr = l+d);
while(d > 4e-12)
{
    d *= PHI;
    if(fl <= fr)
    {
        r=mr; mr=ml; fr=fl; fl = f(ml = r-d);
    }else
    {
        l=ml; ml=mr; fl=fr; fr = f(mr = l+d);
    }
}
cout << fl << '\n';

---

排序算法

其他乱七八糟的毛用没有（归并、松氏基排除外，还没补上来，咕咕咕…）

基本上一个sort全部搞定

计数排序

时间复杂度 $O(n)$

空间复杂度 $O(\max\{n,\max\limits_{0<i\le n}a_i\})$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
int n,w,a[N],b[N],cnt[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i],++cnt[a[i]],w=max(w,a[i]);
    for(int i=1; i<=w; i++)cnt[i]+=cnt[i-1];
    for(int i=n; i>=1; i--)
        b[cnt[a[i]]--]=a[i];
    /*
    逆序
    for(int i=n; i>=1; i--)
        b[n-cnt[a[i]]+1]=a[i],--cnt[a[i]];
    */
    for(int i=1; i<=n; i++)
        cout << b[i] << " \n"[i==n];
    return 0;
}

基数排序

时间复杂度 $O(n)$

空间复杂度 $O(n)$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
int n,w,a[N],cnt[N];
void rdsort(int n,int *a)
{
    int *b=new int[n+5];
    int *cnt=new int[1<<8];
    int mask=(1<<8)-1;
    int *x=a,*y=b;
    for(int i=0; i<64; i+=8)
    {
        for(int j=0; j!=(1<<8); j++)cnt[j]=0;
        for(int j=1; j<=n; j++)++cnt[x[j]>>i&mask];
        for(int j=1; j!=(1<<8); j++)cnt[j]+=cnt[j-1];
        for(int j=n; j>=1; j--)y[cnt[x[j]>>i&mask]--]=x[j];
        swap(x,y);
    }
    delete[] b;
    delete[] cnt;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    rdsort(n,a);
    for(int i=1; i<=n; i++)
        cout << a[i] << " \n"[i==n];
    return 0;
}

---

CDQ分治

P3810 【模板】三维偏序（陌上花开）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
#define K (int)(2e5+15)
int n,k,pos;
struct node
{
    int x,y,z,w,ans;
    bool operator!=(node &o)const
        {return x!=o.x||y!=o.y||z!=o.z;}
}a[N],b[N],tmp[N];
int tree[K],cnt[N];
bool cmpx(node a,node b)
{
    if(a.x==b.x)
    {
        if(a.y==b.y)
            return a.z<b.z;
        return a.y<b.y;
    }
    return a.x<b.x;
}
bool cmpy(node a,node b)
{
    if(a.y==b.y)
        return a.z<b.z;
    return a.y<b.y;
}
#define lowbit(x) (x&(-x))
void add(int x,int v)
{
    while(x&&x<=k)
    {
        tree[x]+=v;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int res=0;
    while(x>=1)
    {
        res+=tree[x];
        x-=lowbit(x);
    }
    return res;
}
void cdq(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    int i=mid+1,j=l,res=0,cnt=0;
    for(;i<=r; i++)
    {
        while(a[j].y<=a[i].y&&j<=mid)
        {
            add(a[j].z,a[j].w);
            tmp[++cnt]=a[j++];
        }
        a[i].ans+=sum(a[i].z);
        tmp[++cnt]=a[i];
    }
    for(int i=l; i<j; i++)
        add(a[i].z,-a[i].w);
    while(j<=mid)tmp[++cnt]=a[j++];
    for(int i=1; i<=cnt; i++)
        a[l+i-1]=tmp[i];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    for(int i=1; i<=n; i++)
        cin >> b[i].x >> b[i].y >> b[i].z;
    sort(b+1,b+1+n,cmpx);
    int c=0;
    for(int i=1; i<=n; i++)
    {
        ++c;
        if(b[i]!=b[i+1])
            a[++pos]=b[i],a[pos].w=c,c=0;
    }
    cdq(1,pos);
    for(int i=1; i<=pos; i++)
        cnt[a[i].ans+a[i].w-1]+=a[i].w;
    for(int i=0; i<n; i++)
        cout << cnt[i] << endl;
    return 0;
}

---

LCA

P3379 【模板】最近公共祖先（LCA）

LCA 倍增

注意代码里的 $\mathtt{lg2[]}$ 表示的是 $\left\lfloor\log_2 n\right\rfloor + 1$ 。加 $1$ 千万不要忘了。

单次询问时间复杂度 $\mathcal{O}(\log n)$

// 2022年09月17日 12:01:27
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(5e5+15))

signed fa[N][20];
int n,m,rt,pos=1,head[N],lg2[N],dep[N];
struct Edge{int u,v,next;} e[N * 2];
void addEdge(int u,int v) { e[++pos]={u,v,head[u]}; head[u]=pos; }
void dfs(int u,int f)
{
    fa[u][0] = f; dep[u] = dep[f] + 1;
    for(int k=1; k<=lg2[dep[u]]; k++)
        fa[u][k] = fa[fa[u][k-1]][k-1];
    for(int i=head[u]; i; i=e[i].next)
        if(e[i].v != f) dfs(e[i].v, u);
}
int lca(int u,int v)
{
    if(dep[u] < dep[v]) swap(u,v);
    while(dep[u] > dep[v]) u = fa[u][lg2[dep[u]-dep[v]]-1];
    if(u == v) return u;
    for(int k=lg2[dep[u]]; k>=0; k--)
    {
        if(fa[u][k] != fa[v][k])
            u=fa[u][k], v=fa[v][k];
    }
    return fa[u][0];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); read(m); read(rt);
    for(int i=1,u,v; i<n; i++)
    {
        read(u); read(v);
        addEdge(u,v); addEdge(v,u);
    }

    lg2[1] = 0 + 1;
    for(int i=2; i<=n; i++) lg2[i] = lg2[i >> 1] + 1;

    dfs(rt,0);
    for(int i=1,u,v; i<=m; i++)
    {
        read(u); read(v);
        write(lca(u,v)); pc('\n');
    }
    return 0;
}

另一种写法，比较简单粗暴

// 2024年05月28日 10:45:17
void dfs(int u, int Fa)
{
    fa[u][0] = Fa; dep[u] = dep[Fa] + 1;
    for(int i = 1; i < 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int v : vec[u]) if(v != Fa) dfs(v, u);
}
int LCA(int x, int y)
{
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 19; ~i; i--)
        if(dep[x] - (1 << i) >= dep[y]) x = fa[x][i];
    if(x == y) return x;
    for(int i = 19; ~i; i--)
        if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

LCA 树链剖分

时间复杂度 $O(\log n)$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ];
char *p1=buf1,*p2=buf1;
char readchar()
{
    if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
    return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('-');}
    static T stk[66];T top=0;
    do{stk[top++]=k%10,k/=10;}while(k);
    while(top){pc(stk[--top]+'0');}
}
#define N (int)(5e5+25)
struct Edge
{
    int u,v,next;
}e[N<<1];
int pos=1,n,Q,rt,p,head[N];
int id[N],idx,fa[N],son[N];
int sz[N],top[N],dep[N];
void addEdge(int u,int v)
{
    e[pos]={u,v,head[u]};
    head[u]=pos++;
}
void dfs(int u,int f,int d)
{
    fa[u]=f;
    sz[u]=1;
    dep[u]=d;
    int mx=-1;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==f)continue;
        dfs(v,u,d+1);
        sz[u]+=sz[v];
        if(sz[v]>mx)mx=sz[v],son[u]=v;
    }
}
void dfs(int u,int ftop)
{
    id[u]=++idx;
    top[u]=ftop;
    if(!son[u])return;
    dfs(son[u],ftop);
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa[u]||v==son[u])continue;
        dfs(v,v);
    }
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
signed main()
{
    read(n);read(Q);read(rt);
    for(int i=1,u,v; i<n; i++)
    {
        read(u);read(v);
        addEdge(u,v);addEdge(v,u);
    }
    dfs(rt,0,1);dfs(rt,rt);
    while(Q--)
    {
        int u,v;read(u);read(v);
        write(lca(u,v));pc('\n');
    }
    return 0;
}

LCA Tarjan 解法

// 2023年03月16日 07:20:59
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))

vector<int> vec[N]; bitset<N> vis;
int n,m,rt,pos = 1,ans[N],head[N],f[N],pre[N],sz[N];
struct Edge { int u,v,next; } e[N * 2], q[N];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void init(int len) { for(int i = 1; i <= len; i++) f[i] = i, sz[i] = 1; }
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void merge(int x,int y)
{
    x = find(x); y = find(y);
    if(sz[x] > sz[y]) swap(x,y);
    f[x] = y; sz[y] += sz[x];
}
void Tarjan(int u)
{
    vis[u] = 1; pre[u] = u;
    for(int i = head[u]; i; i = e[i].next)
    { int v = e[i].v; if(!vis[v]) { Tarjan(v); merge(u,v); pre[find(u)] = u; } }
    for(int i : vec[u])
    {
        int v = (q[i].v == u ? q[i].u : q[i].v);
        if(vis[v]) ans[i] = pre[find(v)];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> rt; init(n);
    for(int i = 1, u,v; i < n; i++) { cin >> u >> v; addEdge(u,v); addEdge(v,u); }
    for(int i = 1, u,v; i <= m; i++) {
        cin >> u >> v; q[i] = {u,v};
        vec[u].push_back(i); vec[v].push_back(i);
    }
    Tarjan(rt); for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
    return 0;
}

---

高精度加减乘除

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define R register
string s1,s2;
int compare(string str1,string str2)
{
    if(str1.size()==str2.size())return str1.compare(str2);
    return str1.size()<str2.size()?-1:1;
}
string add(string str1,string str2)
{
    int len1=str1.size();
    int len2=str2.size();
    if(len1<len2)
    {
        for(R int i=1; i<=len2-len1; i++)
            str1='0'+str1;
    }else for(R int i=1; i<=len1-len2; i++)
            str2='0'+str2;
    string str;
    int len=str1.size();
    int jw=0;
    for(R int i=len-1; i>=0; i--)
    {
        int tmp=str1[i]-'0'+str2[i]-'0'+jw;
        jw=tmp/10;
        tmp%=10;
        str=char(tmp+'0')+str;
    }if(jw)str=char(jw+'0')+str;
    str.erase(0,str.find_first_not_of('0'));
    if(str.empty())str="0";
    return str;
}
string sub(string str1,string str2)
{
    string str;
    int len1=str1.size();
    int len2=str2.size();
    if(len1>len2)
    {
        for(R int i=1; i<=len1-len2; i++)
            str2='0'+str2;
    }
    int len=str1.size();
    int jw=0;
    for(R int i=len-1; i>=0; i--)
    {
        if(str1[i]<str2[i]+jw)
        {
            str=char(str1[i]-str2[i]-jw+10+'0')+str;
            jw=1;
        }else
        {
            str=char(str1[i]-str2[i]-jw+'0')+str;
            jw=0;
        }
    }
    str.erase(0,str.find_first_not_of('0'));
    if(str.empty())str="0";
    return str;
}
string mul(string str1,string str2)
{
    int len1=str1.size();
    int len2=str2.size();
    if(str1=="0"||str2=="0")return "0";
    string tmpstr;
    string str;
    for(R int i=len1-1; i>=0; i--)
    {
        tmpstr="";
        int idx=str1[i]-'0';
        int jw=0;
        if(idx)
        {
            for(R int j=1; j<=len1-1-i; j++)
                tmpstr+='0';
            for(R int j=len2-1; j>=0; j--)
            {
                int tmp=idx*(str2[j]-'0')+jw;
                jw=tmp/10;
                tmp%=10;
                tmpstr=char(tmp+'0')+tmpstr;
            }if(jw)tmpstr=char(jw+'0')+tmpstr;
        }
        str=add(str,tmpstr);
    }
    str.erase(0,str.find_first_not_of('0'));
    if(str.empty())str="0";
    return str;
}
string div(string str1,string str2)
{
    string ans;
    ans="";
    if(str1=="0")return ans="0";
    int check=compare(str1,str2);
    if(check==-1)return ans="0";
    if(check==0)return ans="1";
    int len1=str1.size();
    int len2=str2.size();
    string tmpstr;
    tmpstr.append(str1,0,len2-1);
    for(R int i=len2-1; i<len1; i++)
    {
        tmpstr+=str1[i];
        tmpstr.erase(0,tmpstr.find_first_not_of('0'));
        if(tmpstr.empty())tmpstr="0";
        for(string str="9";str[0]>='0';str[0]--)
        {
            string tmp=mul(str,str2);
            if(compare(tmp,tmpstr)<=0)
            {
                ans+=str[0];
                tmpstr=sub(tmpstr,tmp);
                break;
            }
        }
    }
    ans.erase(0,ans.find_first_not_of('0'));
    return ans;
}
signed main()
{
    // ...
    return 0;
}

---

高精度封装版

网上搜的。有空搞吧。忘记出处了，很久前复制的

#include <bits/stdc++.h>
using namespace std;
const int maxn=5009;
struct bignum{
    int num[maxn],len;
    bignum(){memset(num,0,sizeof(num));}
};
bool comp(bignum a,bignum b)//比较函数
{
    if(a.len!=b.len)    return (a.len>b.len)?1:0;
    for(int i=a.len-1;i>=0;i--)
    if(a.num[i]!=b.num[i])    return (a.num[i]>b.num[i])?1:0;
    return -1;//相等
}
bignum operator / (bignum a,int b)//高精除以低精度
{
    bignum c=a;
    int tw=0,len=a.len;
    for(int i=len-1;i>=0;i--)
    {
        int k=(tw*10+c.num[i])/b;
        tw=(tw*10+c.num[i])%b;
        c.num[i]=k;
    }
    while(c.num[len-1]==0)    len--;
    c.len=len;
    return c;
}
bignum init(bignum &a,string s)
{
    int len=s.length();
    if(s[0]=='-')//处理负数
        len--,a.num[maxn-1]=-1;//这样len-i-1就不会到0去,且留下是负数的标记
    for(int i=0;i<len;i++)
        a.num[i]=s[len-i-1]-'0';
    a.len=len;
    return a;
}
bignum Add(bignum &a,bignum &b)
{
    bignum c;
    int len=max(a.len,b.len);
    for(int i=0;i<len;i++)
    {
        c.num[i]+=(a.num[i]+b.num[i]);
        c.num[i+1]+=c.num[i]/10;
        c.num[i]%=10;
    }
    if(c.num[len])    len++;//加法最多进1位
    c.len=len;
    return c;
}
bignum dmull(bignum &a,int s)//高精乘低精
{
    for(int i=0;i<a.len;i++)    a.num[i]*=s;
    for(int i=0;i<a.len;i++)
    {
        if(a.num[i]>=10)
        {
            if(i==a.len-1)    a.len++;
            a.num[i+1]+=a.num[i]/10;
            a.num[i]%=10;
        }
    }
    return a;
}
bignum Hmull(bignum &a,bignum &b)//高精乘高精
{
    bignum c;
    for(int i=0;i<a.len;i++)
    for(int j=0;j<b.len;j++)
    {
        c.num[i+j]+=(a.num[i]*b.num[j]);
        c.num[i+j+1]+=c.num[i+j]/10;
        c.num[i+j]%=10;
    }
    int len=a.len+b.len;
    while(c.num[len-1]==0&&len>1)    len--;
    c.len=len;
    return c;
}
bignum ddiv(bignum a,bignum b,bignum &c,int &f)//低精度除法
{
    //c是除的结果，f是余数
    for(int i-a.len-1;i>=0;i--)
    {
        f=f*10+a.num[i];//慢慢做求余
        c.num[i]=f/b;
        f%=b;
    }
    while(len>1&&c.num[len-1]==0)    len--;
    c.len=len;
}
void print(bignum &a)
{
    for(int i=a.len-1;i>=0;i--)    cout<<a.num[i];
}
int main()
{
    int n;
    cin>>n;
    bignum temp,ans;
    //下面是求解S=1!+2!+3!....+n!
    init(ans,"1");init(temp,"1");
    for(int i=2;i<=n;i++)
    {
        temp=dmull(temp,i);
        ans=Add(ans,temp);
    }
    print(ans);
}

---

莫队

例题：P4462 [CQOI2018] 异或序列 题解：link

时间复杂度 $\mathcal{O}(n\sqrt{n})$ （认为 $n,m$ 同阶）

代码：

// 2023年08月03日 16:10:05
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n,m,k,B,res,a[N],ans[N],o[N * 2]; // o[i]表示当前区间有多少个数异或和为i
struct node { int l,r,id,bl; } q[N];
bool cmp(node x, node y) {
    return x.bl == y.bl ? x.r < y.r : x.bl < y.bl;
}
void add(int x) { res += o[x ^ k]; ++o[x]; }
void del(int x) { --o[x]; res -= o[x ^ k]; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> k; B = sqrt(n);
    for(int i = 1; i <= n; i++) { cin >> a[i]; a[i] ^= a[i - 1]; }
    for(int i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i; --q[i].l; q[i].bl = (q[i].l - 1) / B + 1;
    }
    sort(q + 1, q + 1 + m, cmp); int l = 1, r = 0;
    for(int i = 1; i <= m; i++)
    {
        while(l < q[i].l) del(a[l++]);
        while(l > q[i].l) add(a[--l]);
        while(r < q[i].r) add(a[++r]);
        while(r > q[i].r) del(a[r--]);
        ans[q[i].id] = res;
    }
    for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
    return 0;
}