This-Is-A-Blog

My Templates

2020-11-05 22:03:48


My Templates

蒟蒻11.5到11.6写的模板在这里了QAQ。

就是分享模板吧,当然如果有dalao可以找到我的bug也是不错的。

提及的题号是用于检测模板的题目。


程序构架

一般模板

注意是否需要读入负数

快读(不带负)

#include<cstdio>
#include<iostream>
#define il inline
#define rg register
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

int main()
{
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);

    return 0;
}

快读(带负)

P1001 A+B Problem

#include<cstdio>
#include<iostream>
#define il inline
#define rg register
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    bool f=false;
    while((c=getchar())<'0' || c>'9')   if(c=='-')  f=true;
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
    if(f)   x=-x;
}

template <typename T> void Wri(T x)
{
    if(x > 9)   Wri(x/10);
    putchar(x%10^48);
}

template <typename T> void Oput(T x)
{
    if(x < 0)   putchar('-'), x=-x;
    Wri(x);
}//快写一定要和快读判负一起修改

int main()
{
    //  freopen(".in", "r", stdin);
    //  freopen(".out", "w", stdout);

    return 0;
}

基础算法

二分

二分查找

P2249 【深基13.例1】查找

这种写法l刚好落在交界线右侧,r落在左侧。

il int Binary(int x)
{
    int l=1, r=n;
    while(l <= r)
    {
        int mid = (l+r)>>1;
        if(a[mid]<x)    l=mid+1;    //实现lower_bound
        else    r=mid-1;
    }
    return l;
}

二分答案

P1182 数列分段 Section II

其实是另一种写法

il LL Binary(LL l, LL r)
{
    while(l != r)
    {
        LL mid = (l&r)+((l^r)>>1);
        if(check(mid))  r=mid;
        else    l=mid+1;
    }
    return l;
}

排序

快排

P1177 【模板】快速排序

void qsort(int l, int r)
{
    int i=l, j=r, mid=a[rand()%(r-l+1)+l];
    do
    {
        while(a[i]<mid) ++i;
        while(a[j]>mid) --j;
        if(i<=j)
        {
            swap(a[i], a[j]);
            ++i, --j;
        }
    }while(i<=j);
    if(i<r) qsort(i, r);
    if(j>l) qsort(l, j);
}

第k大数:

P1923 【深基9.例4】求第 k 小的数

void kth_element(int l, int r, int k)
{
    int i=l, j=r, mid=a[(l+r>>1)];
    do
    {
        while(a[i]<mid) ++i;
        while(a[j]>mid) --j;
        if(i<=j)
        {
            swap(a[i], a[j]);
            ++i, --j;
        }
    }while(i<=j);
    if(k<=j)    kth_element(l, j, k);
    else    if(k>=i)    kth_element(i, r, k);
}

归并

P1177 【模板】快速排序

int t[MAXN];

void msort(int l, int r)
{
    if(l == r)  return ;
    int mid=(l+r)>>1, i=l, j=mid+1, k=l;
    msort(l, mid);
    msort(mid+1, r);
    while(i<=mid && j<=r)
    {
        if(a[i]<a[j])   t[k++] = a[i++];
        else    t[k++] = a[j++];
    }
    while(i<=mid)   t[k++] = a[i++];
    while(j<=r) t[k++] = a[j++];
    for(rg int m=l ; m<=r ; ++m)
        a[m] = t[m];
}

归并求逆序对:

P1908 逆序对

LL ans; //注意long long

int t[MAXN];

void msort(int l, int r)
{
    if(l == r)  return;
    int mid=(l+r)>>1, i=l, j=mid+1, k=l;
    msort(l, mid);
    msort(mid+1, r);
    while(i<=mid && j<=r)
    {
        if(a[i]<=a[j])  t[k++] = a[i++];
        else    t[k++] = a[j++], ans += mid-i+1;
    }
    while(i<=mid)   t[k++] = a[i++];
    while(j<=r) t[k++] = a[j++];
    for(rg int m=l ; m<=r ; ++m)
        a[m] = t[m];
}

倍增

ST表

P3865 【模板】ST表

#define MAXN 100010
#define LOGN 17

int n, m;
int a[MAXN];
int Log[MAXN];
int st[MAXN][LOGN+1];   //数组开够

il void get_Log()
{
    Log[0] = -1;
    for(rg int i=1 ; i<=n ; ++i)
        Log[i] = Log[i>>1] + 1;
}

il void prepare()
{
    for(rg int i=1 ; i<=n ; ++i)
        st[i][0] = a[i];
    for(rg int i=1 ; i<=Log[n] ; ++i)
        for(rg int j=1 ; j<=n&&(j+(1<<i-1))<=n ; ++j)//注意这个条件:会RE
            st[j][i] = max(st[j][i-1], st[j+(1<<i-1)][i-1]);
}

il int query(int l, int r)
{
    int t = Log[r-l+1];
    return max(st[l][t], st[r-(1<<t)+1][t]);
}

int main()
{

    Iput(n), Iput(m);
    get_Log();  //线段树建树同理
    for(rg int i=1 ; i<=n ; ++i)
        Iput(a[i]);
    prepare();  //线段树建树同理
    for(rg int i=1 ; i<=m ; ++i)
    {
        int l, r;
        Iput(l), Iput(r);
        Oput(query(l, r));
        putchar('\n');
    }

    return 0;
}

高精度

数据结构

链表

P1996 约瑟夫问题

删除操作

r[l[p]] = r[p];
l[r[p]] = l[p];

队列

循环队列

#define MAXQ (1<<...)
int q[MAXQ], l=1, r;

q[++r & MAXQ-1] = ...
q[l++ & MAXQ-1] = ...

q[--l & MAXQ-1] = ...

单调队列

for(rg int i=1 ; i<=n ; ++i)    //注意n的取值
{
    if(l<=r && q[l]<i-m)    ++l;    //注意m的取值
    ...
    while(l<=r && cmp(f(q[r]), f(i)))   --r;
    q[++r] = i;
}

