板子(更新ing

优化

取消同步流

ios::sync_with_stdio(0);
cin.tie(0);

读入优化

朴素读入优化

int read() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}

fread读入优化

inline char getcha(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int read(){
    int res=0;char ch=getcha();bool XX=false;
    for(;!isdigit(ch);ch=getcha())
      (ch=='-') && (XX=true);
    for(;isdigit(ch);ch=getcha())
      res=(res<<3)+(res<<1)+(ch^48);
    return XX?-res:res;
}

实数读入优化

inline double dbread(){
    double X=0,Y=1.0; int w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=X*10+(ch^48),ch=getchar();
    ch=getchar();//读入小数点
    while(isdigit(ch)) X+=(Y/=10)*(ch^48),ch=getchar();
    return w?-X:X;
}

输出优化

朴素输出优化

void write(int x) {
  if (x < 0) {
    x = -x;
    putchar('-');
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}

write输出优化

char pbuf[100000],*pp=pbuf;
void push(const char c) {
    if(pp-pbuf==100000) fwrite(pbuf,1,100000,stdout),pp=pbuf;
    *pp++=c;
}
void write(int x){
    static int sta[35];
    int top=0;
    do{sta[top++]=x%10,x/=10;}while(x);
    while(top) push(sta[--top]+'0');
}
//请大家在程序结束前加上一句fwrite(pbuf,1,pp-pbuf,stdout);pp=pbuf;
//防止出现没输出完成的类似错误

O2O3优化

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

离散化

int a[N],b[N],x[N*2],p[N*2]; //乘几具体看题目

int n;cin>>n;
for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
    x[cnt++]=a[i];
    x[cnt++]=b[i];
}
sort(x,x+cnt);
cnt=unique(x,x+cnt)-x;
for(int i=0;i<n;i++){
    a[i]=lower_bound(x,x+cnt,a[i])-x;
    b[i]=lower_bound(x,x+cnt,b[i])-x;
}

数论模板

欧几里得算法(辗转相除法)

gcd(a,b)=gcd(b,a%b)

int gcd(int a, int b){
    return !b ? a : gcd (b, a % b);
}

a,b的最小公倍数

int lcm(int a, int b){ 
    return a / gcd(a, b) * b;
}

扩展欧几里得算法

裴蜀定理:若 a,b 是整数,且 gcd(a,b)=d,那么对于任意的整数 x,y, ax+by 都一定是 d 的倍数,特别地,一定存在整数 x,y,使 ax+by=d 成立。

扩展欧几里德常用在求解模线性方程及方程组中。

https://www.luogu.com.cn/problem/P1082

#include <bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int gcd=exgcd(b,a%b,x,y),temp=x;
    x=y,y=temp-a/b*y;
    return gcd;
}

int main(){
    int a,b,x,y;
    cin>>a>>b;
    exgcd(a,b,x,y);
    cout<<(x%b+b)%b<<"\n";
    return 0;
}

快速幂(a^b % mod)

