算法竞赛进阶指南

2026-01-09

Word count: 3.9k | Reading time≈ 20 min

0x00 基本算法

¶0x01 位运算

¶a^b

快速幂板子 $O(log(b))$


i64 fastpow(i64 a,int b,int p) {
    i64 res=1%p;
    while(b){
        if(b&1){
            res=res*a%p;
        }
        a=a*a%p;
        b>>=1;
    }
    return res;
}

void solve(){
    int a,b,p;
    cin>>a>>b>>p;

    cout<<a<<"^"<<b<<" "<<"mod "<<p<<"="<<fastpow(a,b,p)<<"\n";
    
    return;
}

¶64位整数乘法

龟速乘板子 $O(log(b))$

i64 slowmul(i64 a,i64 b,i64 p){
    i64 res=0;
    while(b){
        if(b&1){
            res=(res+a)%p;
        }
        a=a*2%p;
        b>>=1;
    }
    return res;
}

void solve(){
    i64 a,b,p;
    cin>>a>>b>>p;
    cout<<slowmul(a,b,p)<<"\n";
    return;
}

自然溢出

$O(1)$

i64 overflowmul(u64 a,u64 b,u64 p){
    a%=p,b%=p;
    u64 c=(long double)a*b/p;
    u64 x=a*b,y=c*p;
    i64 ans=((i64)(x%p)-(i64)(y%p)+p)%p;
    return ans;
}

void solve(){
    i64 a,b,p;
    cin>>a>>b>>p;
    cout<<overflowmul(a,b,p)<<"\n";
    return;
}

¶[NOI2014] 起床困难综合症

从高到低拆位计算，如果当前位置取1当且仅当加上后不超过m，且比取0经过n次运算后攻击力更高。 $O(nlog(m))$

void solve(){
    int n,m;
    cin>>n>>m;

    vector<int> op,t;
    for(int i=0;i<n;i++){
        string s;
        int x;
        cin>>s>>x;
        if(s=="AND"){
            op.push_back(0);
        }else if(s=="OR"){
            op.push_back(1);
        }else{
            op.push_back(2);
        }
        t.push_back(x);
    }

    auto calc=[&](int i,int j)->int{
        int res=j<<i;
        for(int k=0;k<n;k++){
            int x=t[k]&(1<<i);
            if(op[k]==0){
                res&=x;
            }else if(op[k]==1){
                res|=x;
            }else{
                res^=x;
            }
        }
        return res;
    };

    int x=0;
    for(int i=30;i>=0;i--){
        if((i64)x+(1<<i)>m){
            continue;
        }
        int calc_0=calc(i,0),calc_1=calc(i,1);
        if(calc_1>calc_0){
            x+=1<<i;
        }
    }

    for(int i=0;i<n;i++){
        if(op[i]==0){
            x&=t[i];
        }else if(op[i]==1){
            x|=t[i];
        }else{
            x^=t[i];
        }
    }

    cout<<x<<"\n";


}

¶trick:

$\forall k \in [0,35],2^k\%37$ 互不相等，且恰好取遍整数1-36
借此技巧将 $2^k$ 哈希

int H[37];
for(int i=0;i<36;i++){
	H[(1ll<<i)%37]=i;
}

cpp内置函数

int __builtin__ctz(unsigned x)
int __builtin__ctzll(unsigned long long x)
// 返回x的二进制表示下最低位的1后边有多少个0

int __builtin__popcount(unsigned int x)
int __builtin__popcountll(unsigned long long x)
// 返回x的二进制表示下有多少位为1

¶0x02 递推与递归

¶枚举子集（递归实现指数型枚举）

$O(2^n)$

void solve(){
    int n;
    cin>>n;
    string s="";
    for(int i=0;i<n;i++){
        s+='N';
    }
    auto dfs=[&](auto dfs,int i)->void{
        if(i==n){
            cout<<s<<"\n";
            return;
        }
        s[i]='N';
        dfs(dfs,i+1);
        s[i]='Y';
        dfs(dfs,i+1);
        return;
    };
    dfs(dfs,0);
}

¶组合型枚举

$O(C_n^k)$

void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> ans;
    auto dfs=[&](auto dfs,int i)->void{
        if(ans.size()==k){
            for(int i=0;i<k;i++){
                cout<<ans[i]<<" \n"[i==k-1];
            }
            return;
        }
        if(i>n||ans.size()+n-i+1<k){
            return;
        }
        ans.push_back(i);
        dfs(dfs,i+1);
        ans.pop_back();
        dfs(dfs,i+1);
    };
    dfs(dfs,1);
}

¶枚举排列（递归实现排列型枚举）

$O(n^k)$

