全文采用一个模板，代码展示仅显示核心内容与核心函数。

部分代码需要去除 #define int long long，请自行辨别。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define MT int TTT=R;while(TTT--)
#define pc putchar
#define R read()
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i>=b;i--)
#define m1(a,b) memset(a,b,sizeof a)
namespace IO
{
    inline int read()
    {
        int x=0;
        char ch=getchar();
        bool f=0;
        while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        if(f) x=-x;
        return x;    
    }
    template<typename T> inline void write(T x)
    {
        if(x<0)
        {
            pc('-');
            x=-x;
        }
        if(x>9) write(x/10);
        pc(x%10+'0');
    }
};
namespace math
{
    inline int gcd(int a,int b)
    {
        return b?gcd(b,a%b):a;
    }
    inline int qmi(int a,int b,int p)
    {
        int res=1;
        while(b)
        {
            if(b&1) res=res*a%p;
            a=a*a%p;
            b>>=1;
        }
        return res;
    }
    inline int inv(int a,int p)
    {
        return qmi(a,p-2,p);
    }
    const int MAXN=2e6+10;
    int my_fac[MAXN],my_inv[MAXN];
    void init_binom(int mod)
    {
        my_fac[0]=1;fo(i,1,min(MAXN,mod)-1) my_fac[i]=my_fac[i-1]*i%mod;
        my_inv[min(MAXN,mod)-1]=qmi(my_fac[min(MAXN,mod)-1],mod-2,mod);rep(i,min(MAXN,mod)-2,0) my_inv[i]=my_inv[i+1]*(i+1)%mod;
    }
    int binom(int a,int b,int mod)
    {
        return my_fac[a]*my_inv[b]%mod*my_inv[a-b]%mod;
    }
}
using namespace IO;
using namespace math;


signed main(){

}

0x00 基础算法

位运算

a^b

快速幂板子题，利用 $a^ba^c=a^{b+c}$ 的性质，将指数二进制拆分后进行计算。

int a,b,p;
signed main(){
    a=R,b=R,p=R;
    write(qmi(a,b,p)%p); 
}

64 位整数乘法

龟速乘板子题，利用乘法分配律，将第二个乘数二进制分解后进行计算。

int mul(int a,int b,int p)
{
    int res=0;
    while(b)
    {
        if(b&1) (res+=a)%=p;
        (a+=a)%=p;
        b>>=1;
    }
    return res%p;
}

最短 Hamilton 路径

考虑一个状压 dp，$f_{state,pos}$ 表示当前经过过的点的二进制表示为 $state$，当前在点 $pos$ 的最小代价。

转移不难。

signed main(){
    m1(f,0x3f),f[1][0]=0;
    n=R;fo(i,0,n-1) fo(j,0,n-1) a[i][j]=R;
    fo(i,1,(1<<n)-1) fo(j,0,n-1) if(i>>j&1) fo(k,0,n-1) if((i^(1<<j))>>k&1) f[i][j]=min(f[i][j],f[i^(1<<j)][k]+a[j][k]);
    write(f[(1<<n)-1][n-1]);
}

起床困难综合症

每一个位都是独立的，于是你考虑枚举每一位是 1 好还是是 0 好，记得考虑不能超过 $m$ 的上限，这里我们采用用一位减一位的方式，这样不需要额外变量去判断是否贴着上限。

bool calc(int pos,bool x)
{
    fo(i,1,n)
    {
        bool now=(a[i]>>pos&1);
        if(opt[i]==1) x|=now;
        else if(opt[i]==2) x&=now;
        else x^=now;
    }
    return x;
}
signed main(){
    rep(i,30,0)
        if(m>>i)
        {
            bool x=calc(i,0),y=calc(i,1);
            if(x>=y) ans|=(x<<i);
            else ans|=(y<<i),m-=1<<i;
        }
        else ans|=calc(i,0)<<i;
}

递推与递归

递归实现指数型枚举

没话好说。

void dfs(int x)
{
    if(x>n)
    {
        for(auto i:v) write(i),pc(' ');
        puts("");
        return;
    }
    dfs(x+1),v.pb(x),dfs(x+1),v.pop_back();
}

递归实现组合型枚举

没话好说。