ll fpow(ll a,ll b,ll mod){
    if(mod==1) return 0;
    ll ans=1%mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

矩阵快速幂

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
struct node{
    ll mat[105][105];
};
int n;
node mul(node x,node y){
    node tmp;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            tmp.mat[i][j]=0;
            for(int k=0;k<n;k++){
                tmp.mat[i][j]+=(x.mat[i][k]*y.mat[k][j])%mod;
            }
            tmp.mat[i][j]%=mod;
        }
    }
    return tmp;
}
node matpow(node x,node y,ll num){
    while(num){
        if(num&1){
            y=mul(x,y);
        }
        x=mul(x,x);
        num=num>>1;
    }
    return y;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    node x,y;//x是系数矩阵,y是单位矩阵 
    ll k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>x.mat[i][j];
            if(i==j) y.mat[i][j]=1;
        }
    }
    node c=matpow(x,y,k);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<c.mat[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

乘法逆元

快速幂逆元

https://www.acwing.com/problem/content/878/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod;
ll fpow(ll a,ll b){
    ll ans=1%mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int main(){
    int n; cin>>n;
    while(n--){
        int a;
        cin>>a>>mod;
        if(a%mod==0) puts("impossible");
        else cout<<fpow(a,mod-2)<<"\n";
    }
    return 0;
}

线性递推求逆元

https://www.luogu.com.cn/problem/P3811

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e6+10;
ll n,mod,inv[N];
int main(){
    cin>>n>>mod;
    inv[1]=1;
    for(int i=2;i<=n;i++) inv[i]=(mod-(mod/i))*inv[mod%i]%mod;
    for(int i=1;i<=n;i++) cout<<inv[i]<<"\n";
    return 0;
}

分数取模(求单个)

https://ac.nowcoder.com/acm/contest/80/B

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
typedef long long ll;
ll fpow(ll a,ll b){
    if(mod==1) return 0;
    ll ans=1%mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main() {
    ll n,m,fz,fm;
    cin>>n>>m;
    fz=n*n-m;fm=n*n;
    cout<<(fz%mod)*fpow(fm,mod-2)%mod<<"\n";
    return 0;
}

分数取模(存数组)(补

素数筛(补

筛法求积性函数

中国剩余定理

整除分块

数据结构

树状数组

单点修改,区间查询

#include <bits/stdc++.h>
using namespace std;
const int N=500010;
int q[N],t[N];
int n,m;

// 算出x二进制的从右往左出现第一个1以及这个1之后的那些0组成数的二进制对应的十进制的数
inline int lowbit(int x){
    return x&(-x);
}

void add(int x,int v){    //在x位置加上v
    while(x<=n){
        t[x]+=v;
        x+=lowbit(x);
    }
}

//求前缀和
int getsum(int x){
    int res=0;
    while(x>0){
        res+=t[x];
        x-=lowbit(x);
    }
    return res;
}

int main(){
    int k,a,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        scanf("%d",&q[i]);
        add(i,q[i]);   //树状数组
    }

    for(int i=0;i<m;i++){
        scanf("%d%d%d",&k,&a,&b);
        if(k==2) printf("%d\n",getsum(b)-getsum(a-1));
        else if(k==1) add(a,b);
    }
    return 0;
}

区间修改,单点查询

#include <bits/stdc++.h>
using namespace std;
const int N=500010;
int q[N],d[N],tree[N],n,m;

inline int lowbit(int x){
    return x&(-x);
}

void add(int p,int x){
    for(int i=p;i<=n;i+=lowbit(i)) tree[i]+=x;
}

int getsum(int p){
    int ans=0;
    for(int i=p;i;i-=lowbit(i)) ans+=tree[i];
    return ans;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>q[i];
        d[i]=q[i]-q[i-1];
        add(i,d[i]);
    }
    for(int i=0;i<m;i++){
        int op,x,y,k;
        cin>>op;
        if(op==1) {
            cin>>x>>y>>k;
            add(x,k),add(y+1,-k);
        }
        else{
            cin>>x;
            cout<<getsum(x)<<"\n";
        }
    }
    return 0;
}

线段树

区间修改,区间查询

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll a[N];
ll tree[N<<2];
ll lazy[N<<2];

inline ll ls(ll x){return x<<1;}
inline ll rs(ll x){return x<<1|1;}

inline void pushup(ll u){
    tree[u]=tree[ls(u)]+tree[rs(u)];
}

inline void build(ll u,ll ul,ll ur){
    lazy[u]=0; 
    if(ul==ur){tree[u]=a[ul];return;}
    ll mid=(ul+ur)>>1;
    build(ls(u),ul,mid);
    build(rs(u),mid+1,ur);
    pushup(u);
}

inline void addlazy(ll u,ll ul,ll ur,ll v){
    lazy[u]+=v;
    tree[u]+=v*(ur-ul+1);
}

inline void pushdown(ll u,ll ul,ll ur){
    if(lazy[u]){
        ll mid=(ul+ur)>>1;
        addlazy(ls(u),ul,mid,lazy[u]);
        addlazy(rs(u),mid+1,ur,lazy[u]);
        lazy[u]=0;
    }
}

//区间修改
inline void update(ll l,ll r,ll u,ll ul,ll ur,ll v){
    if(l<=ul&&ur<=r){
        addlazy(u,ul,ur,v);
        return;
    }
    pushdown(u,ul,ur);
    ll mid=(ul+ur)>>1;
    if(l<=mid) update(l,r,ls(u),ul,mid,v);
    if(r>mid) update(l,r,rs(u),mid+1,ur,v);
    pushup(u);
} 

//区间查询
inline ll query(ll l,ll r,ll u,ll ul,ll ur){
    if(l<=ul&&ur<=r) return tree[u]; 
    pushdown(u,ul,ur);
    ll res=0;
    ll mid=(ul+ur)>>1;
    if(l<=mid) res+=query(l,r,ls(u),ul,mid);
    if(r>mid) res+=query(l,r,rs(u),mid+1,ur);
    return res;
}

int main(){
    ll n,m;cin>>n>>m;
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--){
        int t;scanf("%d",&t);
        ll l,r,v;
        if(t==1){
            scanf("%lld%lld%lld",&l,&r,&v);
            update(l,r,1,1,n,v);
        }
        else{
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",query(l,r,1,1,n));
        }
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
ll q[N];
int p;
struct node{
    int l,r; //tree[i].l和tree[i].r分别表示这个点代表的线段的左右下标
    ll sum; //tree[i].sum表示这个节点表示的线段和
    ll addlazy,mullazy; //懒标记
}tree[N<<2];  //开四倍空间

inline void pushup(int u){        //更新函数
    tree[u].sum=(tree[u<<1].sum+tree[u<<1|1].sum)%p; //父节点的和等于两个子节点之和
}

inline void pushdown(int u){
    tree[u<<1].sum=((tree[u].mullazy*tree[u<<1].sum)%p+(tree[u].addlazy*(tree[u<<1].r-tree[u<<1].l+1))%p)%p;
    tree[u<<1|1].sum=((tree[u].mullazy*tree[u<<1|1].sum)%p+(tree[u].addlazy*(tree[u<<1|1].r-tree[u<<1|1].l+1))%p)%p;

    tree[u<<1].mullazy=(tree[u<<1].mullazy*tree[u].mullazy)%p;
    tree[u<<1|1].mullazy=(tree[u<<1|1].mullazy*tree[u].mullazy)%p;

    tree[u<<1].addlazy=((tree[u<<1].addlazy*tree[u].mullazy)%p+tree[u].addlazy)%p;
    tree[u<<1|1].addlazy=((tree[u<<1|1].addlazy*tree[u].mullazy)%p+tree[u].addlazy)%p;

    tree[u].mullazy=1;
    tree[u].addlazy=0;
}

//一个节点为x 它的父节点为x/2(x>>1) 左儿子2x(x<<1) 右儿子2x+1(x<<1|1)
inline void build(int u,int l,int r){
    tree[u].l=l;
    tree[u].r=r;
    tree[u].mullazy=1;
    if(l==r){     //左端点等于右端点,即为叶子节点,直接赋值即可
        tree[u].sum=q[l]%p;
        return;
    }

    int mid=(l+r)>>1;    //mid则为中间点,左儿子的结点区间为[l,mid],右儿子的结点区间为[m+1,r]
    build(u<<1,l,mid);    //递归构造左儿子结点
    build(u<<1|1,mid+1,r);    //递归构造右儿子结点
    pushup(u);    //更新父节点
}

inline void add(int u,int l,int r,ll v) {  //u为结点下标,[l,r]为修改区间,v为要加上的值
    if(l<=tree[u].l&&r>=tree[u].r){
        tree[u].sum=(tree[u].sum+((tree[u].r-tree[u].l+1)*v)%p)%p;
        tree[u].addlazy=(tree[u].addlazy+v)%p;
        return;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(l<=mid) add(u<<1,l,r,v);
    if(r>mid) add(u<<1|1,l,r,v);
    pushup(u);
} 

inline void mul(int u,int l,int r,ll v) {  //u为结点下标,[l,r]为修改区间,v为要乘上的值
    if(l<=tree[u].l&&r>=tree[u].r){
        tree[u].sum=(tree[u].sum*v)%p;
        tree[u].mullazy=(tree[u].mullazy*v)%p;
        tree[u].addlazy=(tree[u].addlazy*v)%p;
        return;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(l<=mid) mul(u<<1,l,r,v);
    if(r>mid) mul(u<<1|1,l,r,v);
    pushup(u);
} 

//区间查询
inline ll query(int u,int l,int r){    //u为结点下标, [l,r]即为要查询的区间
    if(tree[u].l>=l&&tree[u].r<=r)    //如果当前结点的区间包含于(?)要查询的区间内,则返回结点信息且不需要往下递归
        return tree[u].sum;
    ll sum=0;

    pushdown(u);

    int mid=(tree[u].l+tree[u].r)>>1;    //mid则为中间点,左儿子的结点区间为[l,mid],右儿子的结点区间为[mid+1,r]

    if(l<=mid)   //先找和左边无交集
        sum=(sum+query(u<<1,l,r))%p; //左儿子

    if(r>mid)   //再找和右边无交集
        sum=(sum+query(u<<1|1,l,r))%p; //加上右儿子

    return sum;    //返回当前结点得到的信息
}


int main(){
    int n,m;
    int t,x,y;
    ll k;
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++) scanf("%lld",&q[i]);

    build(1,1,n);

    for(int i=0;i<m;i++){
        scanf("%d",&t);
        if(t==1){
            scanf("%d%d%lld",&x,&y,&k);
            mul(1,x,y,k);
        }
        else if(t==2){
            scanf("%d%d%lld",&x,&y,&k);
            add(1,x,y,k);
        } 
        else if(t==3){
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(1,x,y));
        }
    }
    return 0;
}

维护区间最值操作与区间历史最值

  • 1 l r k:对于所有的 ,将 加上 可以为负数)。
  • 2 l r v:对于所有的 ,将 变成
  • 3 l r:求
  • 4 l r:对于所有的 ,求 的最大值。
  • 5 l r:对于所有的 ,求 的最大值。

在每一次操作后,我们都进行一次更新,让

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10,INF=0x3f3f3f3f;

struct SegmentTree{
    struct Node{
        int l, r;
        int mx, mx_, se, cnt; ll sum;
        int add1, add1_, add2, add2_;
    } tr[N<<2];
    #define lc (o<<1)
    #define rc (o<<1|1)
    void pushup(int o){
        tr[o].sum=tr[lc].sum+tr[rc].sum;
        tr[o].mx_=max(tr[lc].mx_, tr[rc].mx_);
        if (tr[lc].mx==tr[rc].mx){
            tr[o].mx=tr[lc].mx;
            tr[o].se=max(tr[lc].se, tr[rc].se);
            tr[o].cnt=tr[lc].cnt+tr[rc].cnt;
        }
        else if (tr[lc].mx>tr[rc].mx){
            tr[o].mx=tr[lc].mx;
            tr[o].se=max(tr[lc].se, tr[rc].mx);
            tr[o].cnt=tr[lc].cnt;
        }
        else{
            tr[o].mx=tr[rc].mx;
            tr[o].se=max(tr[lc].mx, tr[rc].se);
            tr[o].cnt=tr[rc].cnt;
        }
    }
    void update(int o, int k1, int k1_, int k2, int k2_){
        tr[o].sum+=1ll*k1*tr[o].cnt+1ll*k2*(tr[o].r-tr[o].l+1-tr[o].cnt);
        tr[o].mx_=max(tr[o].mx_, tr[o].mx+k1_);
        tr[o].add1_=max(tr[o].add1_, tr[o].add1+k1_);
        tr[o].mx+=k1, tr[o].add1+=k1;
        tr[o].add2_=max(tr[o].add2_, tr[o].add2+k2_);
        if (tr[o].se!=-INF) tr[o].se+=k2;
        tr[o].add2+=k2;
    }
    void pushdown(int o){
        int tmp=max(tr[lc].mx, tr[rc].mx);
        if (tr[lc].mx==tmp)
            update(lc, tr[o].add1, tr[o].add1_, tr[o].add2, tr[o].add2_);
        else update(lc, tr[o].add2, tr[o].add2_, tr[o].add2, tr[o].add2_);
        if (tr[rc].mx==tmp)
            update(rc, tr[o].add1, tr[o].add1_, tr[o].add2, tr[o].add2_);
        else update(rc, tr[o].add2, tr[o].add2_, tr[o].add2, tr[o].add2_);
        tr[o].add1=tr[o].add1_=tr[o].add2=tr[o].add2_=0;
    }
    void build(int o, int l, int r, int* a){
        tr[o].l=l, tr[o].r=r;
        tr[o].add1=tr[o].add1_=tr[o].add2=tr[o].add2_=0;
        if (l==r){
            tr[o].sum=tr[o].mx_=tr[o].mx=a[l];
            tr[o].se=-INF, tr[o].cnt=1;
            return;
        }
        int mid=l+r>>1;
        build(lc, l, mid, a);
        build(rc, mid+1, r, a);
        pushup(o);
    }
    void modify1(int o, int l, int r, int k){
        if (tr[o].l>r||tr[o].r<l) return;
        if (l<=tr[o].l&&tr[o].r<=r)
            { update(o, k, k, k, k); return; }
        pushdown(o);
        modify1(lc, l, r, k), modify1(rc, l, r, k);
        pushup(o);
    }
    void modify2(int o, int l, int r, int k){
        if (tr[o].l>r||tr[o].r<l||k>=tr[o].mx) return;
        if (l<=tr[o].l&&tr[o].r<=r&&k>tr[o].se)
            { update(o, k-tr[o].mx, k-tr[o].mx, 0, 0); return; }
        pushdown(o);
        modify2(lc, l, r, k), modify2(rc, l, r, k);
        pushup(o);
    }
    ll query3(int o, int l, int r){
        if (tr[o].l>r||tr[o].r<l) return 0;
        if (l<=tr[o].l&&tr[o].r<=r) return tr[o].sum;
        pushdown(o);
        return query3(lc, l, r)+query3(rc, l, r);
    }
    int query4(int o, int l, int r){
        if (tr[o].l>r||tr[o].r<l) return -INF;
        if (l<=tr[o].l&&tr[o].r<=r) return tr[o].mx;
        pushdown(o);
        return max(query4(lc, l, r), query4(rc, l, r));
    }
    int query5(int o, int l, int r){
        if (tr[o].l>r||tr[o].r<l) return -INF;
        if (l<=tr[o].l&&tr[o].r<=r) return tr[o].mx_;
        pushdown(o);
        return max(query5(lc, l, r), query5(rc, l, r));
    }
    #undef lc
    #undef rc
} sgt;
int a[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sgt.build(1, 1, n, a);
    while (m--){
        int op, l, r, k;
        cin>>op;
        switch (op){
            case 1:
                cin>>l>>r>>k;
                sgt.modify1(1, l, r, k);
                break;
            case 2:
                cin>>l>>r>>k;
                sgt.modify2(1, l, r, k);
                break;
            case 3:
                cin>>l>>r;
                cout<<sgt.query3(1, l, r)<<"\n";
                break;
            case 4:
                cin>>l>>r;
                cout<<sgt.query4(1, l, r)<<"\n";
                break;
            case 5:
                cin>>l>>r;
                cout<<sgt.query5(1, l, r)<<"\n";
                break;
        }
    }
    return 0;
}

李超线段树

https://www.luogu.com.cn/problem/P4097

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> pdi;
const int N=1e5+10,mod1=39989,mod2=1e9,INF=0x3f3f3f3f;

int cnt,lastans;
double k[N],b[N];
int tag[N<<2];

inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline double calc(int i,int x){return b[i]+k[i]*x;}

void add(int x0,int y0,int x1,int y1) {
    cnt++;
    if(x0==x1){ //斜率不存在 
        k[cnt]=0;
        b[cnt]=max(y1,y0);
    }
    else{
        k[cnt]=1.0*(y1-y0)/(x1-x0);
        b[cnt]=y0-k[cnt]*x0; 
    } 
}

void update(int l,int r,int p,int pl,int pr,int x){
    int mid=(pl+pr)>>1;
    if(l<=pl&&pr<=r){
        if(pl==pr){
            if(calc(tag[p],pl)<calc(x,pl)) tag[p]=x;
            return;
        }
        if(!tag[p]){tag[p]=x;return;}
        else{
            double y1=calc(tag[p],mid),y2=calc(x,mid);
            if(k[tag[p]]<k[x]) {
                if(y1<=y2) {update(l,r,ls(p),pl,mid,tag[p]);tag[p]=x;} 
                else {update(l,r,rs(p),mid+1,pr,x);}
            }
            else if(k[tag[p]]>k[x]) {
                if(y1<=y2) {update(l,r,rs(p),mid+1,pr,tag[p]);tag[p]=x;}
                else {update(l,r,ls(p),pl,mid,x);}
            }
            else if(b[tag[p]]>b[x]){tag[p]=x;}
        } 
        return;
    }
    if(l<=mid) update(l,r,ls(p),pl,mid,x);
    if(r>mid) update(l,r,rs(p),mid+1,pr,x);
}

pdi query(int p,int l,int r,int x){
    if (r<x||x<l) return {0,0};
    if(l==r) {
        return {calc(tag[p],l),tag[p]};
    }
    double res=calc(tag[p],x);
    int ansid=tag[p];
    int mid=(l+r)>>1;
    if(x<=mid){
        auto temp=query(ls(p),l,mid,x);
        if(res<temp.first){
            res=temp.first;
            ansid=temp.second;
        }
        else if(res==temp.first) {
            ansid=min(ansid,temp.second);
        }
    }
    else {
        auto temp=query(rs(p),mid+1,r,x);
        if(res<temp.first){
            res=temp.first;
            ansid=temp.second;
        }
        else if(res==temp.first){
            ansid=min(ansid,temp.second);
        } 
    }
    return {res,ansid};
}

int main() {
    int n;cin>>n;
    while(n--){
        int op;cin>>op;
        if(op==1){
            int x0,y0,x1,y1;
            cin>>x0>>y0>>x1>>y1;
            x0=(x0+lastans-1)%mod1+1;
            x1=(x1+lastans-1)%mod1+1;
            y0=(y0+lastans-1)%mod2+1;
            y1=(y1+lastans-1)%mod2+1;
            if(x0>x1) swap(x0,x1),swap(y0,y1);
            add(x0,y0,x1,y1);
            update(x0,x1,1,1,mod1,cnt);
        }
        else {
            int x;cin>>x;
            x=(x+lastans-1)%mod1+1;
            lastans=query(1,1,mod1,x).second;
            cout<<lastans<<"\n";
        }
    }
    return 0;
}

扫描线

矩形面积并
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
int n,m;
int y[N<<1];

struct Segment{
    int x;
    int y1,y2;
    int state;//是左边还是右边
    bool operator< (const Segment &t)const{
        return x<t.x;
    }
}seg[N<<1];

struct node{
    int l,r;
    int cover;//当前区间覆盖次数
    ll len;//至少被覆盖1次的区间长度
}tree[N<<4];

inline void pushup(int u){
    if(tree[u].cover) tree[u].len=tree[u].r-tree[u].l;
    else tree[u].len=tree[u<<1].len+tree[u<<1|1].len;
}

void build(int u,int l,int r){
    tree[u].l=y[l],tree[u].r=y[r];
    if(r-l<=1) return;
    int mid=(l+r)>>1;
    build(u<<1,l,mid),build(u<<1|1,mid,r);
}

void modify(int u,int l,int r,int k){
    int x=tree[u].l,y=tree[u].r;
    if(x>=l&&y<=r){
        tree[u].cover+=k;
        pushup(u);
    }
    else{
        if(l<tree[u<<1].r) modify(u<<1,l,r,k); 
        if(r>tree[u<<1|1].l) modify(u<<1|1,l,r,k);
        pushup(u);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        y[i]=y1,y[n+i]=y2;
        seg[m++]={x1,y1,y2,1};
        seg[m++]={x2,y1,y2,-1};
    }
    sort(y+1,y+m+1);
    sort(seg,seg+m);

    build(1,1,m);

    ll ans=0;
    modify(1,seg[0].y1,seg[0].y2,seg[0].state);
    for(int i=1;i<m;i++){
        ans+=tree[1].len*(seg[i].x-seg[i-1].x);
        modify(1,seg[i].y1,seg[i].y2,seg[i].state);
    }
    cout<<ans<<"\n";
    return 0;
}
矩形周长并
#include<bits/stdc++.h>
using namespace std;
int ls(int x){ return x<<1;  }   
int rs(int x){ return x<<1|1;}  
const int MAXN = 200005;
struct ScanLine {
    int l, r, h, inout;  //inout=1 下边, inout=-1 上边
    ScanLine() {}
    ScanLine(int a, int b, int c, int d) :l(a), r(b), h(c), inout(d) {}
}line[MAXN];
bool cmp(ScanLine &a, ScanLine &b) { 
    if(a.h==b.h) return a.inout>b.inout;
    return a.h<b.h; 
}   //y坐标排序

bool lbd[MAXN << 2], rbd[MAXN << 2];//标记这个结点的左右两个端点是否被覆盖(0表示没有,1表示有)
int num[MAXN << 2];    //这个区间有多少条独立的边
int Tag[MAXN << 2];    //标记这个结点是否有效 
int length[MAXN << 2]; //这个区间的有效宽度
void pushup(int p, int pl, int pr) {
    if (Tag[p]) {                 //结点的Tag为正,这个线段对计算宽度有效  
        lbd[p] = rbd[p] = 1;
        length[p] = pr - pl + 1;
        num[p] = 1;               //每条边有两个端点
    }
    else if (pl == pr) length[p]=num[p]=lbd[p]=rbd[p]=0;//叶子结点 
    else {     
        lbd[p] = lbd[ls(p)];      // 和左儿子共左端点
        rbd[p] = rbd[rs(p)];      //和右儿子共右端点
        length[p] = length[ls(p)] + length[rs(p)];
        num[p] = num[ls(p)] + num[rs(p)];
        if (lbd[rs(p)] && rbd[ls(p)]) num[p] -= 1;   //合并边
    }
}
void update(int L, int R, int io, int p, int pl, int pr) {
    if(L<=pl && pr<=R){    //完全覆盖
        Tag[p] += io;
        pushup(p, pl, pr);
        return;
    }
    int mid  = (pl + pr) >> 1;
    if (L<= mid) update(L, R, io, ls(p), pl, mid);
    if (mid < R) update(L, R, io, rs(p), mid+1, pr);
    pushup(p, pl, pr);
}
int main() {
    int n;
    while (~scanf("%d", &n)) {
        int cnt  = 0;
        int lbd = 10000, rbd = -10000;
        for (int i = 0; i < n; i++) {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);   //输入矩形
            lbd = min(lbd, x1);                      //横线最小x坐标
            rbd = max(rbd, x2);                      //横线最大x坐标
            line[++cnt] = ScanLine(x1, x2, y1, 1);   //给入边赋值
            line[++cnt] = ScanLine(x1, x2, y2, -1);  //给出边赋值
        }
        sort(line+1, line + cnt+1, cmp);           //排序。数据小,不用离散化 
        int ans = 0, last = 0;                     //last:上一次总区间被覆盖长度
        for (int i = 1; i <= cnt ; i++){           //扫描所有入边和出边
            if (line[i].l < line[i].r) 
                update(line[i].l, line[i].r-1, line[i].inout, 1, lbd, rbd-1);
            ans += num[1]*2 * (line[i + 1].h - line[i].h);  //竖线
            ans += abs(length[1] - last);            //横线
            last = length[1];                 
        }
        printf("%d\n", ans);
    }
    return 0;
}

可持久化线段树(主席树)

//区间内的第 k 小值
#include <bits/stdc++.h>
using namespace std ;
const int N = 200010;
int cnt = 0;        //用cnt标记可以使用的新结点
int a[N], b[N], root[N];
//a[]是原数组,b[]是排序后数组,root[i]记录第i棵线段树的根节点编号

struct node {
    int L, R, sum;  //L左儿子, R右儿子,sum[i]是结点i的权值
} tree[N<<5];    //需要开 nlogn空间 

int build(int pl, int pr) {
    int rt = ++ cnt;              //cnt为当前节点编号
    tree[rt].sum = 0;
    int mid=(pl+pr)>>1;
    if (pl < pr) {
        tree[rt].L = build(pl, mid);
        tree[rt].R = build(mid+1, pr);
    }
    return rt;  //返回当前节点的编号
}
int update(int pre, int pl, int pr, int x) {  //建一棵只有logn个结点的新线段树
    int rt = ++cnt;          //新的结点,下面动态开点
    tree[rt].L = tree[pre].L;//该结点的左右儿子初始化为前一棵树相同位置结点的左右儿子
    tree[rt].R = tree[pre].R;
    tree[rt].sum = tree[pre].sum + 1;  //插了1个数,在前一棵树的相同结点加1
    int mid = (pl+pr)>>1;
    if (pl < pr) {          //从根结点往下建logn个结点
        if (x <= mid)       //x出现在左子树,修改左子树
            tree[rt].L = update(tree[pre].L, pl, mid, x);
        else                //x出现在右子树,修改右子树
            tree[rt].R = update(tree[pre].R, mid+1, pr, x);
    }
    return rt;              //返回当前分配使用的新结点的编号
}

int query(int u, int v, int pl, int pr, int k) {   //查询区间[u,v]第k小
    if (pl == pr) return pl;  //到达叶子结点,找到第k小,pl是节点编号,答案是b[pl]
    int x = tree[tree[v].L].sum - tree[tree[u].L].sum;   //线段树相减
    int mid = (pl+pr)>>1;
    if (x >= k)     //左儿子数字大于等于k时,说明第k小的数字在左子树
        return query(tree[u].L, tree[v].L, pl, mid, k);
    else            //否则在右子树找第k-x小的数字
        return query(tree[u].R, tree[v].R, mid+1, pr, k-x);
}

int main() {
    int n, m;cin>>n>>m;
    for (int i = 1; i <= n; i ++) {
        cin>>a[i];
        b[i] = a[i];
    }
    sort(b+1, b+1+n);
    int size = unique(b+1, b+1+n)-b-1;
    for (int i = 1; i <= n; i ++) {
        int x = lower_bound(b+1, b+1+size, a[i]) - b;
        root[i] = update(root[i-1], 1, size, x);
    }
    while (m--) {
        int x, y, k;cin>>x>>y>>k;
        int t = query(root[x-1], root[y], 1, size, k);
        //第y棵线段树减第x-1棵线段树,就是区间[x,y]的线段树
        cout<<b[t]<<"\n";
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll;
const int N = 1e5+10;
int cas,cnt;
ll a[N];
int root[N];
int n,m;

struct node {
    int L, R;
    ll lazy,sum;
} tree[N<<5];    //需要开 nlogn空间 

void pushup(int u){
    tree[u].sum=tree[tree[u].L].sum+tree[tree[u].R].sum;
}

int build(int pl, int pr) {
    int rt = ++ cnt;              //cnt为当前节点编号
    tree[rt].L=tree[rt].R=tree[rt].lazy=tree[rt].sum=0;
    if(pl==pr){
        tree[rt].sum=a[pl];
        return rt;
    }
    int mid=(pl+pr)>>1;
    tree[rt].L = build(pl, mid);
    tree[rt].R = build(mid+1, pr);
    pushup(rt);
    return rt;  //返回当前节点的编号
}

int update(int pre, int pl, int pr, int l, int r, ll v) {  //建一棵只有logn个结点的新线段树
    int rt = ++cnt;
    tree[rt] = tree[pre];
    tree[rt].sum+=v*(r-l+1);
    if(l==pl&&r==pr){
        tree[rt].lazy += v;
        return rt;
    }
    int mid=(pl+pr)>>1;
    if(r<=mid) tree[rt].L = update(tree[pre].L,pl,mid,l,r,v);
    else if(l>mid) tree[rt].R = update(tree[pre].R,mid+1,pr,l,r,v);
    else{
        tree[rt].L = update(tree[pre].L,pl,mid,l,mid,v);
        tree[rt].R = update(tree[pre].R,mid+1,pr,mid+1,r,v);
    }
//    pushup(rt);
    return rt;              //返回当前分配使用的新结点的编号
}

//区间查询
ll query(int rt,int pl,int pr,int l,int r){
    if(pl>=l&&pr<=r) return tree[rt].sum;
    int mid=(pl+pr)>>1;
    ll res=tree[rt].lazy*(r-l+1);
    if(r<=mid) res+=query(tree[rt].L,pl,mid,l,r);
    else if(l>mid) res+=query(tree[rt].R,mid+1,pr,l,r);
    else{
        res+=query(tree[rt].L,pl,mid,l,mid);
        res+=query(tree[rt].R,mid+1,pr,mid+1,r);
    }
    return res;    //返回当前结点得到的信息
}

void solve(){
    if(cas++) cout<<"\n";
    cnt=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    root[0]=build(1,n);
    int time=0;
    while(m--){
        char op;cin>>op;
        if(op=='C'){
            int l,r;ll d;cin>>l>>r>>d;
            time++;
            root[time]=update(root[time-1],1,n,l,r,d);
        }
        else if(op=='Q'){
            int l,r;cin>>l>>r;
            cout<<query(root[time],1,n,l,r)<<"\n";
        }
        else if(op=='H'){
            int l,r,t;cin>>l>>r>>t;
            cout<<query(root[t],1,n,l,r)<<"\n";
        }
        else{
            int t;cin>>t;
            time=t;
        }
    }
}

int main() {
    while(cin>>n>>m)
    solve();
    return 0;
}

珂朵莉树(ODT)

推平一段区间

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;

struct node{
    int l,r;
    mutable ll v;
    node(int L,int R=-1,ll V=0):l(L), r(R), v(V) {}
    bool operator<(const node& o) const{
        return l < o.l;
    }
};
set<node> s;
int n,m;
ll seed,vmax;
ll a[N];

ll fpow(ll a,ll b,ll mod){
    if(mod==1) return 0;
    ll ans=1%mod;
    a%=mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

set<node>::iterator split(int pos){
    auto it=s.lower_bound(node(pos));
    if(it!=s.end() && it->l==pos) return it;
    --it;
    int L=it->l,R=it->r;
    ll V=it->v;
    s.erase(it);
    s.insert(node(L,pos-1,V));
    return s.insert(node(pos,R,V)).first;
}

//推平
void assign(int l, int r, ll val){
    auto itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert(node(l,r,val));
}

//区间加 
void add(int l,int r,ll val){
    auto itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl) itl->v+=val;
}

//区间第k小
ll _rank(int l,int r,int k){
    vector<pair<ll,int> >vp;
    auto itr=split(r+1),itl=split(l);
    vp.clear();
    for(;itl!=itr;++itl) vp.push_back({itl->v,itl->r-itl->l+1});
    sort(vp.begin(),vp.end());
    for(auto i:vp){
        k-=i.second;
        if(k<=0) return i.first;
    }
    return -1;
}

//区间幂次和
ll sum(int l,int r,ll ex,ll mod){
    auto itr=split(r+1),itl=split(l);
    ll res=0;
    for(;itl!=itr;++itl) 
        res=(res+(ll)(itl->r - itl->l + 1)*fpow(itl->v,ex,mod))%mod;
    return res;
}

ll rnd(){
    ll ret=seed;
    seed=(seed*7+13)%1000000007;
    return ret;
}

int main(){
    cin>>n>>m>>seed>>vmax;
    for(int i=1;i<=n;i++){
        a[i]=(rnd()%vmax)+1;
        s.insert(node(i,i,a[i]));
    }
    for(int i=1;i<=m;i++){
        int op=(rnd()%4)+1;
        int l=(rnd()%n)+1;
        int r=(rnd()%n)+1;
        if(l>r) swap(l,r);
        ll x,y;
        if(op==3) x=(rnd()%(r-l+1))+1;
        else x=(rnd()%vmax)+1;
        if(op==4) y=(rnd()%vmax)+1;

        if(op==1) add(l,r,x);
        else if(op==2) assign(l,r,x);
        else if(op==3) cout<<_rank(l,r,x)<<"\n";
        else cout<<sum(l,r,x,y)<<"\n";
    }
    return 0;
}

图论模板

最近公共祖先(LCA)

https://www.luogu.com.cn/problem/P3379

#include <bits/stdc++.h>
using namespace std;
const int N=500010;

int n,m,root; 
vector<int> g[N];
int depth[N],fa[N][20],lg[N];

void init(){
    //log2(i)+1
    for(int i=1;i<=n;i++){
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
}

void dfs(int u,int father){
    depth[u]=depth[father]+1;
    fa[u][0]=father;
    // 2^i祖先为2^i-1级祖先的2^i-1级祖先
    for(int i=1;(1<<i)<=depth[u];i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int v:g[u]){
        if(v==father) continue;
        dfs(v,u);
    }
}

int lca(int a,int b){
    if(depth[a]<depth[b]) swap(a,b);
    while(depth[a]>depth[b]){
        a=fa[a][lg[depth[a]-depth[b]]-1];
    }
    if(a==b) return a;
    for(int i=lg[depth[a]];i>=0;i--){
        if(fa[a][i]!=fa[b][i]){
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}

int main(){
    cin>>n>>m>>root;
    init();
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(root,0);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<"\n";
    }
    return 0;
}

最小生成树(MST)

Borůvka (Sollin) 算法

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MaxN = 5000 + 5, MaxM = 200000 + 5;

int N, M;
int U[MaxM], V[MaxM], W[MaxM];
bool used[MaxM];
int par[MaxN], Best[MaxN];

void init() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i)
        scanf("%d %d %d", &U[i], &V[i], &W[i]);
}

void init_dsu() {
    for (int i = 1; i <= N; ++i)
        par[i] = i;
}

int get_par(int x) {
    if (x == par[x]) return x;
    else return par[x] = get_par(par[x]);
}

inline bool Better(int x, int y) {
    if (y == 0) return true;
    if (W[x] != W[y]) return W[x] < W[y];
    return x < y;
}

void Boruvka() {
    init_dsu();

    int merged = 0, sum = 0;

    bool update = true;
    while (update) {
        update = false;
        memset(Best, 0, sizeof Best);

        for (int i = 1; i <= M; ++i) {
            if (used[i] == true) continue;
            int p = get_par(U[i]), q = get_par(V[i]);
            if (p == q) continue;

            if (Better(i, Best[p]) == true) Best[p] = i;
            if (Better(i, Best[q]) == true) Best[q] = i;
        }

        for (int i = 1; i <= N; ++i)
            if (Best[i] != 0 && used[Best[i]] == false) {
                update = true;
                merged++; sum += W[Best[i]];
                used[Best[i]] = true;
                par[get_par(U[Best[i]])] = get_par(V[Best[i]]);
            }
    }

    if (merged == N - 1) printf("%d\n", sum);
    else puts("orz");
}

int main() {
    init();
    Boruvka();
    return 0;
}

字符串

Trie树(字典树)

https://www.acwing.com/problem/content/837/

#include <bits/stdc++.h>
using namespace std;

struct Trie {
    int nex[100010][26], cnt;
    int exist[100010];  // 该结点结尾的字符串是否存在

    void insert(string s, int l) {  // 插入字符串
        int p = 0;
        for (int i = 0; i < l; i++) {
            int c = s[i] - 'a';
            if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有,就添加结点
            p = nex[p][c];
        }
        exist[p] ++;
    }
    int find(string s, int l) {  // 查找字符串
        int p = 0;
        for (int i = 0; i < l; i++) {
            int c = s[i] - 'a';
            if (!nex[p][c]) return 0;
            p = nex[p][c];
        }
        return exist[p];
    }
} t;

int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    char c;
    string s;
    while(n--) {
        cin>>c>>s;
        if(c=='I') t.insert(s,s.length());
        else cout<<t.find(s,s.length())<<"\n";
    } 
    return 0;
}

01Trie

struct Trie {
    int nex[N*32][2],cnt=0;

    void insert(int x) { 
        int p = 0;
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if (!nex[p][c]) nex[p][c] = ++cnt; 
            p = nex[p][c];
        }
    }
    int find(int x) {
        int p = 0,res = 0;
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if(nex[p][c^1]) p=nex[p][c^1],res|=(1<<i);
            else p=nex[p][c];
        }
        return res;
    }
} t;

字符串哈希

https://www.acwing.com/problem/content/description/843/

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull P = 131;
const ull N = 1e5+10;
ull powP[N],H[N];
int n,m;
char str[N];

void init(){
    powP[0]=1;
    for(int i=1;i<=n;i++){
        powP[i]=powP[i-1]*P;
    }
}

void calH(ull H[],char str[]){
    H[0]=str[0];
    for(int i=1;i<=n;i++){
        H[i]=H[i-1]*P+str[i];
    }
}

ull get(int l,int r){
    return H[r]-H[l-1]*powP[r-l+1];
}

int main(){
    cin>>n>>m;
    cin>>str+1;
    init();
    calH(H,str);
    while(m--){
        int l1,l2,r1,r2;
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

KMP算法

https://www.acwing.com/problem/content/description/833/

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int ne[N];

void getNext(string s,int len){
    int j=-1;
    ne[0]=-1;
    for(int i=1;i<len;i++){
        while(j!=-1&&s[i]!=s[j+1]){
            j=ne[j];
        }
        if(s[i]==s[j+1]) j++;
        ne[i]=j;
    }
}

int KMP(string text,string pattern){
    int n=text.length(),m=pattern.length();
    getNext(pattern,m);
    int ans=0,j=-1;
    for(int i=0;i<n;i++){
        while(j!=-1&&text[i]!=pattern[j+1]){
            j=ne[j];
        }
        if(text[i]==pattern[j+1]) j++;
        if(j==m-1) ans++,j=ne[j],printf("%d ", i-m+1);
    }
    return ans;
}

int main(){
    int n,m;
    string s1,s2;
    cin>>n>>s1>>m>>s2;
    getNext(s1,n);
    getNext(s2,m);
    KMP(s2,s1);
    return 0;
}

Manacher(马拉车)算法

最长回文子串 https://www.acwing.com/problem/content/1526/

#include <bits/stdc++.h>
using namespace std;

int Manacher(string s){
    string str="@#";
    for(int i=0;i<s.length();i++) str+=s[i],str+='#';
    vector<int> p(str.length(),0);
    /*
    mx表示某个回文串延伸在最右端半径的下标
    id表示这个回文子串最中间位置下标
    reslen表示对应在s中的最大子回文串的半径
    rescenter表示最大子回文串的中间位置
    */
    int mx=0,id=0,reslen=0,rescenter=0;
    for(int i=1;i<str.length();i++){
        p[i] = mx>i ? min(p[2*id-i],mx-i):1;
        while(str[i+p[i]]==str[i-p[i]]) p[i]++;
        if(mx<i+p[i]) mx=i+p[i],id=i;
        if(reslen<p[i]) reslen=p[i],rescenter=i;
    }
    return reslen-1;
} 

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    string s;getline(cin,s);
    cout<<Manacher(s)<<"\n"; 
    return 0;
}

后缀数组(SA)+++

https://www.luogu.com.cn/problem/P3809

https://www.acwing.com/problem/content/description/142/

后缀自动机 (SAM)+++

AC 自动机+++

动态规划

背包DP

01背包

int v,w; //v体积,w价值
int f[N];

void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&v,&w);
        for(int j=m;j>=v;j--){
            f[j]=max(f[j], f[j-v]+w);
        }
    }
    cout<<f[m]<<"\n";
}