void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> ans;
    vector<bool> chosen(n+1);
    auto dfs=[&](auto dfs,int i)->void{
        if(i==k+1){
            for(int j=0;j<k;j++){
                cout<<ans[j]<<" \n"[j==k-1];
            }
            return;
        }
        for(int j=1;j<=n;j++){
            if(chosen[j])
                continue;
            chosen[j]=true;
            ans.push_back(j);
            dfs(dfs,i+1);
            ans.pop_back();
            chosen[j]=false;
        }
    };
    dfs(dfs,1);
}

4塔汉诺塔问题，可由3塔问题转化。
3塔：设 $d_n$ 为将 n 个盘子从 A 转移到 C 的最小步数， $d_n=2d_{n-1}+1$ 。
4塔：设 $f_n$ 为将 n 个盘子从 A 转移到 D 的最小步数，可以先把 i 个盘子在4塔模式下从 A 转移到 B，再将 n-i 个盘子在3塔模式下从A 转移到 D ，再将 i 个盘子在3塔模式下从B 转移到 D ， $f_n=\min\limits_{1\le i< n}\left\{2f_{i}+d_{n-i}\right\}$ 。

$O(n^2)$

¶约数之和

将A质因数分解， $A=\prod\limits_i{p_i^{c_i}}$

$A^B=\prod\limits_i{p_i^{c_iB}}$

约数之和= $\prod\limits_i\sum\limits_j^{c_iB}{p_i^j}$

设 $C=c_iB$

$C\%2==0，\sum\limits_j^{C}{p^j} = (1+\sum\limits_j^{C/2}{p^j})\sum\limits_j^{C/2-1}{p^j}+p^C$

$C\%2==1, \sum\limits_j^{C}{p^j} = (1+\sum\limits_j^{(C+1)/2}{p^j})\sum\limits_j^{(C-1)/2}{p^j}$

i64 fastpow(i64 a,int b,int p) {
    i64 res=1%p;
    while(b){
        if(b&1){
            res=res*a%p;
        }
        a=a*a%p;
        b>>=1;
    }
    return res;
}

void solve(){
    int a,b;
    cin>>a>>b;

    if(a==0){
        cout<<0<<"\n";
        return;
    }

    map<int,int> cnt;
    for(int i=2;i<=a/i;i++){
        if(a%i==0){
            while(a%i==0){
                cnt[i]++;
                a/=i;
            }
        }
    }
    if(a>1){
        cnt[a]++;
    }

    i64 ans=1;
    int mod=9901;
    auto sum=[&](auto sum,int p,i64 c)->i64{
        if(c==0){
            return 1;
        }
        if(c%2==0){
            return (sum(sum,p,c/2-1)*(1+fastpow(p,c/2,mod))%mod+fastpow(p,c,mod))%mod;
        }else{
            return sum(sum,p,(c-1)/2)*(1+fastpow(p,(c+1)/2,mod))%mod;
        }
    };
    for(auto [p,c]:cnt){
        ans=ans*sum(sum,p,c*b)%mod;
    }

    cout<<ans<<"\n";
}

¶分形之城

解法1（标准解法）：在N级城市中查询编号为A的街区的位置，先在N-1级城市找到编号A%block街区的位置，再考虑通过坐标旋转和翻转以及平移得到在当前城市的位置。
在不同形状的城市中的坐标旋转需要用到旋转矩阵。

def pos(N,c):
    if N==0:
        return 0,0
    block=4**(N-1)
    length=1<<(N-1)
    idx=c//block
    c%=block
    x,y=pos(N-1,c)
    if idx==0:
        return y,x
    elif idx==1:
        return x,y+length
    elif idx==2:
        return x+length,y+length
    else:
        return length*2-y-1,-x+length-1

def solve():
    n,a,b=MIIS()
    a-=1
    b-=1
    xa,ya=pos(n,a)
    xb,yb=pos(n,b)
    dx=xa-xb
    dx*=10
    dy=ya-yb
    dy*=10
    print(int(sqrt(dx*dx+dy*dy)+0.5))
    return

test=1
test=int(input())
for _ in range(test):
    solve()

解法2：大分讨，在N级形状为c的城市中查找编号为A的街区的位置，先在N-1级城市形状为d的城市中查询编号为A%block的街区的位置，再通过平移得到当前位置。