void dfs(int x)
{
    if(v.size()>k) return;
    if(x>n)
    {
        if(v.size()==k)
        {
            for(auto i:v) write(i),pc(' ');
            puts("");
        }
        return;
    }
    v.pb(x),dfs(x+1),v.pop_back(),dfs(x+1);
}

递归实现排列型枚举

没话好说。

void dfs(int x)
{
    if(x>n)
    {
        for(auto i:v) write(i),pc(' ');
        puts("");
        return;
    }
    fo(i,1,n) if(!vis[i])
    {
        vis[i]=1;
        v.pb(i);
        dfs(x+1);
        v.pop_back();
        vis[i]=0;
    }
}

费解的开关

枚举第一个翻转的状态，剩下的贪心翻转。

const int N=6;
const int dx[]={0,0,0,1,-1},dy[]={0,1,-1,0,0};
char g[N][N],backup[N][N];
void turn(int x,int y)
{
    fo(i,0,4)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=0&&xx<=4&&yy>=0&&yy<=4) g[xx][yy]^=1;
    }
}
void solve()
{
    fo(i,0,4) scanf("%s",g[i]);
    int res=10;
    fo(st,0,31)
    {
        memcpy(backup,g,sizeof g);
        int step=0;
        fo(i,0,4) if(st>>i&1) step++,turn(0,i);
        fo(i,0,3) fo(j,0,4) if(g[i][j]=='0') step++,turn(i+1,j);
        bool flag=0;
        fo(i,0,4) if(g[4][i]=='0'){flag=1;break;}
        if(!flag) res=min(res,step);
        memcpy(g,backup,sizeof g);
    }
    write(res>6?-1:res),puts("");
}

奇怪的汉诺塔

我们考虑 3 个塔的做法，$n$ 个铁片的最小步数为 $2^n-1$，设其为 $f_n$。

接着考虑 4 个塔怎么做？假设有 $n$ 个铁片，我们先把 $i$ 个铁片在 4 塔模式下移动到第二个塔，然后再把 $n-i$ 个铁片在 3 塔模式下移动到第四个塔，在把 $i$ 个铁片在 4 塔模式下移动到第四个塔。

有转移式：
$$g_n=\min_{i=1}^{n-1}\{2g_i+f_{n-i}\}$$

const int N=20;
int n;
int f[N],g[N];
void main(){
    n=12;
    fo(i,1,n) f[i]=f[i-1]*2+1;
    m1(g,0x3f);
    g[1]=1;
    fo(i,2,n) fo(j,1,i-1) g[i]=min(g[i],2*g[j]+f[i-j]);
    fo(i,1,n) write(g[i]),puts("");
}

约数之和

不难通过分解质因数转化为求：
$$\sum_{i=0}^{n}p^i$$
考虑进行分治，设答案为 $f(n,p)$，则：
$$f(n,p)= \begin{cases} p \times f(n-1,p)+1 & n \equiv 0 \pmod 2 \\ f(\lfloor \frac n2 \rfloor,p) \times f(1+p^{\lfloor \frac n2 \rfloor+1}) & n \equiv 1 \pmod 2 \end{cases}$$

int sum(int p, int k)
{
    if(k==0) return 1;
    if(k%2==0) return (p%mod*sum(p,k-1)%mod+1)%mod;
    return sum(p,k/2)%mod*(1+qmi(p, k/2+1))%mod;
}

分解质因数部分不给出代码。

分形之城

扔个题解链接吧，这个讲的非常清楚。

AcWing 98. 分形之城 - AcWing

前缀和与差分

激光炸弹

考虑建立二维前缀和数组，计算每个不同正方形内的权值和。

const int N=5010;
int cnt,r;
int s[N][N];
void main(){
    cnt=R,r=min(R,5001);
    while(cnt--)
    {
        int x=R+1,y=R+1,w=R;
        s[x][y]+=w;
    }
    fo(i,1,5001) fo(j,1,5001) s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    int ans=0;
    fo(i,r,5001) fo(j,r,5001) ans=max(ans,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);
    write(ans),puts("");
}

增减序列

发现操作等价于在差分数组上倒腾。

数列一模一样相当于除了 $a_1$ 之外，其他的所有数都为 0。