完全背包

int v,w; //v体积,w价值
int f[N];

void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&v,&w);
        for(int j=v;j<=m;j++){
            f[j]=max(f[j],f[j-v]+w);
        }
    }
    cout<<f[m]<<"\n";
}

多重背包

int v,w,s; //v体积 w价值 s数量
int f[N];

void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v>>w>>s;
        for(int j=m;j>=v;j--){
            for(int k=1;k<=s&&k*v<=j;k++){
                f[j]=max(f[j],f[j-k*v]+w*k);
            }
        }
    }
    cout<<f[m]<<"\n";
}

多重背包(二进制优化)

int v,w,s;
int dp[N];
vector<pii> good;

void solve() {
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++){
        cin>>v>>w>>s;
        for(int k=1;k<=s;k<<=1){
            s-=k;
            good.push_back({v*k,w*k});
        }
        if(s>0) good.push_back({v*s,w*s});    
    }
    for(auto t:good) {
        for(int j=V; j>=t.X; j--) {
            dp[j]=max(dp[j],dp[j-t.X]+t.Y);
        }
    }
    cout<<dp[V]<<"\n";
}

多重背包(单调队列优化)

int v[N],w[N],s[N];//体积、价值和数量
int f[N],g[N];//g[]为f[i-1][],f[]为f[i][]