def get(N,c,x):
    if N==0:
        return 0,0
    s=4**(N-1)
    y=(x-1)//s
    x-=y*s
    d=2**(N-1)
    if c==0:
        if y==0:
            a,b=get(N-1,1,x)
            return a,b
        elif y==1:
            a,b=get(N-1,0,x)
            return a,b+d
        elif y==2:
            a,b=get(N-1,0,x)
            return a+d,b+d
        else:
            a,b=get(N-1,2,x)
            return a+d,b
    elif c==1:
        if y==0:
            a,b=get(N-1,0,x)
            return a,b
        elif y==1:
            a,b=get(N-1,1,x)
            return a+d,b
        elif y==2:
            a,b=get(N-1,1,x)
            return a+d,b+d
        else:
            a,b=get(N-1,3,x)
            return a,b+d
    elif c==2:
        if y==0:
            a,b=get(N-1,3,x)
            return a+d,b+d
        elif y==1:
            a,b=get(N-1,2,x)
            return a,b+d
        elif y==2:
            a,b=get(N-1,2,x)
            return a,b
        else:
            a,b=get(N-1,0,x)
            return a+d,b
    else:
        if y==0:
            a,b=get(N-1,2,x)
            return a+d,b+d
        elif y==1:
            a,b=get(N-1,3,x)
            return a+d,b
        elif y==2:
            a,b=get(N-1,3,x)
            return a,b
        else:
            a,b=get(N-1,1,x)
            return a,b+d


def solve():
    n,a,b=MIIS()
    xa,ya=get(n,0,a)
    xb,yb=get(n,0,b)
    print(int(sqrt((abs(xa-xb)*10)**2+(abs(ya-yb)*10)**2)+0.5))
    return

test=1
test=int(input())
for _ in range(test):
    solve()

¶0x03 前缀和与差分

¶激光炸弹

二位差分，注意R最大取5001

¶增减序列

转化成差分序列，原数组全都相等等价于差分数组除第一位外全为0。

可执行的操作：

选择两个端点，左加右减
选择两个端点，左减右加
选择单点加
选择单点减

最少操作次数=max(加的次数，减的次数)

序列个数=|加的次数-减的次数|+1，即除第一位外，最后那个不为0的数在执行操作的过程中也对第一个数操作，当然也可以不操作

¶最高的牛

l,r可以看见，则将l+1到r-1都减1

¶0x04 二分

¶最佳牛围栏

二分平均值 $x$ ，需要存在一个长度大于 $f$ 的区间 $[l,r]$ ，满足 $\frac{s_r-s_{l-1}}{r-(l-1)}\ge x$ ，即 $s_r-xr\ge s_{l-1}-x(l-1)$ 。
设 $c_i=s_i-xi$ ，不断维护位置 $i-f$ 及其之前的最小值 $c$ ，小于当前值 $c_i$ 即成立。

坑点： $l\lt true\_val \lt r$ ，需要 $r$ * 1000下取整，而不是 $l$ 。

¶特殊排序

快排、归并、二分插入都不需要传递性，但比较次数上快排有1.386的常数因子，询问次数过多。

如果行 $1$ 和行 $n$ 无法交换，转换为均分纸牌问题。

$r_i$ 表示第 $i$ 的感兴趣的摊点数。

考虑前 $i$ 行需要和后面的行交换多少次才能达到最终结果，即 $|s_i-t/n*i|$ 。

其中 $s_i$ 为 $r_i$ 前缀和，所有前缀的该绝对值求和即为答案。

考虑 $1$ 和 $n$ 可交换的情况，但最优解必定存在两个相邻的不交换，枚举这个断点求最小值即为答案。

设 $rm_i=r_i-t/n$ ， $s_i$ 为 $rm_i$ 前缀和。

假设断点为 $k$ ，即最优解为 $|s_{k+1}-s_k|,|s_{k+2}-s_k|……|s_n-s_k|,|s_1+s_n-s_k|……|s_k+s_n-s_k|$

关键: $s_n=0$

答案转化为 $\sum\limits_{i=1}^{n}|s_i-s_k|$ ，转化为货舱选址问题，选择最优位置 $k$ ，使其他 $s$ 到 $s_k$ 距离之和最小。

