自用模板积累（持续更新）

前言

命名规则

t: (全局)test cases测试组数/ (局部)temp 临时变量	sum: 和/前缀和
n: 序列长度	pre: previous 指向时间戳小的/后驱
m: 子序列长度	nxt: next 指向时间戳大的/前驱
len: length 字符串长度	s/e: start/end 开始/结束
cnt: count 计数	arr: array 序列
i/j/k…: 循环变量	s/t: 字符串/主串/模式串
idx: index 下标	m/mp: map 映射
p/q: position 指针	st: set 集合
l/r: left/right 左区间/右区间	stk: stack 栈
max/min: 最大/最小	que: queue 队列
vis: visite 是否访问	g: graph 图
sub: 差/差分	e/edge: 边
ans: answer 输出	v:verticle 结点
dis: distance 距离	inf: infinity 无穷大

顺序编号原则：a、b、c…
arra、arrb、arrc
命名冲突原则：重复末尾字母
字符串s、t，临时变量tt

常用预编译

//<iomanip><sstream><queue>
#define ll long long
#define rep(i,a,b) for(ll i=a;i<b;++i)//0开始
#define rev(i,a,b) for(ll i=a-1;i>=b;--i)
#define reb(i,a,b) for(ll i=a+1;i<b+1;++i)//1开始
#define red(i,a,b) for(ll i=a;i>b;--i)
#define inf 0x3f3f3f3f
#define clr(arr,val) memset(arr,val,sizeof arr)
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mid ((l+r)>>1)
#define sonl rt<<1,l,mid
#define sonr rt<<1|1,mid+1,r
#define tinfo ll rt,ll l,ll

零散技巧

31-__builtin_clz(n);//取对数
__builtin_popcount(n);//二进制1的个数

基础算法

快速排序

void qsort(ll l,ll r)
{
   
  if(l>=r) return;
  ll val=arr[l],p=l,q=r;
  while(p<q)
  {
   
    while(p<q&&arr[q]>val) q--;
    if(p<q){
   arr[p]=arr[q];p++;}
    while(p<q&&arr[p]<val) p++;
    if(p<q){
   arr[q]=arr[p];q--;}
  }
  arr[p]=val;
  qsort(l,p-1);
  //if(m-1>p) 求第m小数
  qsort(p+1,r);
}

并查集

rep(i,0,n) pre[i]=i;//********WARNING*********

无权+状态压缩

ll find(ll x){
   return x==pre[fx]?x:(pre[x]=find(pre[x]));}
void unionn(ll u,ll v){
   pre[find(u)]=find(v);}

带权+状态压缩

ll find(ll x) {
   
  if(x==pre[x]) return x;
  ll fx=pre[x];
  pre[x]=find(pre[x]);
  val[x]+=val[fx];
  return pre[t];
}
void unionn(ll a,ll b,ll value) {
   
  ll fa=pre[a],fb=pre[b];
  val[fa]=val[b]+value-val[a];
  pre[fa]=fb;
}

高精度（输入均为逆序字符串）

加/乘通用模板（记得修改成带返回值得）

void [add@mult](char aa[],char bb[]) {
   
  int a[maxn],b[maxn],c[maxn];
  clr(a,0);clr(b,0);clr(c,0);
  int cnta=strlen(aa),cntb=strlen(bb),cntc=[max(cnta,cntb)+1@cnta+cntb+1];
  rep(i,0,cnta) a[i]=aa[i]-'0';
  rep(i,0,cntb) b[i]=bb[i]-'0';
  [rep(i,0,cntc) c[i]=a[i]+b[i];@
  rep(i,0,cnta) rep(j,0,cntb) c[i+j]+=a[i]*b[j];]
  ll t=0;
  rep(i,0,cntc) {
   
    c[i]+=t;
    t=c[i]/10;
    c[i]%=10;
  }
  while(c[cntc]==0) cntc--;
  rep(i,0,cntc+1) cc[i]=c[i]+'0';
  cc[cntc+1]=0;
}

字符串

kmp

int j=pre[0]=-1,k=0;
//pre[i]为i位置（右开）最长公共前后缀
while(k<lent){
   
    while(j!=-1&&t[j]!=t[k]) j=pre[j];
    pre[++k]=++j;
    //if(t[++j]==t[++k]) pre[k]=pre[j]; 优化
    //else pre[k]=j;
}