void solve(){
    int n,V;cin>>n>>V;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++) {
        memcpy(g,f,sizeof f);
        for(int j=0;j<v[i];j++){ //枚举余数 
            deque<int> q;
            for (int k=j;k<=V;k+=v[i]){
                f[k]=g[k];
                if(!q.empty()&&k-s[i]*v[i]>q.front()){
                    q.pop_front();
                }
                if(!q.empty()){
                    f[k]=max(f[k],g[q.front()]+(k-q.front())/v[i]*w[i]);
                }
                while(!q.empty()&&g[q.back()]-(q.back()-j)/v[i]*w[i]<=g[k]-(k-j)/v[i]*w[i]){
                    q.pop_back();
                }
                q.push_back(k);
            }
        }
    }
    cout<<f[V]<<"\n";
}

混合背包

  • 表示第 种物品只能用1次;
  • 表示第 种物品可以用无限次;
  • 表示第 种物品可以使用 次;
int v[N],w[N],s[N],dp[N];
struct good{
    int kind;
    int v,w;
};
vector<good> g;

void solve() {
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++){
        if(s[i]==-1||s[i]==0) g.push_back({s[i],v[i],w[i]});
        else{
            for(int k=1;k<=s[i];k<<=1){
                s[i]-=k;
                g.push_back({-1,v[i]*k,w[i]*k});
            }
            if(s[i]>0) g.push_back({-1,v[i]*s[i],w[i]*s[i]});
        }
    }
    for(auto t:g){
        if(t.kind==-1){
            for(int j=V;j>=t.v;j--){
                dp[j]=max(dp[j],dp[j-t.v]+t.w);
            }
        }
        else{
            for(int j=t.v;j<=V;j++){
                dp[j]=max(dp[j],dp[j-t.v]+t.w);
            }
        }    
    }
    cout<<dp[V]<<"\n";
}

