语法糖

常用处理

模下运算


ll add(ll x,ll y){
    x+=y;
    //key,模意义
    if(x>=M)x-=M;if(x<0)x+=M;
    return x;
}
ll mul(ll x,ll y){
    return x*1ll*y%M;
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%M;
        a=a*a%M;b>>=1;
    }
    return res;
}
int inv(int x){return ksm(x,M-2);}
ll dv(ll x,ll y){//x/y
    return mul(x,inv(y,M-2));
}
//(A - B) mod C = (A mod C - B mod C) mod C

二进制优化拆分

//二进制拆分，组合可以表示所有不大于s的选择情况
    REP(i,1,n){
        int s,x,y;cin>>s>>x>>y;
		for(int k=1;k<=s;k*=2)
		{
			w[++id]=y*k;
			v[id]=x*k;
			s-=k;
		}
		if(s){w[++id]=y*s;v[id]=x*s;}
    }

求逆序对

way1:树状数组

https://oi-wiki.org/ds/fenwick/#%E5%85%A8%E5%B1%80%E9%80%86%E5%BA%8F%E5%AF%B9%E5%85%A8%E5%B1%80%E4%BA%8C%E7%BB%B4%E5%81%8F%E5%BA%8F

树状数组可以较快完成单点修改和区间求和.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define REP(i,s,e) for(int i=s;i<=e;++i)
const int N=1e6+7,M=998244353;

int n,a[N],tr[N];
int lowbit(int x){return x&-x;}
void upd(int p,int v)
{
    //更新类似爬树过程
    while(p<=n){
        tr[p]+=v;
        p+=lowbit(p);
    }
}
int query(int p)//前p项和
{
    int ans=0;
    while(p>0){
        ans+=tr[p]; p-=lowbit(p);
    }
    return ans;
}
int query(int l,int r)//重载求区间和
{
    return query(r)-query(l-1);
}
ll inv()//求逆序对
{
    ll ans=0;
    REP(i,1,n)
    {
        ans+=(i-1)-query(a[i]);
        upd(a[i],1);
        //cout<<ans<<' ';
    }
    return ans;
}
void solve()
{
    cin>>n;
    REP(i,1,n)cin>>a[i];
    cout<<inv()<<' ';
}


字符

cstring
isalnum(c) 字母或数字 isalnum('a') → true
isalpha(c) 字母 isalpha('Z') → true
isdigit(c) 十进制数字 isdigit('5') → true
string
s.append(str) 追加 s.append("xyz")
s.insert(pos, str) 插入 s.insert(1, "abc")
s.erase(pos, len) 删除 s.erase(1, 2)
s.replace(pos, len, str) 替换 s.replace(1, 2, "new")
s.push_back(c) 末尾添加字符 s.push_back('!')
s.pop_back() 删除末尾字符 s.pop_back()
s.resize(n) 改变大小 s.resize(10, 'x')
s.swap(s2) 交换 s1.swap(s2)
输入输出
cin >> s 读取单词 遇到空白停止
getline(cin, s) 读取一行 包括空格
cin.getline(buf, size) C风格读取一行 用于字符数组
sstream 字符串流处理 #include <sstream>

生成二进制序列

递归生成会受制于层数,当N>?时会栈溢出.

迭代则类似于dfs的处理,用队列存储中间结果.假设已经获取到了n,调用此函数

void gene(){
    vector<ll>res;
    queue<string>q;
    q.push("1");
    while(q.size()){
        auto x=q.front();q.pop();
        res.push_back(stoi(x));
        if(x.size()<n)q.push(x+'0');q.push(x+'1');
    }
    for(auto &it:res)cout<<it<<'\n';
}

假设n<9,则int类型已经够用了.需要对更大的n支持,也可以用std::stol(), std::stoll()

输出控制

保留小数

printf("%.3f\\n",(a+b+c)/3);
cout<<fixed<<setprecision(3)<<(a+b+c)/3;
printf("%05d\\n",12);
cout<<setw(5)<<setfill('0')<<12<<endl;

next_permutation( 双向迭代器1,双向迭代器2); 会直接改变迭代器所在容器,并返回bool值. 相同用法的prev_permutation()修改为前一个字典序排列.

数据结构

树状数组

通俗来说,是二进制下标树.维护一个前缀和状态.