j=k=0;
while(k<lens){
   
    while(j!=-1&&s[k]!=t[j]) j=pre[j];
    j++;k++;
    if(j==lent)
    {
   
    	cnt++;
    	j=pre[j];//重叠
    	//j=0;//不重叠
    }
}
if(j==lent) printf("%d\n",k-m+1);
//lent-nxt[lent]//最小循环节长度

manacher

char s[maxn];
char ma[maxn*2];
int mp[maxn*2];
int id,mx,n,len;
void manacher() {
   
  len=0;
  ma[len++]='!';
  ma[len++]='?';
  rep(i,0,n) {
   
    ma[len++]=s[i];
    ma[len++]='?';
  }
  id=mx=0;
  rep(i,0,len) {
   
    mp[i]=mx>i?min(mp[2*id-i],mx-i):1;
    while(ma[i+mp[i]]==ma[i-mp[i]]) mp[i]++;
    if(i+mp[i]>mx) {
   
      id=i;
      mx=i+mp[i];
    }
  }
}

  while(scanf("%s",s)==1) {
   
    n=strlen(s);
    manacher();
    int maxlen=1;
    for(int i=0; i<len; i++) maxlen=max(maxlen,mp[i]-1);
    //长度：mp[i]-1//起始位置：(i-mp[i])>>1
    printf("%d\n",maxlen);
  }

图论

二分图最大匹配（Hungary）

int n,m,k;
bool g[maxn][maxn],vis[maxn];
int lnk[maxn];

bool dfs(int u) {
    //可否更改
  rep(i,0,m) {
   
    if(g[u][i]&&!vis[i]) {
   
      vis[i]=true;
      if(lnk[i]==-1||dfs(lnk[i])) {
   
        lnk[i]=u;
        return true;
      }
    }
  }
  return false;
}

  int ans=0;
  memset(lnk,-1,m*sizeof(int));
  rep(i,0,n) {
   
    memset(vis,0,m*sizeof(bool));
    if(dfs(i)) ans++;
  }
  return ans;

最短路径

Dij

邻接矩阵

ll n,s,e;
ll dis[maxn],g[maxn][maxn];
bool vis[maxn];
//g[ta][tb]=g[tb][ta]=min(g[ta][tb],tc);
  dis[s]=0;
  while(s!=e)
  {
   
    ll mindis=inf,idx;
    vis[s]=true;
    rep(i,0,n)
    {
   
      dis[i]=min(dis[i],dis[s]+g[s][i]);
      if(!vis[i]&&dis[i]<mindis) mindis=dis[idx=i];
    }
    if(mindis==inf) break;
    s=idx;
  }
  cout<<dis[e]<<endl;

堆优化+前向星

ll n,m;
ll dis[maxn],hd[maxn];
bool vis[maxn];
ll cnt;
ll to[maxm],w[maxm],nxt[maxm];
ll ta,tb,tc,s,e;
struct node {
   
  ll s,w;
  bool operator<(const node &a)const {
   
    return a.w<w; //与condition()同步
  }
};
priority_queue<node> que;

  //init
  memset(dis,inf,sizeof dis);
  memset(vis,0,sizeof vis);
  memset(hd,0,sizeof hd)//*******WARNING********
  cnt=0;
  //in
  cin>>n>>m;
  rep(i,0,m) {
   
    cin>>ta>>tb>>tc;

    w[++cnt]=tc;
    to[cnt]=tb;
    nxt[cnt]=hd[ta];
    hd[ta]=cnt;
  }
  cin>>s>>e;
  //dij
  dis[s]=0;
  que.push(node{
   s,0});
  while(!que.empty()) {
   
    node t=que.top();
    que.pop();
    if(vis[t.s]) continue;
    vis[t.s]=true;
    for(ll i=hd[t.s]; i; i=nxt[i]) {
   
      if(dis[t.s]+w[i]<dis[to[i]])
        //if(condition(stucture(dis[pnt],w[i]),dis[to[i]])) <条件>的<结构> ex. min(dis[pnt],w[i])>dis[to[i]] 最大的路径的边的最小值
      {
   
        dis[to[i]]=dis[t.s]+w[i];
        que.push(node{
   to[i],dis[to[i]]});
      }
    }
  }
  //out
  cout<<dis[e]<<endl;