二维费用的背包

int dp[N][N];

void solve(){
    int n,V,M;cin>>n>>V>>M;
    for(int i=1;i<=n;i++){
        int v,m,w;cin>>v>>m>>w;
        for(int j=V;j>=v;j--){
            for(int k=M;k>=m;k--){
                dp[j][k]=max(dp[j][k],dp[j-v][k-m]+w);
            }
        }
    }
    cout<<dp[V][M]<<"\n";
}

分组背包

int dp[N],v[N],w[N];
void solve(){
    int n,V;cin>>n>>V;
    for(int i=1;i<=n;i++){  //循环每一组
        int s;cin>>s;
        for(int j=1;j<=s;j++) cin>>v[j]>>w[j];
        for(int j=V;j>=0;j--){  //循环背包容量
            for(int k=1;k<=s;k++){  //循环该组的每一个物品
                if(j>=v[k]) dp[j]=max(dp[j],dp[j-v[k]]+w[k]); 
            }
        }
    }
    cout<<dp[V]<<"\n";
}

有依赖的背包

int n,m,root;
int v[N],w[N],dp[N][N];
vector<int> g[N];

void dfs(int u){
    for(int i=v[u];i<=m;i++) dp[u][i]=w[u];
    for(int x:g[u]){
        dfs(x);
        for(int j=m;j>=v[u];j--){
            for(int k=0;k<=j-v[u];k++){
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[x][k]);
            }
        }
    }
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int fa;
        cin>>v[i]>>w[i]>>fa;
        if(~fa) g[fa].push_back(i);
        else root=i;
    }
    dfs(root);
    cout<<dp[root][m]<<"\n";
}