int n,a[N],tr[N];
int lowbit(int x){return x&-x;}
void upd(int p,int v)
{
    //更新类似爬树过程
    while(p<=n){
        tr[p]+=v;
        p+=lowbit(p);
    }
}
int query(int p)//前p项和
{
    int ans=0;
    while(p>0){
        ans+=tr[p]; p-=lowbit(p);
    }
    return ans;
}
int query(int l,int r)//重载求区间和
{
    return query(r)-query(l-1);
}

并查集

int fa[N];
//所有的操作都在根即代表节点上
void init(int n) {for (int i=1;i<=n;++i) fa[i]=i;}

int root(int id)//路径压缩的原理是直接指向根而不是先导节点
{
	  return fa[id]=(fa[id]==id ? id : root(fa[id]));
}

void fix(int i,int j) {fa[root(i)]=root(j);}

bool isSame(int x,int y){return root(x)==root(y);}
void upd(int n){REP(i,1,n)fa[i]=root(i);}//刷新

需要离散化的话,fa数组直接改哈希容器,动态加点.

Segment tree


#define L(x) x<<1
#define R(x) x<<1|1
const int N=1e5+7,M=998244353,inf=1e9;
ll n,a[N];
struct Seg
{
    ll St[N<<2],Lz[N<<2];
    ll merge(ll x,ll y)
    {
        //min(),max(),gcd()
        return x+y;//区间和
    }
    void apl(int u,int l,int r,ll d)
    {
        //最值+=d gcd不适用Lz
        St[u]+=1ll*(r-l+1)*d;//很可能溢出
        Lz[u]+=d;
    }
    void push(int u,int l,int r)
    {
        if(!Lz[u])return;
        int mid=l+(r-l)/2;
        apl(L(u),l,mid,Lz[u]);
        apl(R(u),mid+1,r,Lz[u]);
        Lz[u]=0;
    }
    void pull(int u)
    {
        St[u]=merge(St[L(u)],St[R(u)]);
    }
    void bld(int u,int l,int r)
    {
        Lz[u]=0;
        if(l==r){St[u]=a[l];return;}
        int mid=l+(r-l)/2;
        bld(L(u),l,mid);
        bld(R(u),mid+1,r);
        pull(u);
    }
    void upd(int u,int l,int r,int ql,int qr,ll d){
        if(ql<=l&&qr>=r){
            apl(u,l,r,d);return;
        }
        push(u,l,r);
        int mid=(l+r)>>1;
        if(ql<=mid)upd(L(u),l,mid,ql,qr,d);
        if(qr>mid)upd(R(u),mid+1,r,ql,qr,d);
        pull(u);
    }
    ll query(int u,int l,int r,int ql,int qr)
    {
        if(qr<l||r<ql)return 0;//max:-inf min:inf gcd:0

        if(ql<=l&&r<=qr)return St[u];
        push(u,l,r);
        int mid=l+(r-l)/2;
        return merge(query(L(u),l,mid,ql,qr),query(R(u),mid+1,r,ql,qr));
    }
    void bld(){bld(1,1,n);}
    void upd(int l,int r,ll d){upd(1,1,n,l,r,d);}
    ll que(int l,int r){return query(1,1,n,l,r);}

}seg;

#define L u<<1
#define R u<<1|1
const int N=5e5+7,P=998244353;
int a[N],n;
ll St[N<<2],Lz[N<<2];

ll merge(ll x,ll y){return max(x,y);}
void update(int u,ll d){
    St[u]+=d;Lz[u]+=d;
}
void push(int u){
    if(Lz[u]){
        update(L,Lz[u]);update(R,Lz[u]);
        Lz[u]=0;
    }
}
void pull(int u){St[u]=merge(St[L],St[R]);}
void build(int u,int l,int r){
    Lz[u]=0;//
    if(l==r){St[u]=a[l];return;}
    int mid=(l+r)>>1;
    build(L,l,mid);build(R,mid+1,r);
    pull(u);
}
void add(int u,int l,int r,int ql,int qr,int d){
    if(ql<=l&&qr>=r){
        update(u,d);return;
    }
    push(u);
    int mid=(l+r)>>1;
    if(ql<=mid)add(L,l,mid,ql,qr,d);
    if(qr>mid)add(R,mid+1,r,ql,qr,d);
    pull(u);
}

BTW,关于Lz初始化的实现,在一开始考虑用vector的reserve()实现,但只是预留空间,不会初始化,导致Lz不会正确重置甚至无法访问.

总之,最好的方式是建树时读取原数组顺便重置Lz数组.

算法

拓扑排序

本质计算出一个序列