优先队列(其实是堆 //STL香

priority_queue <Type> q;    //默认大根堆

STL见上

对顶堆

P1168 中位数

priority_queue <int> bigq, smlq;

int main()
{

    int n;
    Iput(n);
    for(rg int i=1 ; i<=n ; i++)
    {
        int t;
        Iput(t);
        if(i&1)
        {
            smlq.push(-t);
            bigq.push(-smlq.top());
            smlq.pop();
            Oput(bigq.top());
            putchar('\n');
        }
        else
        {
            bigq.push(t);
            smlq.push(-bigq.top());
            bigq.pop();
        }
    }

    return 0;
}
//总之插入操作要先插入另一个堆再弹出top插入这一个堆(无视常数

并查集

P3367 【模板】并查集

普通并查集

#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 10010
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

int n, m;

int pre[MAXN];

il void ini_f(int n)
{
    for(rg int i=1 ; i<=n ; ++i)
        pre[i] = i;
}

int find_f(int x)
{
    if(pre[x] == x) return x;
    return find_f(pre[x]);
}

il void union_f(int u, int v)
{
    int fu = find_f(u), fv = find_f(v);
    if(fu != fv)    pre[fu] = fv;
}

il bool judge_f(int u, int v)
{
    return find_f(u) == find_f(v);
}

int main()
{

    Iput(n), Iput(m);
    ini_f(n);
    for(rg int i=1 ; i<=m ; ++i)
    {
        int op, x, y;
        Iput(op), Iput(x), Iput(y);
        if(op == 1)
        {
            union_f(x, y);
        }
        else
        {
            putchar(judge_f(x, y) ? 'Y' : 'N');
            putchar('\n');
        }
    }

    return 0;
}

自己口糊的按秩合并+路径压缩

#include<cstdio>
#include<iostream>
#include<cstring> 
#define il inline
#define rg register
#define MAXN 10010
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

int n, m;

int pre[MAXN];

il void ini_f()
{
    memset(pre, -1, sizeof pre);
}

int find_f(int x)
{
    if(pre[x] < 0)  return x;
    return pre[x] = find_f(pre[x]);
}

il void union_f(int a, int b)
{
    int fa = find_f(a), fb = find_f(b);
    if(fa == fb)    return ;
    if(pre[fa] < pre[fb])   pre[fa] += pre[fb], pre[fb] = fa;
    else    pre[fb] += pre[fa], pre[fa] = fb;
}

il bool judge_f(int u, int v)
{
    return find_f(u) == find_f(v);
}

int main()
{

    Iput(n), Iput(m);
    ini_f();    //注意
    for(rg int i=1 ; i<=m ; ++i)
    {
        int op, x, y;
        Iput(op), Iput(x), Iput(y);
        if(op == 1)
        {
            union_f(x, y);
        }
        else
        {
            putchar(judge_f(x, y) ? 'Y' : 'N');
            putchar('\n');
        }
    }

    return 0;
}

树状数组

普通板子

struct TreeArr {
    int c[MAXN];

    il void add(int pos, int v)
    {
        for(rg int i=pos ; i<=n ; i+=i&-i)
            c[i] += v;
    }

    il int ask(int pos)
    {
        int ret = 0;
        for(rg int i=pos ; i ; i-=i&-i)
            ret += c[i];
        return ret;
    }
}ta;

瞎搞平衡树:

P3369 【模板】普通平衡树

#include<cstdio>
#include<iostream>
#include<algorithm>
#define il inline
#define rg register
#define MAXN 100010
#define ENDL putchar('\n')
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    bool f=false;
    while((c=getchar())<'0' || c>'9')   if(c=='-')  f=true;//这个板子gg了好多次都是因为快读判负
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
    if(f)   x=-x;
}

template <typename T> void Wri(T x)
{
    if(x > 9)   Wri(x/10);
    putchar(x%10^48);
}

template <typename T> void Oput(T x)
{
    if(x < 0)   putchar('-'), x=-x;
    Wri(x);
}//快写一定要和快读判负一起修改

int n;
struct Qs {
    int op, x;
}q[MAXN];

int lsh[MAXN], top;

struct TreeArr {
    int c[MAXN];

    il void add(int pos)
    {
        for(rg int i=pos ; i<=top ; i+=i&-i)
            ++c[i];
    }

    il void del(int pos)
    {
        for(rg int i=pos ; i<=top ; i+=i&-i)
            --c[i];
    }

    il int ask(int pos)
    {
        int ret = 0;
        for(rg int i=pos ; i ; i-=i&-i)
            ret += c[i];
        return ret;
    }

    il int kth(int k)
    {
        int p = 0;
        for(rg int i=17 ; ~i ; --i)
        {
            p += 1<<i;
            if(p>top || c[p]>=k)    //注意c[p](不是c[i]..)
                p -= 1<<i;
            else
                k -= c[p];
        }
        return p+1;
    }

    il int lft(int x)
    {
        return kth(ask(x-1));
    }

    il int rit(int x)
    {
        return kth(ask(x)+1);
    }
}ta;

int main()
{

    Iput(n);
    for(rg int i=1 ; i<=n ; ++i)
        Iput(q[i].op), Iput(q[i].x), lsh[i] = q[i].x;
    sort(lsh+1, lsh+n+1);
    top = unique(lsh+1, lsh+n+1) - lsh - 1;
    for(rg int i=1 ; i<=n ; ++i)
    {
        int op=q[i].op, x=q[i].x;
        if(op != 4) x = lower_bound(lsh+1, lsh+top+1, x) - lsh;
        if(op == 1)
        {
            ta.add(x);
        }
        else if(op == 2)
        {
            ta.del(x);
        }
        else if(op == 3)
        {
            Oput(ta.ask(x-1)+1);
            ENDL;
        }
        else if(op == 4)
        {
            Oput(lsh[ta.kth(x)]);
            ENDL;
        }
        else if(op == 5)
        {
            Oput(lsh[ta.lft(x)]);
            ENDL;
        }
        else
        {
            Oput(lsh[ta.rit(x)]);
            ENDL;
        }
    }

    return 0;
}

线段树

普通线段树

P3373 【模板】线段树 2

#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 100010
using namespace std;
typedef long long LL;   //注意

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

int n, m, p;
LL a[MAXN];

il void Mod(LL &a)
{
    if(a>=p)    a%=p;   //注意:最好不要用减
}

il void add(LL &a, LL b)
{
    a += b;
    Mod(a);
}

il void mul(LL &a, LL b)
{
    a *= b;
    Mod(a);
}

struct SGtree {
    #define MID int mid=(l+r)>>1
    #define L ls(k),l,mid
    #define R rs(k),mid+1,r

    struct Node {
        LL v, la, lm;
    }t[MAXN<<2];

    il int ls(int k)    {return k<<1;}
    il int rs(int k)    {return k<<1|1;}

    il void pu(int k)
    {
        t[k].v = t[ls(k)].v  +t[rs(k)].v;
        Mod(t[k].v);
    }

    void build(int k, int l, int r)
    {
        t[k].la = 0;
        t[k].lm = 1;
        if(l == r)
        {
            t[k].v = a[l];
            return ;
        }
        MID;
        build(L);
        build(R);
        pu(k);
    }

    il void fa(int k, int l, int r, LL v)
    {
        add(t[k].v, v*(r-l+1));
        add(t[k].la, v);
    }

    il void fm(int k, LL v)
    {
        mul(t[k].v, v);
        mul(t[k].la, v);
        mul(t[k].lm, v);
    }

    il void pd(int k, int l, int mid, int r)
    {
        fm(ls(k), t[k].lm);
        fm(rs(k), t[k].lm);
        fa(L, t[k].la);
        fa(R, t[k].la);
        t[k].la = 0;
        t[k].lm = 1;
    }

    void modify_a(int k, int l, int r, int li, int ri, LL v)
    {
        if(li<=l && r<=ri)  return fa(k, l, r, v);
        MID;
        pd(k, l, mid, r);
        if(li<=mid) modify_a(L, li, ri, v);
        if(mid<ri)  modify_a(R, li, ri, v);
        pu(k);
    }

    void modify_m(int k, int l, int r, int li, int ri, LL v)
    {
        if(li<=l && r<=ri)  return fm(k, v);
        MID;
        pd(k, l, mid, r);
        if(li<=mid) modify_m(L, li, ri, v);
        if(mid<ri)  modify_m(R, li, ri, v);
        pu(k);
    }