背包问题求最大价值的方案数

int f[N];
ll cnt[N];

void solve(){
    int n,m;cin>>n>>m;
    for(int i=0;i<=m;i++) cnt[i]=1;
    for(int i=1;i<=n;i++){
        int v,w;cin>>v>>w;
        for(int j=m;j>=v;j--){
            int value=f[j-v]+w;
            if(value>f[j]){
                f[j]=value;
                cnt[j]=cnt[j-v];
            }
            else if(value==f[j]){
                cnt[j]+=cnt[j-v];
                cnt[j]%=mod;
            }
        }
    } 
    cout<<cnt[m]<<"\n";
}

背包问题求最大价值字典序最小的具体方案

int n,m;
int v[N],w[N],f[N][N];

void print(int i,int j){
    if(i==n+1) return;
    if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i]) {
        cout<<i<<" ";
        print(i+1,j-v[i]);
    }
    else print(i+1,j);
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=n;i>=1;i--){
        for(int j=0;j<=m;j++){
            if(j>=v[i]) f[i][j]=max(f[i+1][j],f[i+1][j-v[i]]+w[i]);
            else f[i][j]=f[i+1][j];
        }
    }
    print(1,m);
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-19 15:48
重庆工商大学_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-23 17:45
武汉商学院_2023
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-28 02:13
门头沟学院_2024
点赞 评论 收藏
转发
2 收藏 评论
分享

全站热榜

正在热议