def solve():
    n,m,t=MIIS()
    row=[0]*n
    col=[0]*m
    for i in range(t):
        x,y=MIIS()
        x-=1
        y-=1
        row[x]+=1
        col[y]+=1
    ans=0
    p=0
    out=['impossible','row','column','both']
    if t%n==0:
        p+=1
        for i in range(n):
            row[i]-=t//n
            if i:
                row[i]+=row[i-1]
        row.sort()
        for i in range(n):
            ans+=abs(row[i]-row[n//2])
    if t%m==0:
        p+=2
        for i in range(m):
            col[i]-=t//m
            if i:
                col[i]+=col[i-1]
        col.sort()
        for i in range(m):
            ans+=abs(col[i]-col[m//2])
    print(out[p],end=' \n'[p==0])
    if p:
        print(ans)
    return

¶动态中位数

对顶堆板子。

大根堆维护前一半，小根堆维护后一半。

小根堆堆顶不存在或者小于小根堆的堆顶就放进大根堆，否则放入小根堆。

时刻维护两个堆的大小。（只可在查询之前维护）

def solve():
    ID,m=MIIS()
    a=[]
    while len(a)<m:
        a.extend(LIIS())
    ans=[]
    up=[]
    down=[]
    for i in range(m):
        if not down or a[i]<down[0]:
            heappush(up,-a[i])
        else:
            heappush(down,a[i])
        if i%2==0:
            while len(up)>(i+2)//2:
                heappush(down,-heappop(up))
            while len(down)>i+1-(i+2)//2:
                heappush(up,-heappop(down))
            ans.append(-up[0])
    print(ID,len(ans))
    c=0
    for x in ans:
        c+=1
        print(x,end=' \n'[c%10==0])
    if c%10:
        print()
    return

test=1
test=int(input())
for _ in range(test):
    solve()

¶超快速排序

最优做法就是冒泡排序，交换次数为逆序对数。

可归并排序过程种求逆序数，也可以树状数组动态计数。

def solve():
    while True:
        n=II()
        if n==0:
            break
        a=[]
        for i in range(n):
            a.append(II())
        tmp=[0]*n
        def calc(l,r):
            if l>=r:
                return 0
            mid=l+r>>1
            res=calc(l,mid)+calc(mid+1,r)
            i,j=l,mid+1
            k=l
            while i<=mid and j<=r:
                if a[i]<=a[j]:
                    tmp[k]=a[i]
                    i+=1
                    k+=1
                else:
                    res+=mid-i+1
                    tmp[k]=a[j]
                    j+=1
                    k+=1
            while i<=mid:
                tmp[k]=a[i]
                i+=1
                k+=1
            while j<=r:
                tmp[k]=a[j]
                j+=1
                k+=1
            for i in range(l,r+1):
                a[i]=tmp[i]
            return res
        print(calc(0,n-1))

    return

¶奇数码问题

两个状态能否到达等价于把除0以外的数排成一列后的逆序数奇偶性是否相等。

$n\times m$ 数码的有解性判定：若列数为奇数，逆序数奇偶性相等即可；列数为偶数时，逆序数+0的行数差的奇偶性相等有解。

¶0x06[倍增]

给定一个非负整数数列，每次在线询问前缀最大值小于等于查询值 $T$ 。

两种倍增写法

写法一

def solve():
    n,q=MIIS()
    a=LIIS()
    s=list(accumulate(a,initial=0))
    for i in range(q):
        k=II()
        c=0;l=0
        for j in range(31,-1,-1):
            r=l+(1<<j)
            if r<=n and c+s[r]-s[l]<=k:
                c+=s[r]-s[l]
                l=r
        print(c)
    return

写法二

def solve():
    n,q=MIIS()
    a=LIIS()
    s=list(accumulate(a,initial=0))
    for i in range(q):
        k=II()
        c=0;l=0
        j=1
        while j:
            r=l+j
            if r<=n and c+s[r]-s[l]<=k:
                c+=s[r]-s[l]
                l=r
                j*=2
            else:
                j//=2
        print(c)
    return

写法二中的长度 $j$ 一旦开始减少就不会再增加。

¶天才ACM

每次在当前位置，倍增长度， $check$ 倍增后的区间是否合法（排序后最大最小 $m$ 对数差的平方和 $\le$ $t$ ）。 $O(N(logN)^2)$

def solve():
    n,m,t=MIIS()
    a=LIIS()
    def check(l,r):
        p=list(sorted(a[l:r+1]))
        res=0
        for i in range(min(m,len(p)//2)):
            res+=(p[len(p)-1-i]-p[i])**2
        return res<=t
    cnt=0
    i=0
    while i<n:
        length=0
        j=1
        while j:
            r=i+length+j-1
            if r<n and check(i,r):
                length+=j
                j*=2
            else:
                j//=2
        i+=length
        cnt+=1
    print(cnt)
    return

test=1
test=int(input())
for _ in range(test):
    solve()

新增的长度可以和原来的区间归并排序。 $O(NlogN)$

def solve():
    n,m,t=MIIS()
    a=LIIS()
    cnt=0
    i=0
    while i<n:
        length=0
        j=1
        L=[]
        while j:
            r=i+length+j-1
            if r>=n:
                j//=2
                continue
            R=sorted(a[i+length:r+1])
            M=sorted(L+R)
            res=0
            for k in range(min(m,len(M)//2)):
                res+=(M[len(M)-1-k]-M[k])**2
            if res<=t:
                length+=j
                L=M
                j*=2
            else:
                j//=2
        i+=length
        cnt+=1
    print(cnt)
    return

test=1
test=int(input())
for _ in range(test):
    solve()

tips: $python$ 的 $Timsort$ 会检测有序数组并归并排序，比手写快。

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.