设 $b_i=a_i-a_{i-1}$，则答案为：

$$\max(\sum_{i=2}^{n}[b_i>0]b_i,\sum_{i=2}^{n}[b_i \leq 0]b_i)$$

$$|\sum_{i=2}^{n}[b_i>0]b_i-\sum_{i=2}^{n}[b_i \leq 0]b_i|+1$$

为什么呢？第一个答案是显然的，因为我们需要消去所有的正数和负数，显然有这个下限，并也可以取到这个下限。

第二个较为困难，考虑对于仅消掉一个值的操作，可以从头也可以从尾开始，在这里会体现出不同，因此是这个答案。

const int N=1e5+10;
int n;
int a[N],b[N];
void main(){
    n=R;
    fo(i,1,n) a[i]=R;
    fo(i,1,n) b[i]=a[i]-a[i-1];
    int t1=0,t2=0;
    fo(i,2,n)
        if(b[i]>0) t1+=b[i];
        else t2-=b[i];
    write(max(t1,t2)),puts(""),write(abs(t1-t2)+1);
}

最高的牛

最佳构造是，初始每个牛身高都是 $h$，然后每输入一个区间，不妨设 $a \leq b$，则令从 $a+1$ 到 $b-1$ 的牛身高都减一。

发现可以离线，因此用差分做即可。

const int N=5010;
int n,p,h,m;
map<pair<int,int>,bool> vis;
int s[N];
void main(){
    n=R,p=R,h=R,m=R;
    fo(i,1,m)
    {
        int a=R,b=R;
        if(a>b) swap(a,b);
        if(vis[{a,b}]) continue;
        s[a+1]--,s[b]++;
        vis[{a,b}]=1;
    }
    fo(i,1,n) s[i]+=s[i-1];
    fo(i,1,n) write(s[i]+h),puts("");
}

最佳牛围栏

考虑二分，将所有的数减去 $mid$，判定是否存在一个子序列和大于 $0$。

const int N=1e5+10;
int n,f;
double a[N],s[N];
void main(){
    n=R,f=R;
    fo(i,1,n) cin>>a[i];
    double l=-1e6,r=1e6;
    while(r-l>1e-5)
    {
        double mid=(l+r)/2;
        fo(i,1,n) s[i]=s[i-1]+a[i]-mid;
        double ans=-1e10,minx=1e10;
        fo(i,f,n) minx=min(minx,s[i-f]),ans=max(ans,s[i]-minx);
        if(ans>0) l=mid;
        else r=mid;
    }
    write((int)(r*1000));
}

特殊排序

考虑 stable_sort。

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> v;
        for(int i=1;i<=N;i++) v.push_back(i);
        stable_sort(v.begin(),v.end(),compare);
        return v;
    }
};

电影

离散化语言后，就可以直接用数组统计。

const int N=2e5+10;
int n,m;
int a[N],b[N];
unordered_map<int,int> ma;
void main(){
    n=R;
    fo(i,1,n) ma[R]++;
    m=R;
    int max1=-2e9,max2=2e9,id=0;
    fo(i,1,m) a[i]=R;
    fo(i,1,m) b[i]=R;
    fo(i,1,m) if(ma[a[i]]>max1||(ma[a[i]]==max1&&ma[b[i]]>=max2)) id=i,max1=ma[a[i]],max2=ma[b[i]];
    write(id);
}

货仓选址

根据排序不等式，货仓建在中位数上是最好的。

const int N=1e5+10;
int n;
int a[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int ans=a[n+1>>1],res=0;
    for(int i=1;i<=n;i++) res+=abs(a[i]-ans);
    cout<<res;
}

七夕祭

问题等价于行与列上的环形均分纸牌问题。

由于只能在行与列上进行交换，所以行与列是独立的，可以分开计算。

考虑普通的均分纸牌问题，答案可表述为：

$$\sum_{i=1}^{n}|i \times \frac{\sum_{j=1}^{n}a_j}n-\sum_{j=1}^{i}a_j|$$

那么环上的怎么做呢？

我们考虑破环为链。设在 $k$ 位置断开。

我们令 $A_i=a_i-\frac{\sum_{j=1}^{n}a_j}n$，$S_i=\sum_{i=1}^{n}A_i$，那么答案为：