树

双向链表遍历

ll n,m;
vector<ll> nxt[maxn];
bool vis[maxn];
ll ans;
void dfs(ll p) {
   
  if(vis[p]) return;
  vis[p]=true;
  bool found=false;//有无子节点
  rep(j,0,nxt[p].size()) {
   
    if(!vis[nxt[p][j]]) found=true;
    dfs(nxt[p][j]);
  }
  if(!found) ans++;
}
  scanf("%lld%lld",&n);
  rep(i,0,n-1) {
   
    ll ta,tb;
    scanf("%lld%lld",&ta,&tb);
    nxt[ta].push_back(tb);
    nxt[tb].push_back(ta);
  }
  dfs(1);
  printf("%lld\n",ans);

二叉树

先序遍历+中序遍历->后序遍历（dfs）

int n;
int pre[maxn];
int in[maxn];
bool head;
void build(int la,int ra,int lb,int rb) {
   
  if(la==ra) return;
  if(la+1==ra) {
   
    if(head) {
   
      printf("%d",pre[la]);
      head=false;
    } else printf(" %d",pre[la]);
    return;
  }
  int p=lb;
  while(in[p]!=pre[la]&&p<rb)p++;
  build(la+1,la+1+p-lb,lb,p);
  build(la+1+p-lb,ra,p+1,rb);
  if(head) {
   
    printf("%d",pre[la]);
    head=false;
  } else printf(" %d",pre[la]);
}

  while(~scanf("%d",&n)) {
   
    head=true;
    rep(i,0,n) scanf("%d",&pre[i]);
    rep(i,0,n) scanf("%d",&in[i]);
    build(0,n,0,n);
    puts("");
  }

查询/修改

树状数组

ll tree[maxn];

ll lowbit(int x) {
   
  return x&(-x);
}
void update(ll x) {
   
  while(x<=n) {
   
    tree[x]++;
    x+=lowbit(x);
  }
}
ll getsum(ll x) {
   
  ll ans=0;
  while(x) {
   
    ans+=tree[x];
    x-=lowbit(x);
  }
  return ans;
}
ll qury(ll l,ll r) {
   
  return getsum(r)-getsum(l-1);
}

线段树

ll tree[maxn<<2];
ll arr[maxn];
ll n;
void pushup(ll rt) {
   
  //要维护操作
  tree[rt]=operation(tree[rt<<1],tree[rt<<1|1]);
}
void build(tinfo) {
   
  if(l==r) {
   
    tree[rt]=arr[l];
    return;
  }
  build(sonl);
  build(sonr);
  pushup(rt);
}
void update(tinfo,ll p,ll w) {
   
  if(l==r) {
   
  	//更新操作
    tree[rt] operation=w;
    return ;
  } else if(p>mid) update(sonr,p,w);
  else update(sonl,p,w);
  pushup(rt);
}
ll qury(ll p,ll l,ll r,ll tl,ll tr) {
   
  if(tl<=l&&tr>=r) return tree[rt];
  ll ans;
  if(tr>mid) ans operation=qury(sonr,tl,tr);
  if(tl<=mid) ans operation=qury(sonl,tl,tr);
  return ans;
}

RMQ(ST)

ll n,q;
ll arr[maxn];
ll dp[20][maxn];
inline ll log(ll n) {
   
  return 31-__builtin_clz(n);
}
void prep() {
   
  rep(i,0,n)
  dp[0][i]=arr[i];
  ll logen=log(n);
  reb(i,0,logen)
  rep(j,0,n-(1<<i-1))
  dp[i][j]=max(dp[i-1][j],dp[i-1][j+(1<<i-1)]);
}
ll query(ll l,ll r) {
   
  ll logen=log(r-l);
  return max(dp[logen][l],dp[logen][r-(1<<logen)]);
}
  scanf("%lld%lld",&n,&q);
  rep(i,0,n)
  scanf("%lld",&arr[i]);
  prep();
  while(q--) {
   
// init();
    ll l,r;
    scanf("%lld%lld",&l,&r);
    printf("%lld\n",query(l-1,r);
  }
  return 0;