队列维护不受约束的点,进行bfs,对访问到的点入度减1,如果为0则入队.如果bfs结束仍有入度不为零的点,排序失败.

  • 拓扑排序可能不止一个,要得到保持字典序的排序,使用优先队列.
  • 拓扑排序成功当且仅当序列大小等于节点数
  • 线性dp的转移关系构成的图为有向无环图
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define ALL(x) x.begin(),x.end()
#define REP(i,s,e) for(int i=s;i<=e;++i)
#define REP2(i,s,e) for(int i=s;i>=e;--i)
const int N=1e5+7,P=998244353,inf=1e9;
int ind[N];
vector<int> g[N];
void solve(){
    int n,m;cin>>n>>m;
    REP(i,1,m)
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v);
        ind[v]++;
    }
    priority_queue<int,vector<int>,greater<int>>q;
    REP(i,1,n)if(!ind[i])q.push(i);
    vector<int>res;
    while(q.size())
    {
        auto u=q.top();q.pop();
        res.push_back(u);
        for(auto v:g[u]){ind[v]--;if(!ind[v])q.push(v);}
    }
    if(res.size()!=n)cout<<-1<<'\n';
    else for(auto x:res)cout<<x<<' ';
}

不同子串数量(后缀数组)

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define ALL1(x) x.begin(),x.end()
#define REP(i,s,e) for(int i=s;i<=e;++i)
#define REP2(i,s,e) for(int i=s;i>=e;--i)
const int N=2e5+7;
int sa[N],rk[N],tmp[N],lcp[N];

void bld_sa(string s)
{
    int n=s.size();
    REP(i,0,n-1)
    {
        sa[i]=i;//
        rk[i]=s[i]-'a';//
    }
    for(int k=1;k<n;k<<=1)
    {
        sort(sa,sa+n,[&](int i,int j){
            if(rk[i]!=rk[j])return rk[i]<rk[j];
            return (i+k<n?rk[i+k]:-1)<(j+k<n?rk[j+k]:-1);
        });
        tmp[sa[0]]=0;
        REP(i,1,n-1)
        {
            tmp[sa[i]]=tmp[sa[i-1]];

            if(rk[sa[i]]!=rk[sa[i-1]]||
                (sa[i]+k<n?rk[sa[i]+k]:-1)!=(sa[i-1]+k<n?rk[sa[i-1]+k]:-1)
            )tmp[sa[i]]++;
        }
        REP(i,0,n-1)rk[i]=tmp[i];
    }
}
void bld_lcp(string s)
{
    int n=s.size(),h=0;
    REP(i,0,n-1)
    {
        if(rk[i]==0)continue;
        int j=sa[rk[i]-1];
        while(i+h<n&&j+h<n&&s[i+h]==s[j+h])
        {
            h++;
        }
        lcp[rk[i]]=h;
        if(h>0)h--;
    }
}
void solve(){
    int n;cin>>n;
    string s;cin>>s;
    bld_sa(s);
    bld_lcp(s);
    ll tot=1ll*n*(n+1)/2;
    REP(i,1,n-1)tot-=lcp[i];
    cout<<tot<<'\n';
    
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)solve();
    return 0;
}

多重背包

int w[N],v[N];
int dp[N];
void solve(){
    ll m,n;cin>>m>>n;
    int id=0;
    REP(i,1,n){
        int s,x,y;cin>>s>>x>>y;
        REP(j,1,s){
            w[++id]=y;v[id]=x;
        }
    }
    REP(i,1,m){
        REP(j,1,id){

            if(i-w[j]>=0)dp[i]=max(dp[i],dp[i-w[j]]+v[j]);
        }
    }
    cout<<dp[m];
}

无穷背包

ll y,n,m,dp[2][M];
struct E{
	ll w,v;
};
E a[N];
void solve()
{
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<=m;++j)
		{
			if (j-a[i].w>=0)dp[y][j]=max(dp[y][j-a[i].w]+a[i].v,dp[y^1][j]);
			else dp[y][j]=dp[y^1][j];
		}
		y^=1;
	}
	cout<<dp[n&0][m]<<'\n';
}

滚动哈希

ull toH(const string& s){
    ull h=0;
    for(auto c:s)h=h*base+c;//key
    return h;
}

ST表