$$\sum_{i=1}^{n}|S_i-S_k|$$

根据排序不等式，$k$ 取到中位数时这个式子值最小。

复杂度 $O(n \log n+m \log m)$。

精细实现可以做到 $O(n+m)$。

const int N=1e5+10;
int n,m,k;
int a[N],b[N],s[N];
int get(int* a,int n)
{
    int avg=0;
    fo(i,1,n) avg+=a[i];
    avg/=n;
    fo(i,2,n) s[i]=s[i-1]+a[i]-avg;
    sort(s+1,s+n+1);
    int ans=0;
    fo(i,1,n) ans+=abs(s[i]-s[n/2+1]);
    return ans;
}
void main(){
    n=R,m=R,k=R;
    fo(i,1,k) a[R]++,b[R]++;
    if(k%n&&k%m) puts("impossible");
    else if(k%n) printf("column %lld",get(b,m));
    else if(k%m) printf("row %lld",get(a,n));
    else printf("both %lld",get(a,n)+get(b,m));
}

动态中位数

对顶堆。

每插入一个数，最多两次 push，一次 pop。

所以复杂度是对的。

const int N=1e5+10;
int id,n;
int a[N];
priority_queue<int> down;
priority_queue<int,vector<int>,greater<int> > up;
void solve()
{
    id=R,n=R;
    write(id),pc(' '),write((n+1)/2),puts("");
    while(down.size()) down.pop();
    while(up.size()) up.pop();
    int cnt=0;
    fo(i,1,n)
    {
        int x=R;
        if(down.empty()||x<=down.top()) down.push(x);
        else up.push(x);
        while(down.size()>up.size()+1) up.push(down.top()),down.pop();
        while(up.size()>down.size()) down.push(up.top()),up.pop();
        if(i&1) write(down.top()),pc(" \n"[++cnt%10==0]);
    }
    if(cnt%10) puts("");
}

超快速排序

什么超快速排序，明明就是冒泡排序！

最小交换次数等价于序列的逆序对数，

按照逆序对的定义，我们采用树状数组进行计算。

我们需要计算的是一个数之前比它大的数，离散化序列后就是树状数组板子啦。

const int N=5e5+10;
int n;
int a[N];
int tr[N];
void update(int x,int c)
{
    for(;x<=n;x+=(x&-x)) tr[x]+=c;
}
int query(int x)
{
    int res=0;
    for(;x;x-=(x&-x)) res+=tr[x];
    return res;
}
vector<int> v;
void main(){
    while(n=R)
    {
        int ans=0;
        fo(i,1,n) tr[i]=0;
        fo(i,1,n) a[i]=R;
        v.clear();
        fo(i,1,n) v.pb(a[i]);
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        fo(i,1,n) a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
        fo(i,1,n)
        {
            ans+=i-1-query(a[i]);
            update(a[i],1);
        }
        write(ans),puts("");
    }
}

奇数码问题

将矩阵中去掉 0，拍平成序列。

两个序列的逆序对数奇偶性相同，那么两个矩阵可达。

const int N=3e5+10;
int n;
int a[N],b[N];
int tr[N];
void update(int x,int c)
{
    for(;x<=n*n;x+=(x&-x)) tr[x]+=c;
}
int query(int x)
{
    int res=0;
    for(;x;x-=(x&-x)) res+=tr[x];
    return res;
}
void main(){
    while(cin>>n)
    {
        int cnt=1;
        fo(i,1,n*n)
        {
            a[cnt]=R+1;
            if(a[cnt]!=1) cnt++;
        }
        cnt=1;
        fo(i,1,n*n)
        {
            b[cnt]=R+1;
            if(b[cnt]!=1) cnt++;
        }
        fo(i,1,n*n) tr[i]=0;
        int ans1=0,ans2=0;
        fo(i,1,n*n-1)
        {
            ans1+=i-1-query(a[i]);
            update(a[i],1);
        }
        fo(i,1,n*n) tr[i]=0;
        fo(i,1,n*n-1)
        {
            ans2+=i-1-query(b[i]);
            update(b[i],1);
        }
        if(ans1%2==ans2%2) puts("TAK");
        else puts("NIE"); 
    }
}