    LL query(int k, int l, int r, int li, int ri)
    {
        if(li<=l && r<=ri)  return t[k].v;
        MID;
        LL ret=0;
        pd(k, l, mid, r);
        if(li<=mid) add(ret, query(L, li, ri));
        if(mid<ri)  add(ret, query(R, li, ri));
        return ret;
    }
}sg;

int main()
{

    Iput(n), Iput(m), Iput(p);
    for(rg int i=1 ; i<=n ; ++i)
        Iput(a[i]);
    sg.build(1, 1, n);
    for(rg int i=1 ; i<=m ; ++i)
    {
        int op, x, y, k;
        Iput(op), Iput(x), Iput(y);
        if(op == 1)
        {
            Iput(k);
            sg.modify_m(1, 1, n, x, y, k);
        }
        else if(op == 2)
        {
            Iput(k);
            sg.modify_a(1, 1, n, x, y, k);
        }
        else
        {
            Oput(sg.query(1, 1, n, x, y));
            putchar('\n');
        }
    }

    return 0;
}

扫描线

zkw线段树

P3374 【模板】树状数组 1

//记得加M啊
struct ZKW {
    LL t[MAXN<<3];
    int M;

    il void pu(int k)
    {
        t[k] = t[k<<1] + t[k<<1|1];
    }

    il void build()
    {
        for(M=1 ; M<n+2 ; M<<=1);
        for(rg int i=M+1 ; i<=M+n ; ++i)
            Iput(t[i]);
        for(rg int i=M ; i ; --i)
            pu(i);
    }

    il void modify(int pos, LL v)
    {
        for(rg int i=M+pos ; i ; i>>=1)
            t[i] += v;
    }

    il LL query(int l, int r)
    {
        LL ret = 0;
        for(rg int i=M+l-1, j=M+r+1 ; i^j^1 ; i>>=1, j>>=1)
        {
            if(~i&1)    ret += t[i^1];
            if(j&1)     ret += t[j^1];
        }
        return ret;
    }
}sg;

分块

P2357 守墓人

#include<cstdio>
#include<iostream>
#include<cmath>
#define il inline
#define rg register
#define int long long
#define MAXN 200010
#define RTN 500
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    bool f=false;
    while((c=getchar())<'0' || c>'9')   if(c=='-')  f=true;
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
    if(f)   x=-x;
}

template <typename T> void Wri(T x)
{
    if(x > 9)   Wri(x/10);
    putchar(x%10^48);
}

template <typename T> il void Oput(T x)
{
    if(x < 0)   putchar('-'), x=-x;
    Wri(x);
}

int n, m, rtn;
int a[MAXN], lazy[RTN], pos[MAXN], sum[RTN];

il int L(int k)
{
    return (pos[k]-1)*rtn+1;
}

il int R(int k)
{
    return pos[k]*rtn;
}

il void change(int l, int r, int v)
{
    for(rg int i=l, top=min(r, R(l)) ; i<=top ; ++i)    a[i]+=v, sum[pos[i]]+=v;
    for(rg int i=pos[l]+1 ; i<=pos[r]-1 ; ++i)  lazy[i] += v;
    if(pos[l] != pos[r])
        for(rg int i=L(r) ; i<=r ; ++i)
            a[i]+=v, sum[pos[i]]+=v;
}

il int query(int l, int r)
{
    int ret = 0;
    for(rg int i=l, top=min(r, R(l)) ; i<=top ; ++i)    ret += a[i]+lazy[pos[i]];
    for(rg int i=pos[l]+1 ; i<=pos[r]-1 ; ++i)  ret += sum[i]+rtn*lazy[i];
    if(pos[l] != pos[r])
        for(rg int i=L(r) ; i<=r ; ++i)
            ret += a[i]+lazy[pos[i]];
    return ret;
}

signed main()
{

    Iput(n), Iput(m);
    rtn = sqrt(n);
    for(rg int i=1 ; i<=n ; ++i)
    {
        Iput(a[i]);
        pos[i] = (i-1)/rtn+1;
        sum[pos[i]] += a[i];
    }
    for(rg int i=1 ; i<=m ; ++i)
    {
        int op, l, r, k;
        Iput(op);
        if(op == 1)
        {
            Iput(l), Iput(r), Iput(k);
            change(l, r, k);
        }
        else if(op == 2)
        {
            Iput(k);
            a[1] += k;
            sum[1] += k;
        }
        else if(op == 3)
        {
            Iput(k);
            a[1] -= k;
            sum[1] -= k;
        }
        else if(op == 4)
        {
            Iput(l), Iput(r);
            Oput(query(l, r));
            putchar('\n');
        }
        else if(op == 5)
        {
            Oput(a[1]+lazy[1]);
            putchar('\n');
        }
    }

    return 0;
}

图论

最短路

Floyd

P5905 【模板】Johnson 全源最短路(n^3 68分?)

    for(rg int i=1 ; i<=n ; ++i)
        for(rg int j=1 ; j<=n ; ++j)
            dis[i][j] = INF;
    for(rg int i=1 ; i<=n ; ++i)
        dis[i][i] = 0;
    for(rg int i=1 ; i<=m ; ++i)
    {
        int u, v, w;
        Iput(u), Iput(v), Iput(w);
        Min(dis[u][v], w);
    }
    for(rg int k=1 ; k<=n ; ++k)
        for(rg int i=1 ; i<=n ; ++i)
            for(rg int j=1 ; j<=n ; ++j)
            {
                if(dis[i][k]==INF || dis[k][j]==INF)    continue;
                Min(dis[i][j], dis[i][k]+dis[k][j]);
            }
    for(rg int i=1 ; i<=n ; ++i)    //负环
        if(dis[i][i] < 0)
        {
            Oput(-1);
            return 0;
        }   

SPFA(+带容错SLF)

P3371 【模板】单源最短路径(弱化版)

LL dis[MAXN];
#define MAXQ (1<<14)
int q[MAXQ], l=MAXN<<1, r=l-1;
bool in_q[MAXN];

il void spfa()
{
    for(rg int i=1 ; i<=n ; ++i)
        dis[i] = 0x7fffffff;
    dis[s] = 0;
    q[++r & MAXQ-1] = s;
    in_q[s] = true;
    while(l <= r)
    {
        int u = q[l++ & MAXQ-1];
        in_q[u] = false;
        for(rg int i=head[u] ; i ; i=e[i].nex)
        {
            int v = e[i].x, w = e[i].w;
            if(dis[v] > dis[u]+w)
            {
                dis[v] = dis[u]+w;
                if(!in_q[v])
                {
                    if(dis[v] > dis[q[l & MAXQ-1]]+1)   q[++r & MAXQ-1] = v;
                    else    q[--l & MAXQ-1] = v;
                    in_q[v] = true;
                }
            }
        }
    }
}

Dijkstra

P4779 【模板】单源最短路径(标准版)

int dis[MAXN];
priority_queue <pair<int, int> > q;
bool vis[MAXN];