//原数组，区间gcd稀疏表.对其它问题，替换gcd就行
int a[N],f_gcd[__lg(N)+1][N];
void init(int n)
{
		//计算存储
    REP(i,1,n)f_gcd[0][i]=a[i];
    REP(i,1,__lg(n))
    {
        for(int j=1;j+(1<<i)-1<=n;++j)
        {
            f_gcd[i][j]=gcd(f_gcd[i-1][j],f_gcd[i-1][j+(1<<(i-1))]);
        }
    }
}
int query(int l,int r)
{
    int s=__lg(r-l+1);
    return gcd(f_gcd[s][l],f_gcd[s][r-(1<<s)+1]);
}


欧拉筛

对N≤1e8,筛法完全可以胜任标记并存储所有质数。

vector<bool> vis(N,0);//bool
vector<int> pri;
void init()
{
    REP1(i,2,N)
    {
        if(vis[i])continue;
        pri.push_back(i);
        for(int k=i;k<=N;k+=i)vis[k]=1;
    }
    cout<<pri.size();
}

线性筛

int prime[6000010], cnt;
bool isprime[N + 10];
void prim() {
	isprime[0] = isprime[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!isprime[i]) prime[++cnt] = i;
		for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
			isprime[i * prime[j]] = 1;
			if (i % prime[j] == 0) break;
		}
	}
}

KMP

int kmp(string& s,string& p)
{
    int m=p.size();
    //匹配和预处理过程相似,一起处理
    string us=p+'#'+s;
    int k=us.size();
    vector<int> nx(k,0);//变量名别用next...
    for(int i=1;i<k;++i)
    {
        int len=nx[i-1];
        while(len&&us[i]!=us[len]){
            len=nx[len-1];
        }
        if(us[i]==us[len]){
            nx[i]=len+1;
            if(nx[i]==m)return i-2*m;
        }
    }
    return -1;
}

高精度加

string add(string a,string b){// a>b
    stack<int> res;
    string ans;
    int up=0,i=a.size(),j=b.size();
    
    while(i||j||up){
        int curr=0;
        if (i) curr+=a[--i]-'0';
        if (j) curr+=b[--j]-'0';
        curr+=up;
        up=curr/10;
        res.push(curr%10);
    }
    while(!res.empty()){
        ans+=to_string(res.top());
        res.pop();
    }
    return ans;

}

高精度乘

  • 高精度乘小数

vector<int> mul(vector<int>&A,int b)
{
    vector<int>c;
    int t=0;
    for(int i=0;i<A.size()||t;++i)
    {
        if(i<A.size())t+=b*A[i];
        c.push_back(t%10);
        t/=10;
    }
    while(c.size()>1&&c.back()==0)c.pop_back();
    return c;
}
bool bigger(vector<int>&A,vector<int>&B)//比较大小
{
    if(A.size()!=B.size())return A.size()>B.size();
    for(int i=A.size()-1;i>=0;--i)if(A[i]!=B[i])return A[i]>B[i];
    return false;
}
  • 高精度乘高精度
vector<int> mul(vector<int> a,vector<int>b)
{
    int len1=a.size(),len2=b.size();
    vector<int>c(len1+len2,0);
    for(int i=0;i<len1;++i)
        for(int j=0;j<len2;++j)
        {
            c[i+j]+=a[i]*b[j];
        }
    int t=0;
    for(int i=0;i<c.size();++i)
    {
        t+=c[i];
        c[i]=t%10;
        t/=10;
    }
    while(c.size()>1&&c.back()==0)c.pop_back();
    return c;
}

最长非降子序列(LIS)

way1:dp维护最大序列长度,O(n*2)的时间复杂度

REP(i,1,n)
{
    dp[i]=1;//dp[x]表示始于位置x的最长子序列长度
    REP(j,1,i-1)
    {
        //尝试更新(连接)之前的位置
        if(a[i]>=a[j])dp[i]=max(dp[i],dp[j]+1);
    }
}
ll res=0;
REP(i,1,n)res=max(res,dp[i]);

way2: 维护长度->最优结尾的映射(二分)

void LIS(vector<int>& vec)
{
    //不再像dp方法一样维护最大长度
    //stk的(下标+1,val)相当于长度->最优结尾的映射
    vector<int> stk;
    for(auto x:vec)
    {
        auto pos=upper_bound(ALL(stk),x);
        if(pos==stk.end())
            stk.push_back(x);
        else *pos=x;
    }
    //for(auto it:stk)cout<<it<<' ';
    cout<<stk.size();
}

再考虑一个问题:知道长度,还能求出具体序列吗?

多源最短路径

当对全部点遍历复杂度不可接受时,考虑筛选出一些点进行多源bfs.