il void dijkstra()
{
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    q.push(make_pair(0, s));
    while(q.size())
    {
        int u = q.top().second;
        q.pop();
        if(vis[u])  continue;
        vis[u] = true;
        for(rg int i=head[u] ; i ; i=e[i].nex)
        {
            int v = e[i].x, w = e[i].w;
            if(dis[v] > dis[u]+w)
            {
                dis[v] = dis[u]+w;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}

Johnson

P5905 【模板】Johnson 全源最短路

#include<cstdio>
#include<iostream>
#include<queue>
#define il inline
#define rg register
#define MAXN 3010
#define MAXM 6010
#define INF 1000000000
using namespace std;
typedef long long LL;

template <typename T> il void Iput(T &x)
{
    char c;
    bool f=false;
    while((c=getchar())<'0' || c>'9')   if(c=='-')  f=true;
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
    if(f)   x = -x;
}

template <typename T> void Wri(T x)
{
    if(x > 9)   Wri(x/10);
    putchar(x%10^48);
}

template <typename T> il void Oput(T x)
{
    if(x < 0)   putchar('-'), x=-x;
    Wri(x);
}

struct Edge {
    int x, nex, w;
}e[MAXN+MAXM];

int head[MAXN], tote;

il void ae(int u, int v, int w)
{
    e[++tote].x = v;
    e[tote].w = w;
    e[tote].nex = head[u];
    head[u] = tote;
}

int n, m;

int h[MAXN];
#define MAXQ (1<<14)
int qs[MAXQ], l=MAXQ<<1, r=l-1;
bool in_q[MAXN];
int len[MAXN];

il bool spfa()
{
    for(rg int i=1 ; i<=n ; ++i)
        h[i] = INF;
    h[0] = 0;
    qs[++r & MAXQ-1] = 0;
    in_q[0] = true;
    while(l <= r)
    {
        int u = qs[l++ & MAXQ-1];
        in_q[u] = false;
        for(rg int i=head[u] ; i ; i=e[i].nex)
        {
            int v = e[i].x, w = e[i].w;
            if(h[v] > h[u]+w)
            {
                len[v] = len[u] + 1;
                if(len[v] > n)  return true;    //注意应该>n,因为建了一个超级原点
                h[v] = h[u]+w;
                if(!in_q[v])
                {
                    if(h[v] > h[qs[l & MAXQ-1]]+1)  qs[++r & MAXQ-1] = v;
                    else    qs[--l & MAXQ-1] = v;
                    in_q[v] = true;
                }
            }
        }
    }
    return false;
}

priority_queue <pair<int, int> > q;
int dis[MAXN];
bool vis[MAXN];

il void dijkstra(int s)
{
    for(rg int i=1 ; i<=n ; ++i)
    {
        dis[i] = INF;
        vis[i] = 0;
    }
    dis[s] = 0;
    q.push(make_pair(0, s));
    while(q.size())
    {
        int u = q.top().second;
        q.pop();
        if(vis[u])  continue;
        vis[u] = true;
        for(rg int i=head[u] ; i ; i=e[i].nex)
        {
            int v = e[i].x, w=e[i].w;
            if(dis[v] > dis[u]+w)
            {
                dis[v] = dis[u]+w;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}

int main()
{

    Iput(n), Iput(m);
    for(rg int i=1 ; i<=m ; ++i)
    {
        int u, v, w;
        Iput(u), Iput(v), Iput(w);
        ae(u, v, w);
    }
    for(rg int i=1 ; i<=n ; ++i)
        ae(0, i, 0);
    if(spfa())
    {
        putchar('-');
        putchar('1');
        return 0;
    }
    for(rg int u=1 ; u<=n ; ++u)
        for(rg int i=head[u] ; i ; i=e[i].nex)
            e[i].w += h[u]-h[e[i].x];
    for(rg int u=1 ; u<=n ; ++u)
    {
        LL ans = 0;
        dijkstra(u);
        for(rg int i=1 ; i<=n ; ++i)
            ans += (LL)i*(dis[i]==INF ? INF : dis[i]-h[u]+h[i]);
        Oput(ans);
        putchar('\n');
    }

    return 0;
}

差分约束

最小生成树

P3366 【模板】最小生成树

Prim

#include<cstdio>
#include<iostream>
#include<cstring>
#define il inline
#define rg register
#define MAXN 5010
#define MAXM 200010
#define INF 0x3f3f3f3f
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

struct Edge {
    int x, nex, w;
}e[MAXM<<1];

int head[MAXN], tote;

il void ae(int u, int v, int w)
{
    e[++tote].x = v;
    e[tote].w = w;
    e[tote].nex = head[u];
    head[u] = tote;
}

int n, m;

int dis[MAXN];
bool vis[MAXN];

int main()
{
    memset(dis, 0x3f, sizeof dis);
    Iput(n), Iput(m);
    for(rg int i=1 ; i<=m ; ++i)
    {
        int u, v, w;
        Iput(u), Iput(v), Iput(w);
        ae(u, v, w);
        ae(v, u, w);
    }
    dis[1] = 0;
    for(rg int k=1 ; k<n ; ++k)
    {
        int u = 0;
        for(rg int i=1 ; i<=n ; ++i)
            if(!vis[i] && (!u || dis[u]>dis[i]))
                u = i;
        vis[u] = true;
        for(rg int i=head[u] ; i ; i=e[i].nex)
        {
            int v = e[i].x, w = e[i].w;
            if(!vis[v] && dis[v]>w) //注意dis的含义为最小生成树的边长
                dis[v] = w;
        }
    }
    int ans = 0;
    for(rg int i=1 ; i<=n ; ++i)
    {
        if(dis[i] == INF)
        {
            printf("orz\n");
            return 0;
        }
        ans += dis[i];
    }
    Oput(ans);

    return 0;
}

Kruskal

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define il inline
#define rg register
#define MAXN 5010
#define MAXM 200010
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

struct Edge_k {
    int u, v, w;
}e[MAXM];

bool operator < (Edge_k x, Edge_k y)
{
    return x.w < y.w;
}

int pre[MAXN];

int find_f(int x)
{
    if(pre[x] < 0)  return x;
    return pre[x] = find_f(pre[x]);
}

il void union_f(int a, int b)
{
    int fa=find_f(a), fb=find_f(b);
    if(fa == fb)    return ;
    if(pre[fa] < pre[fb])   pre[fa]+=pre[fb], pre[fb]=fa;
    else    pre[fb]+=pre[fa], pre[fa]=fb;
}

il bool judge_f(int a, int b)
{
    return find_f(a) == find_f(b);
}

int n, m;
int ans;

int main()
{

    memset(pre, -1, sizeof pre);
    Iput(n), Iput(m);
    for(rg int i=1 ; i<=m ; ++i)
        Iput(e[i].u), Iput(e[i].v), Iput(e[i].w);
    sort(e+1, e+m+1);
    for(rg int i=1 ; i<=m ; ++i)
    {
        int u=e[i].u, v=e[i].v;
        if(!judge_f(u, v))
        {
            union_f(u, v);
            ans += e[i].w;
        }
    }
    int fa = find_f(1);
    for(rg int i=2 ; i<=n ; ++i)
        if(find_f(i) != fa)
        {
            printf("orz\n");
            return 0;
        }
    Oput(ans);

    return 0;
}

Tarjan

割点

P3388 【模板】割点(割顶)

#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 20010
#define MAXM 100010
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

struct Edge {
    int x, nex;
}e[MAXM<<1];

int head[MAXN], tote;

il void ae(int u, int v)
{
    e[++tote].x = v;
    e[tote].nex = head[u];
    head[u] = tote;
}

il void Min(int &a, int b)
{
    if(a > b)   a = b;
}

int n, m;

int root;
int low[MAXN], dfn[MAXN], dtr;
bool cut[MAXN];

void tarjan(int u)
{
    int flag = 0;
    low[u] = dfn[u] = ++dtr;
    for(rg int i=head[u] ; i ; i=e[i].nex)
    {
        int v = e[i].x;
        if(!dfn[v])
        {
            tarjan(v);
            Min(low[u], low[v]);
            if(dfn[u]<=low[v])
            {
                ++flag;
                if(u!=root || flag>1)
                    cut[u] = true;
            }
        }
        else
        {
            Min(low[u], dfn[v]);
        }
    }
}

int main()
{

    Iput(n), Iput(m);
    for(rg int i=1 ; i<=m ; ++i)
    {
        int u, v;
        Iput(u), Iput(v);
        ae(u, v);
        ae(v, u);
    }
    for(rg int i=1 ; i<=n ; ++i)
        if(!dfn[i])
        {
            root = i;
            tarjan(root);
        }
    int ans = 0;
    for(rg int i=1 ; i<=n ; ++i)
        if(cut[i])
            ++ans;
    Oput(ans);
    putchar('\n');
    for(rg int i=1 ; i<=n ; ++i)
        if(cut[i])
            Oput(i), putchar(' ');

    return 0;
}

割边

struct Edge {
    int x, nex;
}e[MAXM<<1];

int head[MAXN], tote=1; //注意这里初值为1才满足异或配偶性质

il void ae(int u, int v)
{
    e[++tote].x = v;
    e[tote].nex = head[u];
    head[u] = tote;
}

int n, m, ans;

int dfn[MAXN], dtr, low[MAXN];
bool cut[MAXM<<1];

void tarjan(int u, int in_edge) //较割点多一个参数:入边
{
    //这里无须特判根节点,无须flag
    low[u] = dfn[u] = ++dtr;
    for(rg int i=head[u] ; i ; i=e[i].nex)
    {
        int v = e[i].x;
        if(!dfn[v])
        {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u])
             {
                cut[i] = cut[i^1] = true;
                ++ans;  //由于搜索树上每条边只被搜索一次,可直接++ans
             }
        }
        else if(i != (in_edge^1))   //注意判反边,防止被父亲更新
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main()
{

    ...//Input
    for(rg int i=1 ; i<=n ; ++i)
        if(!dfn[i])
            tarjan(i, 0);   //这里注意不要写-1等等负数,不满足异或性质
    Oput(ans);

    return 0;
}

强连通分量:缩点

P3387 【模板】缩点

#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 10010
#define MAXM 100010 
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

struct Star {
    struct Edge {
        int x, nex;
    }e[MAXM];

    int head[MAXN], tote;

    il void ae(int u, int v)
    {
        e[++tote].x = v;
        e[tote].nex = head[u];
        head[u] = tote;
    }
}Nor, Scc;

il void Min(int &a, int b)
{
    if(a > b)   a = b;
}

il void Max(int &a, int b)
{
    if(a < b)   a = b;
}

int n, m;
int w[MAXN];

int low[MAXN], dfn[MAXN], dtr;
int scc, bel[MAXN], stk[MAXN], top, wscc[MAXN];
bool in_s[MAXN];

void tarjan(int u)
{
    low[u] = dfn[u] = ++dtr;
    stk[++top] = u;
    in_s[u] = true;
    for(rg int i=Nor.head[u] ; i ; i=Nor.e[i].nex)
    {
        int v = Nor.e[i].x;
        if(!dfn[v])
        {
            tarjan(v);
            Min(low[u], low[v]);
        }
        else if(in_s[v])
        {
            Min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u])
    {
        int t;
        ++scc;
        do
        {
            t = stk[top--];
            in_s[t] = false;
            bel[t] = scc;
            wscc[scc] += w[t];
        }while(t != u);
    }
}

int dp[MAXN], ans;

int main()
{

    Iput(n), Iput(m);
    for(rg int i=1 ; i<=n ; ++i)
        Iput(w[i]);
    for(rg int i=1 ; i<=m ; ++i)
    {
        int u, v;
        Iput(u), Iput(v);
        Nor.ae(u, v);
    }
    for(rg int i=1 ; i<=n ; ++i)
        if(!dfn[i])
            tarjan(i);
    for(rg int u=1 ; u<=n ; ++u)
        for(rg int i=Nor.head[u] ; i ; i=Nor.e[i].nex)
        {
            int v = Nor.e[i].x;
            if(bel[u] != bel[v])
                Scc.ae(bel[u], bel[v]);
        }
    for(rg int u=scc ; u ; --u)
    {
        dp[u] += wscc[u];
        Max(ans, dp[u]);
        for(rg int i=Scc.head[u] ; i ; i=Scc.e[i].nex)
            Max(dp[Scc.e[i].x], dp[u]);
    }
    Oput(ans); 

    return 0;
}

直径

倍增

#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 500010
#define MAXM 500010
#define LOGN 19
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

struct Edge {
    int x, nex;
}e[MAXM<<1];

int head[MAXN], tote;

il void ae(int u, int v)
{
    e[++tote].x = v;
    e[tote].nex = head[u];
    head[u] = tote;
}

int n, m, s;

int fa[MAXN][LOGN+1], dep[MAXN];    //注意+1 

void get_fa(int u, int f)
{
    dep[u] = dep[f] + 1;
    fa[u][0] = f;
    for(rg int i=1 ; i<=LOGN ; ++i)
        fa[u][i] = fa[fa[u][i-1]][i-1];
    for(rg int i=head[u] ; i ; i=e[i].nex)
    {
        int v = e[i].x;
        if(v == f)  continue;
        get_fa(v, u);
    }
}

il int lca(int u, int v)
{
    if(dep[u] < dep[v]) swap(u, v);
    for(rg int i=LOGN ; ~i ; --i)
        if(dep[fa[u][i]] >= dep[v])
            u = fa[u][i];
    if(u == v)  return u;
    for(rg int i=LOGN ; ~i ; --i)
        if(fa[u][i] != fa[v][i])
        {
            u = fa[u][i];
            v = fa[v][i];
        }
    return fa[u][0];
}

int main()
{

    Iput(n), Iput(m), Iput(s);
    for(rg int i=1 ; i<n ; ++i)
    {
        int u, v;
        Iput(u), Iput(v);
        ae(u, v);
        ae(v, u);
    }
    get_fa(s, s);
    for(rg int i=1 ; i<=n ; ++i)
    {
        int u, v;
        Iput(u), Iput(v);
        Oput(lca(u, v));
        putchar('\n');
    }

    return 0;
}

树剖

P3384 【模板】轻重链剖分

#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 100010
#define int long long
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

struct Edge {
    int x, nex;
}e[MAXN<<1];

int head[MAXN], tote;

il void ae(int u, int v)
{
    e[++tote].x = v;
    e[tote].nex = head[u];
    head[u] = tote;
}

int n, m, r, p;
int w[MAXN];

il void Mod(int &a)
{
    if(a >= p)  a %= p;
}

il void add(int &a, int b)
{
    a += b;
    Mod(a);
}

struct SGtree {
    #define MID int mid=(l+r)>>1
    #define L ls(k),l,mid
    #define R rs(k),mid+1,r

    int a[MAXN];

    struct Node {
        int v, lazy;
    }t[MAXN<<2];

    il int ls(int k)    {return k<<1;}
    il int rs(int k)    {return k<<1|1;}

    il void pu(int k)
    {
        t[k].v = t[ls(k)].v + t[rs(k)].v;
        Mod(t[k].v);    //注意取模
    }

    void build(int k, int l, int r)
    {
        if(l == r)
        {
            t[k].v = a[l];
            Mod(t[k].v);
            return ;
        }
        MID;
        build(L);
        build(R);
        pu(k);
    }

    il void f(int k, int l, int r, int v)
    {
        add(t[k].v, v*(r-l+1));
        add(t[k].lazy, v);
    }

    il void pd(int k, int l, int mid, int r)
    {
        if(!t[k].lazy)  return ;
        f(L, t[k].lazy);
        f(R, t[k].lazy);
        t[k].lazy = 0;
    }

    void modify(int k, int l, int r, int li, int ri, int v)
    {
        if(li<=l && r<=ri)  return f(k, l, r, v);
        MID;
        pd(k, l, mid, r);
        if(li<=mid) modify(L, li, ri, v);
        if(mid<ri)  modify(R, li, ri, v);
        pu(k);
    }

    int query(int k, int l, int r, int li, int ri)
    {
        if(li<=l && r<=ri)  return t[k].v;
        MID, ret=0;
        pd(k, l, mid, r);
        if(li<=mid) add(ret, query(L, li, ri));
        if(mid<ri)  add(ret, query(R, li, ri)); //注意取模:写add 
        return ret;
    }

}sg;

struct Decomposition {
    int siz[MAXN], dep[MAXN], wson[MAXN], fa[MAXN], top[MAXN], dfn[MAXN], dtr;

    void dfs1(int u, int f)
    {
        fa[u] = f;
        dep[u] = dep[f] + 1;
        siz[u] = 1;
        for(rg int i=head[u] ; i ; i=e[i].nex)
        {
            int v = e[i].x;
            if(v == f)  continue;
            dfs1(v, u);
            siz[u] += siz[v];
            if(!wson[u] || siz[wson[u]]<siz[v])
                wson[u] = v;
        }
    }

    void dfs2(int u, int topf)
    {
        top[u] = topf;
        dfn[u] = ++dtr;
        sg.a[dtr] = w[u];
        if(!wson[u])    return ;    //注意处理重儿子 
        dfs2(wson[u], topf);
        for(rg int i=head[u] ; i ; i=e[i].nex)
        {
            int v = e[i].x;
            if(v==fa[u] || v==wson[u])  continue;
            dfs2(v, v);
        }
    }

    il void modify_lca(int u, int v, int val)
    {
        while(top[u] != top[v])
        {
            if(dep[top[u]] < dep[top[v]])   swap(u, v);
            sg.modify(1, 1, n, dfn[top[u]], dfn[u], val);
            u = fa[top[u]];
        }
        if(dep[u] > dep[v]) swap(u, v);
        sg.modify(1, 1, n, dfn[u], dfn[v], val);
    }

    il int query_lca(int u, int v)
    {
        int ret = 0;
        while(top[u] != top[v])
        {
            if(dep[top[u]] < dep[top[v]])   swap(u, v);
            add(ret, sg.query(1, 1, n, dfn[top[u]], dfn[u]));
            u = fa[top[u]];
        }
        if(dep[u] > dep[v]) swap(u, v); //想清楚那个更浅 
        add(ret, sg.query(1, 1, n, dfn[u], dfn[v]));
        return ret;
    }

    il void modify_son(int x, int val)
    {
        sg.modify(1, 1, n, dfn[x], dfn[x]+siz[x]-1, val);
    }

    il int query_son(int x)
    {
        return sg.query(1, 1, n, dfn[x], dfn[x]+siz[x]-1);
    }
}dc;

signed main()
{

    Iput(n), Iput(m), Iput(r), Iput(p);
    for(rg int i=1 ; i<=n ; ++i)
        Iput(w[i]);
    for(rg int i=1 ; i<n ; ++i) //n-1边 
    {
        int u, v;
        Iput(u), Iput(v);
        ae(u, v);
        ae(v, u);
    }
    dc.dfs1(r, r);  //remember
    dc.dfs2(r, r);
    sg.build(1, 1, n);
    for(rg int i=1 ; i<=m ; ++i)
    {
        int op, x, y, z;
        Iput(op);
        if(op == 1)
        {
            Iput(x), Iput(y), Iput(z);
            dc.modify_lca(x, y, z);
        }
        else if(op == 2)
        {
            Iput(x), Iput(y);
            Oput(dc.query_lca(x, y));
            putchar('\n');
        }
        else if(op == 3)
        {
            Iput(x), Iput(z);
            dc.modify_son(x, z);
        }
        else
        {
            Iput(x);
            Oput(dc.query_son(x));
            putchar('\n');
        }
    }

    return 0;
}

欧拉路

P1341 无序字母对

#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 'z'
#define MINN 'A'
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

int n;
int mp[MAXN+10][MAXN+10];
int deg[MAXN+10];
int stk[10000], top;

void dfs(int u)
{
    for(rg int i=MINN ; i<=MAXN ; ++i)
        if(mp[u][i])
        {
            --mp[u][i];
            --mp[i][u];
            dfs(i);
        }
    stk[++top] = u;
}

int main()
{

    Iput(n);
    for(rg int i=1 ; i<=n ; ++i)
    {
        int u, v;
        while(!( ((u=getchar())>='a'&&u<='z') || (u>='A'&&u<='Z') ));
        while(!( ((v=getchar())>='a'&&v<='z') || (v>='A'&&v<='Z') ));
        ++mp[u][v];
        ++mp[v][u];
        ++deg[u];
        ++deg[v];
    }
    int ctr=0, s=0;
    for(rg int i=MINN ; i<=MAXN ; ++i)
        if(deg[i]&1)
        {
            if(!s)  s=i;
            ++ctr;
        }
    if(!ctr)
    {
        for(rg int i=MINN ; i<=MAXN ; ++i)
            if(deg[i])
            {
                if(!s)  s=i;
                break;
            }
    }
    if(ctr!=0 && ctr!=2)
    {
        printf("No Solution\n");
        return 0;
    }
    dfs(s);
    if(top != n+1)
    {
        printf("No Solution\n");
        return 0;
    }
    for(rg int i=top ; i ; --i)
        putchar(stk[i]);

    return 0;
}

数学相关

快速幂

P1226 【模板】快速幂||取余运算

多取模

int a, k, p;

il void Mod(int &a)
{
    if(a >= p)  a %= p;
}

il void mul(int &a, int b)
{
    a *= b;
    Mod(a);
}

il int qpow(int a, int k)
{
    int ret = 1;
    while(k)
    {
        if(k&1) mul(ret, a);
        mul(a, a);
        k >>= 1;
    }
    return ret%p;   //不模的话这样会挂:x^0 mod 1=1
}

signed main()
{

    Iput(a), Iput(k), Iput(p);
    printf("%lld^%lld mod %lld=%lld\n", a, k, p, qpow(a, k));

    return 0;
}

慢速乘

int a, k, p;

il void Mod(int &a)
{
    if(a >= p)  a %= p;
}

il void add(int &a, int b)
{
    a += b;
    Mod(a);
}

il void mul(int &a, int b)
{
    int ret = 0;
    while(b)
    {
        if(b&1) add(ret, a);
        add(a, a);
        b >>= 1;
    }
    a = ret;
}

il int qpow(int a, int k)
{
    int ret = 1;
    while(k)
    {
        if(k&1) mul(ret, a);
        mul(a, a);
        k >>= 1;
    }
    return ret%p;
}

signed main()
{

    Iput(a), Iput(k), Iput(p);
    printf("%lld^%lld mod %lld=%lld\n", a, k, p, qpow(a, k));

    return 0;
}

线性筛素数

#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 100000010
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

int N, q;

int prime[MAXN], mdiv[MAXN], tot;

il void get_prime(int n)
{
    for(rg int i=2 ; i<=n ; ++i)
    {
        if(!mdiv[i])
        {
            prime[++tot] = i;
            mdiv[i] = i;
        }
        for(rg int j=1 ; j<=tot&&prime[j]*i<=n ; ++j)
        {
            mdiv[i*prime[j]] = prime[j];
            if(mdiv[i] == prime[j]) break;
        }
    }
}

int main()
{

    Iput(N), Iput(q);
    get_prime(N);
    for(rg int i=1 ; i<=q ; ++i)
    {
        int t;
        Iput(t);
        Oput(prime[t]);
        putchar('\n');
    }

    return 0;
}

gcd

P4549 【模板】裴蜀定理

il int gcd(int a, int b)
{
    while(a^=b^=a^=b%=a);
    return b;
}

exgcd

#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define int long long
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    bool f=false;
    while((c=getchar())<'0' || c>'9')   if(c=='-')  f=true;
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
    if(f)   x=-x;
}

template <typename T> void Wri(T x)
{
    if(x > 9)   Wri(x/10);
    putchar(x%10^48);
}

template <typename T> il void Oput(T x)
{
    if(x < 0)   putchar('-'), x=-x;
    Wri(x);
}

int T;

void exgcd(int a, int b, int &g, int &x, int &y)
{
    if(!b)
    {
        x=1, y=0, g=a;
    }
    else
    {
        exgcd(b, a%b, g, y, x);
        y -= x*(a/b);
    }
}

signed main()
{

    Iput(T);
    for(rg int rp=1 ; rp<=T ; ++rp)
    {
        int a, b, c;
        Iput(a), Iput(b), Iput(c);
        int x, y, g;
        exgcd(a, b, g, x, y);
        if(c%g)
        {
            Oput(-1);
            putchar('\n');
            continue;
        }
        a /= g;
        b /= g;
//      c /= g;
        x *= c/g;
        y *= c/g;
        int xmin = (x%b+b)%b;
        int ymin = (y%a+a)%a;
        if(!xmin)   xmin += b;
        if(!ymin)   ymin += a;
        a *= g;
        b *= g;
//      c *= g;
        int xmax = (c-b*ymin)/a;
        int ymax = (c-a*xmin)/b;
        a /= g;
        b /= g;
        if(xmax<=0 || ymax<=0)
        {
            Oput(xmin);
            putchar(' ');
            Oput(ymin);
            putchar('\n');
        }
        else
        {
            Oput((xmax-xmin)/b+1);
            putchar(' ');
            Oput(xmin);
            putchar(' ');
            Oput(ymin);
            putchar(' ');
            Oput(xmax);
            putchar(' ');
            Oput(ymax);
            putchar('\n');
        }
    }

    return 0;
}

高斯消元

#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 55
using namespace std;
typedef double DB;

il DB Abs(DB x)
{
    if(x < 0)   return -x;
    return x;
}

il bool e0(DB x)
{
    return Abs(x) < 1e-7;
}

int n;
DB a[MAXN][MAXN];

il void gauss()
{
    int rank = 0;
    for(rg int c=1 ; c<=n ; ++c)
    {
        int pos = 0;
        for(rg int r=rank+1 ; r<=n ; ++r)
            if(!e0(a[r][c]))
            {
                pos = r;
                break;
            }
        if(!pos)    continue;
        ++rank;
        for(rg int i=c ; i<=n+1 ; ++i)
            swap(a[rank][i], a[pos][i]);
        for(rg int r=1 ; r<=n ; ++r)
        {
            if(r == rank)   continue;
            DB t = -a[r][c]/a[rank][c];
            for(rg int i=c ; i<=n+1 ; ++i)
                a[r][i] += t*a[rank][i];
        }
    }
    for(rg int i=rank+1 ; i<=n ; ++i)
        if(!e0(a[i][n+1]))
        {
            putchar('-');
            putchar('1');
            return ;
        }
    if(rank < n)
    {
        putchar('0');
        return ;
    }
    for(rg int i=1 ; i<=n ; ++i)
        printf("x%d=%.2lf\n", i, a[i][n+1]/a[i][i]);
}

int main()
{

    scanf("%d", &n);
    for(rg int i=1 ; i<=n ; ++i)
        for(rg int j=1 ; j<=n+1 ; ++j)
            scanf("%lf", &a[i][j]);
    gauss();

    return 0;
}

矩阵快速幂

#include<cstdio>
#include<iostream>
#include<cstring>
#define il inline
#define rg register
#define MAXN 110
#define MOD 1000000007
#define int long long
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    bool f=false;
    while((c=getchar())<'0' || c>'9')   if(c=='-')  f=true;
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
    if(f)   x=-x;
}

template <typename T> void Wri(T x)
{
    if(x > 9)   Wri(x/10);
    putchar(x%10^48);
}

template <typename T> il void Oput(T x)
{
    if(x < 0)   putchar('-'), x=-x;
    Wri(x);
}

int n, k;
struct Sqr {
    int a[MAXN][MAXN];
    Sqr() {memset(a, 0, sizeof a);}
}org;

Sqr operator * (Sqr x, Sqr y)
{
    Sqr ret;
    for(rg int k=1 ; k<=n ; ++k)
        for(rg int i=1 ; i<=n ; ++i)
            for(rg int j=1 ; j<=n ; ++j)
            {
                ret.a[i][j] += x.a[i][k]*y.a[k][j]%MOD;
                ret.a[i][j] %= MOD;
            }
    return ret;
}

Sqr qpow(Sqr x, int k)
{
    Sqr ret;
    for(rg int i=1 ; i<=n ; ++i)
        ret.a[i][i] = 1;
    while(k)
    {
        if(k&1) ret = ret*x;
        x = x*x;
        k >>= 1;
    }
    return ret;
}

signed main()
{

    Iput(n), Iput(k);
    for(rg int i=1 ; i<=n ; ++i)
        for(rg int j=1 ; j<=n ; ++j)
            Iput(org.a[i][j]);
    org = qpow(org, k);
    for(rg int i=1 ; i<=n ; ++i)
        for(rg int j=1 ; j<=n ; ++j)
            Oput((org.a[i][j]%MOD+MOD)%MOD), putchar(j==n?'\n':' ');

    return 0;
}

组合数的求法

高中数学..

字符串

Hash

P3370 【模板】字符串哈希

bitset开桶

#include<cstdio>
#include<iostream>
#include<bitset>
#define il inline
#define rg register
#define BASE 131
#define MOD 1000000007
using namespace std;
typedef long long LL;

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

int n;
bitset <MOD> Hash;  //120MB
int ans;

int main()
{

    Iput(n);
    for(rg int i=1 ; i<=n ; ++i)
    {
        char c;
        while(!( ((c=getchar())>='0'&&c<='9') || (c>='a'&&c<='z') || (c>='A'&&c<='Z') ));
        LL ret = c;
        while( ((c=getchar())>='0'&&c<='9') || (c>='a'&&c<='z') || (c>='A'&&c<='Z') )
        {
            ret = ret*BASE+c;
            if(ret >= MOD)  ret %= MOD;
        }
        if(!Hash[ret])
        {
            Hash[ret] = 1;
            ++ans;
        }
    }
    Oput(ans);

    return 0;
}

离散化

#include<cstdio>
#include<algorithm>
#define rg register
#define il inline
#define MAXN 10010
#define Base 26
#define MOD 2147483629
using namespace std;
typedef long long LL;

LL a[MAXN];

il LL hash(char c[])
{
    LL ans = 1ll;
    for(rg int i=0 ; c[i]!='\0' ; ++i)
    {
        ans = ans*26 + c[i];
        if(ans > MOD)
            ans %= MOD;
    }
    return ans;
}

int main()
{

    int n, ans=0;
    scanf("%d", &n);
    for(rg int i=1 ; i<=n ; ++i)
    {
        char c[1510];
        scanf("%s", c);
        a[i] = hash(c);
    }
    sort(a+1, a+1+n);
    printf("%d", unique(a+1, a+1+n) - a - 1);

    return 0;
}

哈希表

#include<cstdio>
#include<iostream>
#include<string>
#define il inline
#define rg register
#define MAXN 10010
#define BASE 131
#define MOD 1000003
using namespace std;
typedef long long LL;

struct Edge {
    string s;
    int nex;
}e[MAXN];

int head[MOD], tote;

il void ae(int Hash, string s)
{
    e[++tote].s = s;
    e[tote].nex = head[Hash];
    head[Hash] = tote;
}

int n, ans;

int main()
{

    cin >> n;
    for(rg int i=1 ; i<=n ; ++i)
    {
        string t;
        cin >> t;
        LL ret = 0;
        for(string::iterator it=t.begin() ; it!=t.end() ; ++it)
        {
            ret = ret*BASE+(*it);
            if(ret >= MOD)  ret %= MOD;
        }
        bool flag = false;
        for(rg int j=head[ret] ; j ; j=e[j].nex)
            if(e[j].s == t)
            {
                flag = true;
                break;
            }
        if(!flag)
        {
            ae(ret, t);
            ++ans;
        }
    }
    cout << ans; 

    return 0;
}

单字符串Hash

il void make_base(int l)
{
    b[0] = 1;
    for(rg int i=1 ; i<=l ; ++i)
    {
        b[i] = b[i-1] * base % MOD;
        if(b[i] < 0)    b[i] += MOD;
    }
}

il void make_hash(int l)
{
    for(rg int i=1 ; i<=l ; ++i)
    {
        h[i] = (h[i-1] * base + str[i]-'a') % MOD;
        if(h[i] < 0)    h[i] += MOD;
    }
}

il int hash(int l, int r)
{
    return ((h[r] - b[r-l+1]*h[l-1])%MOD + MOD)%MOD;
}

Trie

struct Trie {
    struct Node {
        int ch[26], ctr;
    }t[MAXN*MAXL];  //注意大小

    int tot;

    il void insert(char s[])
    {
        int p = 0;
        int len=strlen(s);
        for(rg int i=0 ; i<len ; ++i)
        {
            int c = s[i]-'a';
            if(!t[p].ch[c]) t[p].ch[c] = ++tot;
            p = t[p].ch[c];
        }
        ++t[p].end;
    }

    il int find(char s[])
    {
        int p = 0;
        int len=strlen(s);
        for(rg int i=0 ; i<len ; ++i)
        {
            int c = s[i]-'a';
            if(!t[p].ch[c]) return 0;
            p = t[p].ch[c];
        }
        return t[p].end;
    }
}trie;

KMP

#include<cstdio>
#include<iostream>
#include<cstring>
#define il inline
#define rg register
#define MAXN 1000010
using namespace std;

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

char s[MAXN], t[MAXN];
int ls, lt;
int fail[MAXN];

int main()
{

    scanf("%s%s", t+1, s+1);    //注意1下标开始 
    lt = strlen(t+1);
    ls = strlen(s+1);
    for(rg int i=2, j=0 ; i<=ls ; ++i)  //fail[1] = 0;
    {
        while(j && s[i]!=s[j+1])    j = fail[j];
        if(s[i] == s[j+1])  ++j;
        fail[i] = j;
    }
    for(rg int i=1, j=0 ; i<=lt ; ++i)  //从1开始 
    {
        while(j && t[i]!=s[j+1])    j = fail[j];
        if(t[i] == s[j+1])  ++j;
        if(j == ls)
        {
            Oput(i-ls+1);
            putchar('\n');
        }
    }
    for(rg int i=1 ; i<=ls ; ++i)
        Oput(fail[i]), putchar(' '); 

    return 0;
}

Manacher

#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 11000010
using namespace std;

template <typename T> il void Iput(T &x)
{
    char c;
    while((c=getchar())<'0' || c>'9');
    x = c^48;
    while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}

template <typename T> void Oput(T x)
{
    if(x > 9)   Oput(x/10);
    putchar(x%10^48);
}

int n;
char s[MAXN];
int mid, mp;    //mp为开区间 
int ans;
int p[MAXN];    //包括自己的翼长 

int main()
{

    s[0] = 1;   //注意这个 
    do
    {
        n += 2;
        s[n] = getchar();
    }while(s[n]>='a' && s[n]<='z');
    s[n--] = 2; //注意这个 
    for(rg int i=1 ; i<=n ; ++i)
    {
        p[i] = i<mp ? min(mp-i, p[(mid<<1)-i]) : 1;
        while(s[i-p[i]] == s[i+p[i]])   ++p[i];
        if(i+p[i] > mp)
        {
            mp = i+p[i];
            mid = i;
        }
        ans = max(ans, p[i]);
    }
    Oput(ans-1);    //注意减1!! 

    return 0;
}

最小表示法

其他知识和技巧

离散化

eg:

P1496 火烧赤壁

    Iput(n);
    for(rg int i=1 ; i<=n ; ++i)
    {
        Iput(a[i].l), Iput(a[i].r);
        lsh[i] = a[i].l;
        lsh[i+n] = a[i].r;
    }
    sort(lsh+1, lsh+(n<<1)+1);  //注意离散化数组长度,并且记得开够
    int len = unique(lsh+1, lsh+(n<<1)+1) - lsh - 1;
    for(rg int i=1 ; i<=n ; ++i)
    {
        int ll = lower_bound(lsh+1, lsh+len+1, a[i].l) - lsh;
        int rr = lower_bound(lsh+1, lsh+len+1, a[i].r) - lsh;
        for(rg int j=ll ; j<rr ; ++j)
            bt[j] = true;
    }

康拓展开

随机化算法