多源bfs,从实现上看就像从一个虚点开始的bfs,多个源点作为其邻点入队.

V lv(n+1),dis(n+1,-1);
REP1(i,1,n)lv[i]=g[i].size();
    queue<int> q;
    REP1(i,1,n){
        for(auto &v:g[i]){
            if(lv[v]>lv[i]){
                dis[i]=1; q.push(i); break;
            }
        }
    }
    while(q.size()){
        int u=q.front();q.pop();
        for(auto& v:g[u]){
            if(lv[v]<=lv[u]&&dis[v]==-1){
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    REP1(i,1,n)cout<<dis[i]<<' ';cout<<'\n';

Floyd

# 三重循环，枚举每个中间点 k
   for k in range(n):
       for i in range(n):
           # 跳过不可达的起点
           if dist[i][k] == float('inf'):
               continue
           for j in range(n):
               # 跳过不可达的终点
               if dist[k][j] == float('inf'):
                   continue
               # 如果经过 k 能让 i 到 j 更短，则更新
               if dist[i][j] > dist[i][k] + dist[k][j]:
                   dist[i][j] = dist[i][k] + dist[k][j]

Dijkstra

Input: 

graph G=(V,E), (un)directed;Positive edge and vertex.

Init:

for all u in V:

​	dist(u)=inf; prev(u)=0;

dist(s)=0;

Dijkstra:

Q=makequeue(V)

while Q is not empty:

​	u=deletemin(Q)

​	for all edges (u,v):

​		if dist(v)>dist(u)+l(u,v): 

​		dist(v)=dist(u)+l(u,v)

​		prev(v)=u;

​	REC
void dij(int s) {
	priority_queue <pii, vector<pii>, greater<pii> > q; 
	memset(dis, 0x7f7f7f7f, sizeof(dis));
	q.push({0, s});
	dis[s] = 0;
	while (!q.empty()) {
		pii u = q.top(); q.pop();
		int pos = u.second;
		if (vis[pos]) continue;
		vis[pos] = 1;
		for (int j = last[pos]; j; j = e[j].next) {
			int v = e[j].to;
			if (vis[v]) continue;
			if (dis[pos] + e[j].w < dis[v]) dis[v] = dis[pos] + e[j].w, q.push({dis[v], v});
		}
	}
}

单调栈

https://codeforces.com/problemset/problem/2165/A

每次选择一个小的元素,被删除的时候,代价为相邻元素中较小的一个.也就是说, 尽量和“比它大、但尽量小的那个数”合并. 要找到左右两侧第一个大于其的元素.

要解决几个问题:

  • 如何快速删除,维护,找到第一个大于元素,用什么数据结构?
  • 解决环的问题

单调递减栈,在维护的同时可以快速删除;从最大元素处拉直(作为栈底).

先考虑最简单的情况:整个数组单调,从最大元素加到倒数第二个元素(都加左侧元素(第一个大于的元素))就是结果.当出现不和谐元素,即一般情况时,要综合考虑左右侧.总之都是一个逻辑:找到最近的较大元素,维护单调栈的过程即是综合比较的过程

stack<int> stk;
void op(int st,int ed){
    REP(i,st,ed)
    {
        int x=a[i];
        while(stk.size()&&stk.top()<x){
            stk.pop();
            res+=min(stk.top(),x);
        }
        stk.push(x);
    }
}
void solve(){
    cin>>n;int p=0;
    REP(i,1,n){cin>>a[i];p=(a[p]<a[i]?i:p);}
    op(p,n);op(1,p-1);
    while(stk.size()>1){
        stk.pop();res+=stk.top();
    }
    cout<<res<<'\n';
    res=0;stk.pop();
}

从简单情况到一般情况,从找差异的过程中抽象出规则.

Kadane-最大和子序列

def max_subarray_kadane(nums):
    if not nums:
        return 0
    
    max_sum = current_sum = nums[0]
    
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

可以看作是隐式双指针法.l,r,都在for循环第一个语句中

这样想:如果cur+a[i]<a[i],不是说明cur为负值嘛,甩掉就行了,对应左指针的更新;否则加上a[i],对应右指针的线性扫描.好处是实现简洁,指针操纵要注意的实在太多了,但不能记录l,r了…image-20251124232607722

这题可以通过1->-1,0->1来适配该算法,以统计0净数量最大的区间.相比于更改算法结构,构造一个导出数组显然更简单.注意题干,确切执行一次操作,哪怕全是1.