• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

OI 基础模板

开发技术 开发技术 4小时前 2次浏览

(text{Update:})

2021.9.15
STL 新增写了 list, multimap, bieset 等
历史更新记录

2021.9.10
更新 LCA 为 不含 lg 数组
2021.9.8 更新 FHQ-Treap 为能看的指针代码 更新 线段树 为效率高的指针代码
2021.9.1 重写了 tarjan 并更改模板题为 缩点 新增 Fast-Output
2021.8.29 线性求逆元和线性求欧拉函数
2021.8.20 更新 ST 表 和 Kruskal 为阳间代码
2021.7.24 更新快速幂为zrt的快速幂
2021.7.22 新增 Splay
2021.7.7 新增树链剖分
2021.7.4 更新线段树区间为左闭右闭 新增可持久化数组、可持久化线段树 将“常用 STL 初步”改名为“STL” 新增 STL:rope
2021.7.3 新增 Tarjan 输出强连通分量
2021.7.2 新增图的 BFS 与 DFS 参考代码
2021.6.30 新增扩展 KMP 算法
2021.6.29 新增 KMP 和 LCA 新增 FHQ-Treap 新增 AC自动机
2021.6.28 新增 std::string 新增 Tarjan
2021.6.15 新增 Treap 和 左偏树
2021.6.14 新增 Kruskal 最小生成树
2021.5.30 单源最短路径新增 vector 存图的
2021.5.16 动态规划新增 LCIS (最长公共上升子序列)
2021.5.14 更新了区间dp的模板
2021.4.29 新增了珂朵莉树 快速幂的代码锅了,现已修复 格式化了全部代码!!!
2021.4.28 添加了单调队列,包含 “定长” 和 “不定长”。
2021.4.23 求 gcd 的部分锅了,重新写了下。
2021.4.20 新增线段树的区间加乘,区间修改。 重构了线段树的代码。 更新了部分标题名称。

考试必备

Fast I/O

inline ll read()
{
    int x = 0, f = 0;
    char ch = getchar();
    while (!isdigit(ch))
        f |= (ch == '-'), ch = getchar();
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

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

对拍

卡常小技巧

① 位运算乘除

$ x=xtimes2^n 可以转化成 x<<n $

$ x=x÷2^n 可以转化成 x>>n $

② for 卡常

for (register int i(1); i <= n; ++i)

③ 短函数前加 inline 卡常

④ 判断奇偶

if(a % 2 == 0)  可以转化成  if((a & 1) == 0)

⑤ 取模用 &

x = 667 % 4;    可以转化成  x = 667 & (4-1);
x = 667 % 32;   可以转化成  x = 667 & (32-1);

⑥ 正负转换用位运算

i = -1;       可以转换成  i = ~i + 1;   或   i = (i ^ -1) + 1; 

⑦ 取绝对值

k = abs(x);   可以转换成  k = (x ^ (x >> 31))-(x >> 31);  

数据结构

ST表

静态查询区间最值。

ll f[100001][20], lg[100001];
ll n, m, a[100001];

void pre()
{
    lg[0] = -1;
    for (int i = 1; i <= n; ++i)
        lg[i] = lg[i >> 1] + 1;
}

void ST_make()
{
    for (int i = 1; i <= n; ++i)
        f[i][0] = a[i];
    for (int j = 1; j < 22; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

ll ST_check(ll l, ll r)
{
    ll k = lg[r - l + 1];
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    pre();
    ST_make();
    for (int i = 1; i <= m; ++i)
    {
        ll l = read(), r = read();
        printf("%lldn", ST_check(l, r));
    }
    return 0;
}

单调队列

例题1

有一个长为 (n) 的序列 (a),以及一个大小为 (k) 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。

ll n, k, cnt = 0;
ll ans[2][1000005];

struct node
{
    ll sum, id;
};

deque<node> maxq;
deque<node> minq;

int main()
{
    n = read();
    k = read();
    node t;
    for (int i = 1; i <= n; ++i)
    {
        ll x = read();
        t.id = i;
        t.sum = x;
        while (!minq.empty() && x <= minq.back().sum)
            minq.pop_back();
        while (!maxq.empty() && x >= maxq.back().sum)
            maxq.pop_back();
        minq.push_back(t);
        maxq.push_back(t);
        while (i - k >= minq.front().id)
            minq.pop_front();
        while (i - k >= maxq.front().id)
            maxq.pop_front();
        if (i >= k)
        {
            ans[0][++cnt] = minq.front().sum;
            ans[1][cnt] = maxq.front().sum;
        }
    }
    for (int i = 1; i <= n - k + 1; ++i)
        printf("%lld ", ans[0][i]);
    puts("");
    for (int i = 1; i <= n - k + 1; ++i)
        printf("%lld ", ans[1][i]);
}

例题2

最大不定长子段和问题。

在一段长为 (n) 的数列中,找出一个长度 (≤m) 的子段,使得它的和是最大的。子段长度不能为0。

const ll maxn = 5000005;
#define INF 9223372036854775800

ll sum[maxn], q[maxn];
ll n, m;

int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i)
    {
        ll x = read();
        sum[i] = sum[i - 1] + x;
    }

    ll h = 1, t = 1, ans = -INF;
    q[1] = 0;
    for (int i = 1; i <= n; ++i)
    {
        while (h <= t && q[h] < i - m)
            h++;
        ans = max(ans, sum[i] - sum[q[h]]);
        while (h <= t && sum[i] <= sum[q[t]])
            t--;
        q[++t] = i;
    }
    printf("%lldn", ans);
    Edison Ba;
}

树状数组

支持单点修改,区间查询。

ll lowbit(ll x)
{
    return x & (-x);
}

ll c[500002], n, m;

void add(ll x, ll y) //单点修改
{
    for (; x <= n; x += lowbit(x))
        c[x] += y;
}

ll sum(ll x) //前缀和
{
    ll ans = 0;
    for (; x; x -= lowbit(x))
        ans += c[x];
    return ans;
}

ll ask(ll l, ll r) //区间查询
{
    return sum(r) - sum(l - 1);
}

int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i) //初始化
    {
        ll x = read();
        add(i, x);
    }
    for (int i = 1; i <= m; ++i)
    {
        ll opt = read();
        if (opt == 1) //单点修改
        {
            ll x = read(), k = read();
            add(x, k);
        }
        else if (opt == 2) //区间查询
        {
            ll x, y;
            x = read();
            y = read();
            ll ans = ask(x, y);
            printf("%lldn", ans);
        }
    }
    return 0;
}

线段树

P3373 【模板】线段树 2

注:本线段树使用链表形式(指针),每个结点都是左闭右闭区间。

操作为加或乘,最后答案模 (mod)

打两个标记,分别为 addmul

ll n, m, mod;

struct node{
    ll L, R, add, mul, sum;
    node *lc, *rc;
    void makeadd(ll k)
    {
        sum = (sum + k * (R - L + 1)) % mod;
        add = (add + k) % mod;
    }
    void makemul(ll k)
    {
        sum = (sum * k) % mod;
        mul = (mul * k) % mod;
        add = (add * k) % mod;
    }
    void pushup()
    {
        sum = (lc->sum + rc->sum) % mod;
    }
    void pushdown()
    {
        if(mul != 1)
        {
            lc->makemul(mul);
            rc->makemul(mul);
            mul = 1;
        }
        if(add)
        {
            lc->makeadd(add);
            rc->makeadd(add);
            add = 0;
        }
    }
};

const ll N = 1e5 + 4;
ll a[N];

void Build(node *now, ll l, ll r)
{
    now->L = l;
    now->R = r;
    now->add = 0;
    now->mul = 1;
    now->sum = 0;
    if(l < r)
    {
        ll mid = (l + r) >> 1;
        now->lc = new node;
        now->rc = new node;
        Build(now->lc, l, mid);
        Build(now->rc, mid + 1, r);
        now->pushup();
    }
    else
    {
        now->sum = a[l];
        now->lc = now->rc = NULL;
    }
}

ll check(node *now, ll l, ll r)
{
    if(l <= now->L and now->R <= r)
        return now->sum % mod;
    now->pushdown();
    ll mid = (now->L + now->R) >> 1;
    ll ans = 0;
    if(l <= mid)
        ans = (ans + check(now->lc, l, r)) % mod;
    if(mid < r)
        ans = (ans + check(now->rc, l , r)) % mod;
    return ans % mod;
}

void add(node *now, ll l, ll r, ll k)
{
    if(l <= now->L and now->R <= r)
        now->makeadd(k);
    else
    {
        now->pushdown();
        ll mid = (now->L + now->R) >> 1;
        if(l <= mid)
            add(now->lc, l, r, k);
        if(mid < r)
            add(now->rc, l, r, k);
        now->pushup();
    }
}

void mul(node *now, ll l, ll r, ll k)
{
    if(l <= now->L and now->R <= r)
        now->makemul(k);
    else
    {
        now->pushdown();
        ll mid = (now->L + now->R) >> 1;
        if(l <= mid)
            mul(now->lc, l, r, k);
        if(mid < r)
            mul(now->rc, l, r, k);
        now->pushup();
    }
}

int main()
{
    n = read(), m = read(), mod = read();
    for(int i = 1; i <= n; ++i)
        a[i] = read();
    node *root;
    root = new node;
    Build(root, 1, n);
    for(int i = 1; i <= m; ++i)
    {
        ll opt = read(), l = read(), r = read(), k;
        if(opt == 1)
        {
            k = read();
            mul(root, l, r, k);
        }
        if(opt == 2)
        {
            k = read();
            add(root, l ,r, k);
        }
        if(opt == 3)
        {
            printf("%lldn", check(root, l, r) % mod);
        }
    }
    return 0;
}

树链剖分

(n) 个点, (m) 个操作数, 根结点为 (R), 取模数为 (mod)

输入一颗树。

支持的操作:

  1. (x) 点的点权增加(或修改)(y)
  2. 将树从 (x)(y) 结点最短路径上所有节点的值都加上 (z)
  3. 询问某个节点 (x)(y) 节点的路径中所有点的点权和 (或maxn)。
  4. (x) 为根结点的子树中所有点的点权都增加 (y)
  5. 求以 (x) 为根节点的子树内所有节点值之和
const ll N = 3e5 + 4;
ll n, m, tot, R, mod;
ll head[N], fa[N], son[N], siz[N], top[N], dep[N], seg[N], rev[N], a[N], lim[N];

struct nodee
{
    ll to, nxt;
} t[2 * N];

void add(ll x, ll y)
{
    t[++tot].to = y;
    t[tot].nxt = head[x];
    head[x] = tot;
}

void dfs1(ll u, ll father)
{
    siz[u] = 1, fa[u] = father, dep[u] = dep[father] + 1;
    for (ll i = head[u]; i; i = t[i].nxt)
    {
        ll y = t[i].to;
        if (siz[y] == 0)
        {
            dfs1(y, u);
            siz[u] += siz[y];
            if (siz[y] > siz[son[u]])
            {
                son[u] = y;
            }
        }
    }
}

void dfs2(ll u)
{
    seg[u] = ++seg[0];
    rev[seg[0]] = u;
    if (son[u])
    {
        top[son[u]] = top[u];
        dfs2(son[u]);
    }
    for (ll i = head[u]; i; i = t[i].nxt)
    {
        ll y = t[i].to;
        if (y == son[u] || fa[u] == y)
        {
            continue;
        }
        dfs2(y);
    }
    lim[u] = seg[0];
}

struct node
{
    ll L, R, sum, tag, maxn;
    node *lc, *rc;
};

void pushup(node *now)
{
    now->sum = (now->lc->sum + now->rc->sum) % mod;
    now->maxn = max(now->lc->maxn, now->rc->maxn);
}

inline void maketag(node *now, ll w)
{
    now->tag = (now->tag + w) % mod;
    now->sum = (now->sum + (now->R - now->L + 1) * w) % mod;
    now->maxn = w;
}

inline void pushdown(node *now)
{
    if (now->tag == 0)
        return;
    maketag(now->lc, now->tag);
    maketag(now->rc, now->tag);
    now->tag = 0;
}

void build(node *now, ll l, ll r)
{
    now->L = l;
    now->R = r;
    now->tag = 0;
    if (l < r)
    {
        ll mid = (l + r) >> 1;
        now->lc = new node;
        now->rc = new node;
        build(now->lc, l, mid);
        build(now->rc, mid + 1, r);
        pushup(now);
    }
    else
    {
        now->maxn = a[rev[l]];
        now->sum = a[rev[l]];
        now->lc = now->rc = NULL;
    }
}

void change(node *now, ll l, ll r, ll w)
{
    if (l <= now->L and now->R <= r)
    {
        maketag(now, w);
    }
    else if (!((now->L > r) || (now->R < l)))
    {
        pushdown(now);
        change(now->lc, l, r, w);
        change(now->rc, l, r, w);
        pushup(now);
    }
}

ll check1(node *now, ll l, ll r)
{
    if (l <= now->L and now->R <= r)
        return now->sum;
    if ((now->L > r) || (now->R < l))
        return 0;
    pushdown(now);
    return (check1(now->lc, l, r) + check1(now->rc, l, r)) % mod;
}

ll check2(node *now, ll l, ll r)
{
    if (l <= now->L and now->R <= r)
        return now->maxn;
    if ((now->L > r) || (now->R < l))
        return -INF;
    pushdown(now);
    return max(check2(now->lc, l, r), check2(now->rc, l, r));
}

int main()
{
    n = read(), m = read();
    R = 1, mod = INF; // R为根结点序号

    for (ll i = 1; i <= n; i++)
        top[i] = i;

    for (ll i = 1; i <= n; i++)
        a[i] = read();

    for (ll i = 1; i <= n - 1; i++)
    {
        ll x = read(), y = read();
        add(x, y);
        add(y, x);
    }

    dfs1(R, 0);
    dfs2(R);

    node *root;
    root = new node;
    build(root, 1, n);

    for (int i = 1; i <= m; ++i)
    {
        ll opt = read(), x = read(), y, z;

        // 把 x 点的点权增加 y
        // 如果想要修改,更改上面的 maketag
        if (opt == 0) 
        {
            y = read(); 
            change(root, seg[x], seg[x], y);
        }

        // 表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。
        else if (opt == 1)
        {
            y = read(), z = read();
            while (top[x] != top[y])
            {
                if (dep[top[x]] < dep[top[y]])
                    swap(x, y);
                change(root, seg[top[x]], seg[x], z);
                x = fa[top[x]];
            }
            if(seg[x] > seg[y]) swap(x, y);
            change(root, seg[x], seg[y], z);
        }
        
        // 询问某个节点 x 到 y 节点的路径中所有点的点权和 (或maxn)
        else if (opt == 2)
        {
            y = read();
            ll sum = 0;
            // ll maxn = -2147483647;
            while (top[x] != top[y])
            {
                if (dep[top[x]] < dep[top[y]])
                    swap(x, y);
                sum = (sum + check1(root, seg[top[x]], seg[x])) % mod;
                // maxn = max(maxn, check2(root, seg[top[x]], seg[x]));
                x = fa[top[x]];
            }
            if (seg[x] > seg[y])
                swap(x, y);
            sum = (sum + check1(root, seg[x], seg[y])) % mod;
            // maxn = max(maxn, check2(root, seg[x], seg[y]));
            printf("%lldn", sum);
        }

        // 把 x 为根结点的子树中所有点的点权都增加 y
        else if (opt == 3) 
        {
            y = read();
            change(root, seg[x], lim[x], y);
        }

        // 求以 x 为根节点的子树内所有节点值之和
        else if (opt == 4)
        {
            ll ans = check1(root, seg[x], lim[x]) % mod;
            printf("%lldn", ans);
        }
    }
    return 0;
}

平衡树

FHQ-Treap

普通平衡树

您需要写一种数据结构,来维护一些数,其中需要提供以下操作:

  1. 插入 (x)
  2. 删除 (x) 数(若有多个相同的数,因只删除一个)
  3. 查询 (x) 数的排名(排名定义为比当前数小的数的个数 (+1) )
  4. 查询排名为 (x) 的数
  5. (x) 的前驱(前驱定义为小于 (x),且最大的数)
  6. (x) 的后继(后继定义为大于 (x),且最小的数)

第一行为 (n),表示操作的个数,下面 (n) 行每行有两个数 (text{opt})(x)(text{opt}) 表示操作的序号(( 1≤opt≤6 ))

对于操作 (3,4,5,6) 每行输出一个数,表示对应答案


ll n;

struct node{
    ll size, w, ran;
    node *lc, *rc;
    node(int x)
    {
        size = 1, w = x, ran = rand();
        lc = rc = NULL;
    }
} *root = NULL;

void pushup(node *now)
{
    now->size = 1;
    if(now->lc != NULL) now->size += now->lc->size;
    if(now->rc != NULL) now->size += now->rc->size;
}

void split(node *now , ll k, node *&x, node *&y)
{
    if(now == NULL)
    {
        x = y = NULL;
        return ;
    }
    if(k < now->w)
        y = now, split(now->lc, k, x, now->lc);
    else 
        x = now, split(now->rc, k ,now->rc, y);
    pushup(now);
}

node *merge(node *x, node *y)
{
    if(x == NULL || y == NULL)
        return x == NULL ? y : x;
    if(x->ran < y->ran)
    {
        x->rc = merge(x->rc, y);
        pushup(x);
        return x;
    }
    else
    {
        y->lc = merge(x, y->lc);
        pushup(y);
        return y;
    }
}

void Insert(ll k)
{
    node *x, *y, *now = new node(k);
    split(root, k, x, y);
    root = merge(merge(x, now), y);
}

void Del(ll k)
{
    node *x, *y, *z;
    split(root, k, x, z);
    split(x, k - 1, x, y);
    y = merge(y->lc, y->rc);
    root = merge(merge(x, y), z);
}

ll Ran(ll k)
{
    ll ans = 0;
    node *x, *y;
    split(root, k - 1, x, y);
    ans = (x == NULL ? 0 : x->size) + 1;
    root = merge(x, y);
    return ans;
}

ll Kth(ll k)
{
    node *now = root;
    ll lsize;
    while(1)
    {
        lsize = (now->lc == NULL ? 0 : now->lc->size);
        if(lsize + 1 == k) break;
        else if(k <= lsize) now = now->lc;
        else
        {
            k -= lsize + 1;
            now = now->rc;
        }
    }
    return now->w;
}

int main()
{
    n = read();
    for(int i = 1; i <= n; ++i)
    {
        ll opt = read(), x = read();
        if(opt == 1) Insert(x);
        if(opt == 2) Del(x);
        if(opt == 3) printf("%lldn", Ran(x));
        if(opt == 4) printf("%lldn", Kth(x));
        if(opt == 5) printf("%lldn", Kth(Ran(x) - 1));
        if(opt == 6) printf("%lldn", Kth(Ran(x + 1)));
    }
    return 0;   
}
文艺平衡树

const ll N = 1e6 + 3;
ll n, m, a[N];

struct node
{
    ll size, w, ran, add;
    node *lc, *rc;
    node(int x)
    {
        size = 1, w = x, ran = rand(), add = 0;
        lc = rc = NULL;
    }
} *root = NULL;

void pushdown(node *now)
{
    swap(now->lc, now->rc);
    if (now->lc != NULL)
        now->lc->add ^= 1;
    if (now->rc != NULL)
        now->rc->add ^= 1;
    now->add = 0;
}

void pushup(node *now)
{
    now->size = 1;
    if (now->lc != NULL)
        now->size += now->lc->size;
    if (now->rc != NULL)
        now->size += now->rc->size;
}

void split(node *now, ll k, node *&x, node *&y)
{
    if (now == NULL)
    {
        x = y = NULL;
        return;
    }
    if (now->add)
        pushdown(now);
    ll ls = (now->lc == NULL) ? 1 : now->lc->size + 1;
    if (k < ls)
        y = now, split(now->lc, k, x, now->lc);
    else
        x = now, split(now->rc, k - ls, now->rc, y);
    pushup(now);
}

node *merge(node *x, node *y)
{
    if (x == NULL || y == NULL)
        return x == NULL ? y : x;
    if (x->ran < y->ran)
    {
        if (x->add)
            pushdown(x);
        x->rc = merge(x->rc, y);
        pushup(x);
        return x;
    }
    else
    {
        if(y->add) pushdown(y);
        y->lc = merge(x, y->lc);
        pushup(y);
        return y;
    }
}

node *Build(ll l, ll r)
{
    node *now;
    if (l == r)
        return now = new node(a[l]);
    ll mid = (l + r) >> 1;
    return merge(Build(l, mid), Build(mid + 1, r));
}

void Insert()
{
    for (int i = 1; i <= n; ++i)
        a[i] = i;
    root = Build(1, n);
}

void Reverse(ll l, ll r)
{
    node *x, *y, *z;
    split(root, r, x, z);
    split(x, l - 1, x, y);
    y->add ^= 1;
    root = merge(merge(x, y), z);
}

void Print(node *now)
{
    if(now->add) pushdown(now);
    if(now->lc) Print(now->lc);
    printf("%lld ", now->w);
    if(now->rc) Print(now->rc);
}

int main()
{
    n = read(), m = read();
    Insert();
    for (int i = 1; i <= m; ++i)
    {
        ll l = read(), r = read();
        Reverse(l, r);
    }
    Print(root);
    return 0;
}

Treap

const ll maxn = 1e5 + 10;
const ll inf = 1e14 + 10;
ll n, tot, root;

struct node
{
    ll l, r;
    ll v, rk;
    ll cnt, si
} s[maxn << 1];

inline ll New(ll w)
{
    s[++tot].v = w;
    s[tot].rk = rand();
    s[tot].cnt = s[tot].siz = 1;
    return tot;
}

inline void upd(ll p)
{
    s[p].siz = s[s[p].l].siz + s[s[p].r].siz + s[p].cnt;
}

inline void build()
{
    New(-inf), New(inf);
    root = 1;
    s[1].r = 2;
    upd(root);
    return;
}

inline void zig(ll &p)
{
    ll q = s[p].l;
    s[p].l = s[q].r, s[q].r = p;
    p = q;
    upd(s[p].r);
    upd(p);
}

inline void zag(ll &p)
{
    ll q = s[p].r;
    s[p].r = s[q].l, s[q].l = p;
    p = q;
    upd(s[p].l);
    upd(p);
}

inline void add(ll &p, ll x)
{
    if (p == 0)
    {
        p = New(x);
        return;
    }
    if (s[p].v == x)
    {
        s[p].cnt++;
        upd(p);
        return;
    }
    if (s[p].v < x)
    {
        add(s[p].r, x);
        if (s[p].rk < s[s[p].r].rk)
            zag(p);
    }
    if (s[p].v > x)
    {
        add(s[p].l, x);
        if (s[p].rk < s[s[p].l].rk)
            zig(p);
    }

    upd(p);
}

inline void delt(ll &p, ll x)
{
    if (p == 0)
        return;
    if (s[p].v == x)
    {
        if (s[p].cnt > 1)
        {
            s[p].cnt--;
            upd(p);
            return;
        }
        if (s[p].l || s[p].r)
        {
            if (s[p].r == 0 || s[s[p].l].rk > s[s[p].r].rk)
            {
                zig(p);
                delt(s[p].r, x);
            }
            else
            {
                zag(p);
                delt(s[p].l, x);
            }
            upd(p);
        }
        else
            p = 0;
        return;
    }
    if (s[p].v < x)
    {
        delt(s[p].r, x);
        upd(p);
        return;
    }
    if (s[p].v > x)
    {
        delt(s[p].l, x);
        upd(p);
        return;
    }
}

inline ll getrank(ll p, ll x)
{
    if (p == 0)
        return 0;
    if (s[p].v == x)
    {
        return s[s[p].l].siz + 1;
    }
    if (s[p].v > x)
    {
        return getrank(s[p].l, x);
    }
    else
    {
        return getrank(s[p].r, x) + s[s[p].l].siz + s[p].cnt;
    }
}

inline ll getval(ll p, ll x)
{
    if (p == 0)
        return inf;
    if (s[s[p].l].siz >= x)
    {
        return getval(s[p].l, x);
    }
    if (s[s[p].l].siz + s[p].cnt >= x)
    {
        return s[p].v;
    }
    else
    {
        return getval(s[p].r, x - s[s[p].l].siz - s[p].cnt);
    }
}

inline ll getpre(ll x)
{
    ll ans = 1;
    ll p = root;
    while (p)
    {
        if (x == s[p].v)
        {
            if (s[p].l)
            {
                p = s[p].l;
                while (s[p].r)
                    p = s[p].r;
                ans = p;
            }
            break;
        }
        if (s[p].v < x && s[p].v > s[ans].v)
            ans = p;
        if (x < s[p].v)
            p = s[p].l;
        else
            p = s[p].r;
    }
    return s[ans].v;
}

inline ll getnxt(ll x)
{
    ll ans = 2;
    ll p = root;
    while (p)
    {
        if (x == s[p].v)
        {
            if (s[p].r)
            {
                p = s[p].r;
                while (s[p].l)
                    p = s[p].l;
                ans = p;
            }
            break;
        }
        if (s[p].v > x && s[p].v < s[ans].v)
            ans = p;
        if (x < s[p].v)
            p = s[p].l;
        else
            p = s[p].r;
    }
    return s[ans].v;
}

int main()
{
    build();
    n = read();
    for (int i = 1; i <= n; i++)
    {
        ll op = read(), x = read();
        if (op == 1)
            add(root, x);
        if (op == 2)
            delt(root, x);
        if (op == 3)
            printf("%lldn", getrank(root, x) - 1);
        if (op == 4)
            printf("%lldn", getval(root, x + 1));
        if (op == 5)
            printf("%lldn", getpre(x));
        if (op == 6)
            printf("%lldn", getnxt(x));
    }
    return 0;
}

Splay

struct node
{
    ll cnt, val, size;
    node *son[2], *fa;
};

node *root, *null;

inline void C(node *&now)
{
    now->son[0] = now->son[1] = now->fa = null;
    now->val = now->cnt = now->size = 0;
}

inline bool getwhich(node *now)
{
    return now->fa->son[1] == now;
}

inline void rotate(node *now)
{
    node *fa = now->fa;
    node *gfa = fa->fa;
    ll idson = getwhich(now);
    gfa->son[getwhich(fa)] = now;
    now->fa = gfa;
    fa->son[idson] = now->son[idson ^ 1];
    now->son[idson ^ 1]->fa = fa;
    now->son[idson ^ 1] = fa;
    fa->fa = now;
    fa->size = fa->son[0]->size + fa->son[1]->size + fa->cnt;
    now->size = now->son[0]->size + now->son[1]->size + now->cnt;
}

inline void Splay(node *now, node *f)
{
    while (now->fa != f)
    {
        node *fa = now->fa;
        node *gfa = fa->fa;
        if (gfa != f)
            getwhich(now) ^ getwhich(fa) ? rotate(now) : rotate(fa);
        rotate(now);
    }
    if (f == null)
        root = now;
}

inline void insert(ll x)
{
    node *now = root, *fa = null;
    while (now != null and now->val != x)
    {
        fa = now;
        now = now->son[x > now->val];
    }
    if (now != null)
        ++now->cnt;
    else
    {
        node *p = new node;
        if (fa != null)
            fa->son[x > fa->val] = p;
        p->fa = fa;
        p->val = x;
        p->size = p->cnt = 1;
        p->son[0] = p->son[1] = null;
        Splay(p, null);
        return;
    }
    Splay(now, null);
}

void search(ll x)
{
    node *now = root;
    if (now == null)
        return;
    while (now->son[x > now->val] != null and x != now->val)
        now = now->son[x > now->val];
    Splay(now, null);
}

node *getpre(ll x)
{
    search(x);
    node *now = root->son[0];
    while (now->son[1] != null)
        now = now->son[1];
    return now;
}

node *getback(ll x)
{
    search(x);
    node *now = root->son[1];
    while (now->son[0] != null)
        now = now->son[0];
    return now;
}

ll getnum(ll x)
{
    node *now = root;
    while (1)
    {
        if (x <= now->son[0]->size)
            now = now->son[0];
        else
        {
            x -= (now->son[0]->size + now->cnt);
            if (x <= 0)
                return now->val;
            else
                now = now->son[1];
        }
    }
}

void _delete(ll x)
{
    node *pre = getpre(x), *back = getback(x);
    Splay(pre, null);
    Splay(back, pre);
    if (back->son[0]->cnt > 1)
    {
        --back->son[0]->cnt;
        Splay(back->son[0], null);
    }
    else
    {
        back->son[0] = null;
        C(back->son[0]);
    }
}

int main()
{
    null = new node;
    null->size = null->cnt = null->val = 0;
    null->son[0] = null->son[1] = null->fa = NULL;
    root = null;
    n = read();
    insert(-INF);
    insert(INF);
    for (int i = 1; i <= n; ++i)
    {
        ll opt = read(), x = read();
        if (opt == 1)
        {
            insert(x);
        }
        else if (opt == 2)
        {
            _delete(x);
        }
        else if (opt == 3)
        {
            search(x);
            printf("%lldn", root->son[0]->size);
        }
        else if (opt == 4)
        {
            printf("%lldn", getnum(x + 1));
        }
        else if (opt == 5)
        {
            insert(x);
            printf("%lldn", getpre(x)->val);
            _delete(x);
        }
        else
        {
            insert(x);
            printf("%lldn", getback(x)->val);
            _delete(x);
        }
    }
    return 0;
}

可持久化数组

P3919 【模板】可持久化线段树 1(可持久化数组)

如题,你需要维护这样的一个长度为 (N) 的数组,支持如下几种操作:

  1. 在某个历史版本上修改某一个位置上的值

  2. 访问某个历史版本上的某一位置的值

此外,每进行一次操作(对于操作 (2),即为生成一个完全一样的版本,不作任何改动),就会生成一个新的版本。版本编号即为当前操作的编号(从 (1) 开始编号,版本 (0) 表示初始状态数组)

  1. 对于操作1,格式为 (v_i ~1 ~loc_i~ value_i),即为在版本 (v_i) ​的基础上,将 (a_{{loc}_i}) 修改为 ({value}_i)

  2. 对于操作2,格式为 (v_i 2 {loc}_i)​,即访问版本 (v_i) ​中的 (a_{{loc}_i}) ​​的值,生成一样版本的对象应为 (v_i)

输出包含若干行,依次为每个操作2的结果。

学会动态开点很重要。本代码采用指针形式,点区间为左闭右闭。

const ll N = 1e6 + 3;
int n, m, tot, a[N];

struct node
{
    int L, R, w;
    node *lc, *rc;
};

struct node by[N * 21], *pool = by, *root[N];

node *New()
{
    return ++pool;
}

node *build(int l, int r)
{
    node *now = New();
    now->L = l;
    now->R = r;
    if (l < r)
    {
        ll mid = (now->L + now->R) >> 1;
        now->lc = build(l, mid);
        now->rc = build(mid + 1, r);
    }
    else
    {
        now->w = a[l];
        now->lc = now->rc = NULL;
    }
    return now;
}

inline bool out(node *&now, int l, int r)
{
    return (now->R < l) || (r < now->L);
}

void change(node *&pre, node *&now, int x, int w)
{
    *now = *pre;
    if (pre->L == x and pre->R == x)
        now->w = w;
    else
    {
        if (!out(pre->lc, x, x))
        {
            now->lc = New();
            change(pre->lc, now->lc, x, w);
        }
        else
        {
            now->rc = New();
            change(pre->rc, now->rc, x, w);
        }
    }
}

int check(node *now, int x)
{
    if (now->L == x && now->R == x)
        return now->w;
    if (!out(now->lc, x, x))
        return check(now->lc, x);
    else
        return check(now->rc, x);
}

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; ++i)
    {
        a[i] = read();
    }
    root[0] = build(1, n);
    for (int i = 0; i < m; ++i)
    {
        ll v = read(), opt = read(), x = read(), k;
        if (opt == 1)
        {
            k = read();
            root[++tot] = New();
            change(root[v], root[tot], x, k);
        }
        else
        {
            ll ans = check(root[v], x);
            printf("%lldn", ans);
            root[++tot] = New();
            root[tot] = root[v];
        }
    }
    return 0;
}

可持久化线段树

P3834 【模板】可持久化线段树 2(主席树)

这是个非常经典的主席树入门题——静态区间第 (k) 小。

对于指定的闭区间 ([l, r]) 查询其区间内的第 (k) 小值.

代码采用指针形式,区间为左闭右闭。

const ll M = 2e5 + 3;
int n, N, m, tot, a[M], b[M];

struct node
{
    int L, R, cnt;
    node *lc, *rc;
};

struct node by[M * 21], *pool = by, *root[M];

node *New()
{
    return ++pool;
}

void update(node *&now)
{
    now->cnt = now->lc->cnt + now->rc->cnt;
}

node *build(int l, int r)
{
    node *now = New();
    now->L = l;
    now->R = r;
    if (l < r)
    {
        int mid = (l + r) >> 1;
        now->lc = build(l, mid);
        now->rc = build(mid + 1, r);
        update(now);
    }
    else
    {
        now->cnt = 0;
        now->lc = now->rc = NULL;
    }
    return now;
}

inline bool out(node *&now, int l, int r)
{
    return (now->R < l) || (r < now->L);
}

void change(node *pre, node *now, int x)
{
    *now = *pre;
    if (pre->L == x and pre->R == x)
        now->cnt++;
    else
    {
        if (!out(pre->lc, x, x))
        {
            now->lc = New();
            change(pre->lc, now->lc, x);
            update(now);
        }
        else
        {
            now->rc = New();
            change(pre->rc, now->rc, x);
            update(now);
        }
    }
}

int check(node *&nowl, node *&nowr, int k)
{
    if (nowl->L == nowl->R)
        return nowl->L;
    int lcnt = nowr->lc->cnt - nowl->lc->cnt;
    if (lcnt >= k)
        return check(nowl->lc, nowr->lc, k);
    else
        return check(nowl->rc, nowr->rc, k - lcnt);
}

void Main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i)
    {
        a[i] = read();
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    N = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(b + 1, b + N + 1, a[i]) - b;
    root[0] = build(1, N);
    for (int i = 1; i <= n; ++i)
    {
        root[++tot] = New();
        change(root[tot - 1], root[tot], a[i]);
    }
    for (int i = 1; i <= m; ++i)
    {
        int l, r, k;
        l = read(), r = read(), k = read();
        int ans = b[check(root[l - 1], root[r], k)];
        printf("%dn", ans);
    }
}

左偏树

一开始有 (n) 个小根堆,每个堆包含且仅包含一个数。接下来需要支持两种操作:

  1. 1 x y:将第 (x) 个数和第 (y) 个数所在的小根堆合并(若第 (x) 或第 (y) 个数已经被删除或第 (x) 和第 (y) 个数在用一个堆内,则无视此操作)。
  2. 2 x:输出第 (x) 个数所在的堆最小数,并将这个最小数删除(若有多个最小数,优先删除先输入的;若第 (x) 个数已经被删除,则输出 (-1) 并无视删除操作)。

第一行包含两个正整数 (n,m),分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含 (n) 个正整数,其中第 (i) 个正整数表示第 (i) 个小根堆初始时包含且仅包含的数。

接下来 (m) 行每行 (2) 个或 (3) 个正整数,表示一条操作。

输出包含若干行整数,分别依次对应每一个操作 (2) 所得的结果。

#define M 150010
#define swap my_swap
#define ls S[x].Son[0]
#define rs S[x].Son[1]

struct Tree
{
    ll dis, val, Son[2], rt;
} S[M];
ll N, T, A, B, C, i;

inline ll Merge(ll x, ll y);
ll my_swap(ll &x, ll &y) { x ^= y ^= x ^= y; }
inline ll Get(ll x) { return S[x].rt == x ? x : S[x].rt = Get(S[x].rt); }
inline void Pop(ll x) { S[x].val = -1, S[ls].rt = ls, S[rs].rt = rs, S[x].rt = Merge(ls, rs); }
inline ll Merge(ll x, ll y)
{
    if (!x || !y)
        return x + y;
    if (S[x].val > S[y].val || (S[x].val == S[y].val && x > y))
        swap(x, y);
    rs = Merge(rs, y);
    if (S[ls].dis < S[rs].dis)
        swap(ls, rs);
    S[ls].rt = S[rs].rt = S[x].rt = x, S[x].dis = S[rs].dis + 1;
    return x;
}
int main()
{
    N = read(), T = read();
    S[0].dis = -1;
    for (i = 1; i <= N; ++i)
        S[i].rt = i, S[i].val = read();
    for (i = 1; i <= T; ++i)
    {
        A = read(), B = read();
        if (A == 1)
        {
            C = read();
            if (S[B].val == -1 || S[C].val == -1)
                continue;
            ll f1 = Get(B), f2 = Get(C);
            if (f1 != f2)
                S[f1].rt = S[f2].rt = Merge(f1, f2);
        }
        else
        {
            if (S[B].val == -1)
                puts("-1");
            else
                printf("%lldn", S[Get(B)].val), Pop(Get(B));
        }
    }
    return 0;
}

珂朵莉树

神奇的暴力数据结构

例题

(n) 个数,(m) 次操作 ((n,m≤105))

操作:

  • 区间加
  • 区间赋值
  • 区间第k小
  • 求区间幂次和

数据随机,时限 (2s)

关键操作:推平一段区间,使一整段区间内的东西变得一样。保证数据随机

#include <set>
#include <vector>
#define p 1000000007
#define IT set<node>::iterator

/* 初始化 */
struct node
{
    ll l, r;
    mutable ll w; //可变的
    node(ll L, ll R = -1, ll W = 0)
    {
        l = L;
        r = R;
        w = W;
    }
    bool operator<(const node &o) const
    {
        return l < o.l;
    }
};


ll n, m, seed, vmax, a[100005];
set<node> s;

ll rnd() /* 对于本题的数据生成器 */
{
    ll ans = seed;
    seed = (seed * 7 + 13) % p;
    return ans;
}

ll ksm(){}

IT split(ll pos) /* 分裂 */
{
    IT it = s.lower_bound(node(pos));
    if (it != s.end() && it->l == pos)
        return it;
    --it;
    ll L = it->l, R = it->r;
    ll W = it->w;
    s.erase(it);
    s.insert(node(L, pos - 1, W));
    return s.insert(node(pos, R, W)).first;
}

void assign(ll l, ll r, ll w = 0) /* 推平 */
{
    IT itl = split(l), itr = split(r + 1);
    s.erase(itl, itr);
    s.insert(node(l, r, w));
}

void add(ll l, ll r, ll w = 1) /* 暴力区间加 */
{
    IT itl = split(l), itr = split(r + 1);
    for (; itl != itr; ++itl)
        itl->w += w;
}

ll rnk(ll l, ll r, ll k) /* 暴力区间第 k 小 */
{
    vector<pair<ll, int>> vp;
    IT itl = split(l), itr = split(r + 1);
    vp.clear();
    for (; itl != itr; ++itl)
        vp.push_back(pair<ll, int>(itl->w, itl->r - itl->l + 1));
    std::sort(vp.begin(), vp.end());
    for (vector<pair<ll, int>>::iterator it = vp.begin(); it != vp.end(); ++it)
    {
        k -= it->second;
        if (k <= 0)
            return it->first;
    }
    return -1LL;
}

ll sum(ll l, ll r, ll ex, ll mod) /* 暴力求和 */
{
    IT itl = split(l), itr = split(r + 1);
    ll res = 0;
    for (; itl != itr; ++itl)
        res = (res + (ll)(itl->r - itl->l + 1) * ksm(itl->w, ex, mod)) % mod;
    return res;
}

int main()
{
    n = read();
    m = read();
    seed = read();
    vmax = read();
    for (int i = 1; i <= n; ++i)
    {
        a[i] = (rnd() % vmax) + 1;
        s.insert(node(i, i, a[i]));
    }
    s.insert(node(n + 1, n + 1, 0));

    for (int i = 1; i <= m; ++i)
    {
        ll op = 1LL * (rnd() % 4) + 1;
        ll l = 1LL * (rnd() % n) + 1;
        ll r = 1LL * (rnd() % n) + 1;
        if (l > r)
            swap(l, r);
        ll x, y;
        if (op == 3)
            x = 1LL * (rnd() % (r - l + 1)) + 1;
        else
            x = 1LL * (rnd() % vmax) + 1;
        if (op == 4)
            y = 1LL * (rnd() % vmax) + 1;
        if (op == 1)
            add(l, r, x);
        else if (op == 2)
            assign(l, r, x);
        else if (op == 3)
            printf("%lldn", rnk(l, r, x));
        else
            printf("%lldn", sum(l, r, x, y));
    }
    return 0;
}

数学

线性筛素数

给定一个整数 (n) ,求出 $[2,n] $ 之间的所有素数。

思路:prime 数组存放已经筛出的素数, (m) 代表素数个数(也就是说遍历时从 (1) 遍历(m) 即可),v 数组代表有没有被标记,避免重复筛。

int v[maxn], prime[maxn], n, k, t, m;
void primes(int n)
{
    memset(v, 0, sizeof(v)); //清空标记数组
    m = 0;                   //质数个数
    for (int i = 2; i <= n; i++)
    {
        if (!v[i])                    //未被标记,i为质数
            v[i] = i, prime[++m] = i; //记录
        for (int j = 1; j <= m; j++)
        {
            if (prime[j] > v[i] || prime[j] > n / i)
                break;                  //i有更小的质因子,或者超出n的范围
            v[i * prime[j]] = prime[j]; //prime[j]为合数 i*prime[j]的最小质因子
        }
    }
}
int main()
{
    scanf("%d", &n);
    primes(n);
    for (int i = 1; i <= m; ++i)
        printf("%dn", prime[i]);
}

最大公约数

① 标准

inline int gcd(int a, int b)
{
    int r;
    while (b > 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

② 位运算

inline int gcd(int a, int b) //a,b不能为0
{
    while (b ^= a ^= b ^= a %= b)
        ;
    return a;
}

③ 辗转相除法

inline int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

④ 三目

inline int gcd(int a, int b)
{
    return b > 0 ? gcd(b, a % b) : a;
}

⑤ 外挂(考试禁止)

#include <algorithm>
inline int gcd(int a, int b)
{
    return __gcd(a, b); //其实可以在主函数里直接用这个
}

线性求逆元

inv[0] = inv[1] = 1;
    for (register int i(2); i <= n; i++)
        inv[i] = (1ll * (mod - mod / i) * inv[mod % i]) % mod;

线性求欧拉函数

int prime[N], phi[N];
bool isprime[N];

void pre()
{
    ll cnt = 0;
    isprime[1] = 1;
    phi[1] = 1;
    for (register int i(2); i <= n; ++i)
    {
        if (!isprime[i])
        {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (register int j(1); j <= cnt and i * prime[j] <= n; ++j)
        {
            isprime[i * prime[j]] = 1;
            if (i % prime[j])
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            else
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}

分治

快速乘法取余

给定三个整数 (a,n,mod) ,求 (a times n ~%~mod) 的值。

inline int mult_mod(int a, int n, int mod)
{
    int ans = 0;
    while (n > 0)
    {
        if (n & 1)
            ans = (ans + a) % mod;
        a = (a + a) % mod;
        n >>= 1;
    }
    return ans;
}

这个东西好像没有必要的样子,貌似只需要 ((a~%~mod)×(n~%~mod)~%~mod) 即可。

快速幂

给定三个整数 (a,b,mod) ,求 (a^b~%~mod) 的值。

ll ksm(ll a, ll b, ll mod)
{
    ll ret = 1 % mod;
    while(b)
    {
        if(b & 1)
            ret = ret * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ret;
}

LIS

求一个序列的最长上升子序列个数。
本程序采用边读边处理 + 二分法。

ll f[maxn], ans = 1; //注意答案个数初始化为1

int main()
{
    ll n = read();
    for (int i = 1; i <= n; ++i)
    {
        int x = read();
        if (i == 1)
        {
            f[1] = x;
            continue;
        }
        int l = 1, r = ans, mid;
        while (l <= r)
        {
            mid = (l + r) >> 1;
            if (x <= f[mid])
                r = mid - 1;
            else
                l = mid + 1;
        }
        f[l] = x;
        if (l > ans)
            ++ans;
    }
    printf("%lldn", ans);
    return 0;
}

lower_bound

使用前提:数列为有序数列。

①数组内

//查找范围:[ begin , end ) ,左闭右开区间。
*lower_bound(begin, end, num);        //返回第一个 >= num 的数的数值
lower_bound(begin, end, num) - begin; // 返回下标

实际操作:
int a[100] = {0, 1, 3, 5, 7, 9, 10};
//       下标:0  1  2  3  4  5  6
int main()
{
    int x = lower_bound(a + 1, a + 6 + 1, 6) - a; //输出下标
    int y = *lower_bound(a + 1, a + 6 + 1, 6);    //输出值
    printf("%d %d", x, y);
    return 0;
}

输出结果:4 7

②结构体内

结构体内使用 lower_bound 需要重载,下面我们主要对结构体中的 (a) 进行操作。

struct node //开结构体
{
    int a, id; //定义结构体内的两个变量
    node() {}
    node(int x, int y) : a(x), id(y) {}
    bool operator<(const node t) const //重载
    {
        return a < t.a;
    }
} t[1001];

bool cmp(node x, node y) //快排 cmp 比较函数
{
    if (x.a < y.a)
        return 1; //结构体内按 a 由小到大排序。
    return 0;
}

int main()
{
    int n = read(); //数列中数的个数
    for (int i = 1; i <= n; ++i)
    {
        t[i].a = read(); //读入数列
        t[i].id = i;
    }
    sort(t + 1, t + n + 1, cmp); //按小到大排序

    int x, xiabiao, ans;
    x = read();                                              //需要查找的数字
    xiabiao = lower_bound(t + 1, t + n + 1, node(x, 0)) - t; //这样求下标
    ans = (*lower_bound(t + 1, t + n + 1, node(x, 0))).a;    //这样求值
    printf("%d %dn", xiabiao, ans);
    return 0;
}

输入:
5
20 40 30 10 50
35
输出:
4 40

另:upper_bound 的使用与 lower_bound 的使用类似,只不过是严格大于(>)。

动态规划

基础模型

数字金字塔

f[i][j] = max((f[i][j] + f[i + 1][j]), (f[i][j] + f[i][j + 1]));

LCS

操作对象:两个长度不一定相等的字符串。

例题

string s, t;
int f[maxn][maxn];

int main()
{
    cin >> s >> t;
    int ls = s.length(), lt = t.length();
    for (int i = 1; i <= ls; i++)
        for (int j = 1; j <= lt; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (s[i - 1] == t[j - 1])
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    cout << f[ls][lt] << endl;
    return 0;
}

LCIS

操作对象:两个长度不一定相等的数列。

CF10D

const int maxn = 1005;
ll n, m, a[maxn], b[maxn], ans;
ll f[maxn][maxn], lcis[maxn][maxn];

int main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    m = read();
    for (int i = 1; i <= m; ++i)
        b[i] = read();

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1, k = 0; j <= m; ++j)
        {
            if (a[i] == b[j])
            {
                f[i][j] = f[i - 1][k] + 1;
                for (int p = 1; p <= f[i - 1][k]; ++p)
                    lcis[j][p] = lcis[k][p];
                lcis[j][f[i][j]] = a[i];
            }
            else
                f[i][j] = f[i - 1][j];
            if (b[j] < a[i] && f[i][j] > f[i][k])
                k = j;
        }
    }

    for (int i = 1; i <= m; ++i)
        if (f[n][i] > f[n][ans])
            ans = i;

    printf("%lldn", f[n][ans]);
    for (int p = 1; p <= f[n][ans]; ++p)
        printf("%lld ", lcis[ans][p]);
    puts("");
    return 0;
}

基础背包

01背包

背包数量为 (V),有 (n)件物品,重量为 (w_i),价值为 (c_i)。求能获得最大价值。

ll V, n, w[10000], c[10000], f[10000];

int main()
{
    V = read();
    n = read();
    for (int i = 1; i <= n; ++i)
    {
        w[i] = read();
        c[i] = read();
    }
    for (int i = 1; i <= n; ++i)
        for (int v = V; v >= w[i]; --v)
        {
            if (f[v - w[i]] + c[i] > f[v])
                f[v] = f[v - w[i]] + c[i];
        }
    printf("%lldn", f[V]);
    return 0;
}

01-方案数

一种物品只能选一次,组合出固定价值的方案数问题。

例题:ybt1291:数字组合

ll a[21], f[1003], n, t;
int main()
{
    n = read();
    t = read();
    for (int i = 1; i <= n; ++i)
    {
        a[i] = read();
    }
    f[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = t; j >= a[i]; --j)
        {
            f[j] += f[j - a[i]];
        }
    }
    printf("%lldn", f[t]);
    return 0;
}

完全背包

一种物品可以选无限次。
只需要改一下第二层循环的循环顺序就行了。

for (int i = 1; i <= n; ++i)
    for (int v = w[i]; v <= V; ++v)
    {
        if (f[v - w[i]] + c[i] > f[v])
            f[v] = f[v - w[i]] + c[i];
    }

完全-方案数

一种物品可以选无限次,组合出固定价值的方案数问题。
例题:ybt1293:买书

ll a[5], f[10002], m;

int main()
{
    m = read();
    a[1] = 10, a[2] = 20, a[3] = 50, a[4] = 100;
    f[0] = 1;
    for (int i = 1; i <= 4; ++i)
    {
        for (int j = a[i]; j <= m; ++j)
        {
            f[j] += f[j - a[i]];
        }
    }
    printf("%lldn", f[m]);
    return 0;
}

混合背包

一种物品可以选 (p) 次。

ll w[31], c[31], p[31];
ll f[201], n, m;

int main()
{
    m = read();
    n = read();
    for (int i = 1; i <= n; ++i)
    {
        w[i] = read();
        c[i] = read();
        p[i] = read();
    }
    for (int i = 1; i <= n; ++i)
    {
        if (p[i] == 0) //完全
        {
            for (int j = w[i]; j <= m; ++j)
                f[j] = max(f[j], f[j - w[i]] + c[i]);
        }
        else //01和多重
        {
            for (int j = 1; j <= p[i]; ++j)
            {
                for (int k = m; k >= w[i]; --k)
                {
                    f[k] = max(f[k], f[k - w[i]] + c[i]);
                }
            }
        }
    }
    printf("%lldn", f[m]);
    return 0;
}

二维费用背包

再加一重循环,多开一维数组即可。

例题:ybt1271:【例9.15】潜水员

ll v, u, k;
ll a[1091], b[1021], c[1092];
ll f[101][101];

int main()
{
    memset(f, 127, sizeof f);
    f[0][0] = 0;
    v = read();
    u = read();
    k = read();
    for (int i = 1; i <= k; ++i)
    {
        a[i] = read();
        b[i] = read();
        c[i] = read();
    }
    for (int i = 1; i <= k; ++i)
    {
        for (int j = v; j >= 0; --j)
        {
            for (int l = u; l >= 0; --l)
            {
                ll t1 = j + a[i];
                ll t2 = l + b[i];
                t1 = min(t1, v);
                t2 = min(t2, u);
                f[t1][t2] = min(f[t1][t2], f[j][l] + c[i]);
            }
        }
    }
    printf("%lldn", f[v][u]);
    return 0;
}

进阶dp

区间dp

f[i][j] 中的 (i) 为起点,(j) 为终点进行 dp。

核心代码:


for (int t = 2; t <= n; ++t)
{
    for (int i = 1; i <=  n - t + 1; ++i)
    {
        int j = i + t - 1;
        for (int k = i; k < j; ++k)
        {
            f[i][j] = ();
        }
    }
}

print()

斜率优化dp

未完成,待补充。

例题:[HNOI2008]玩具装箱

ll sum[M], f[M], Q[M];
ll n, L;

ll X(ll j)
{
    return sum[j];
}

ll Y(ll j)
{
    return f[j] + (sum[j] + L) * (sum[j] + L);
}

long double K(ll j, ll k)
{
    return 1.0 * ((Y(j) - Y(k)) / (X(j) - X(k)));
}

int main()
{
    n = read();
    L = read();
    for (int i = 1; i <= n; ++i)
    {
        sum[i] = read();
        sum[i] += sum[i - 1];
        ++sum[i];
    }

    ll l = 1, r = 1, j;
    for (int i = 1; i <= n; ++i)
    {
        while (l < r && K(Q[l + 1], Q[l]) <= 2 * sum[i])
            ++l;
        j = Q[l];
        f[i] = f[j] + (sum[i] - sum[j] - (L + 1)) * (sum[i] - sum[j] - (L + 1));
        while (l < r && K(Q[r], Q[r - 1]) >= K(i, Q[r - 1]))
            --r;
        Q[++r] = i;
    }
    printf("%lldn", f[n]);
}

图论

前置

链式前向星存图

ll head[maxn];

struct node
{
    ll nxt, to, w;
} t[maxn];

void add(const ll u, const ll v, const ll w)
{
    t[++tot].to = v;
    t[tot].w = w;
    t[tot].nxt = head[u];
    head[u] = tot;
}

vector 存图

struct node{
    ll to, w;
};

vector<node> t[maxn];

void add(const int u, const int v, const int w)
{
    t[u].push_back((node){v, w});
}

图的遍历

存图形式采用 (text{vector}) 存图

ans 存储遍历顺序。

DFS

void dfs(ll s)
{
    vis[s] = 1;
    ans.push_back(s);
    for (int i = 0; i < t[s].size(); ++i)
        if (!vis[t[s][i]])
            dfs(t[s][i]);
}

BFS

void bfs(ll s)
{
    queue<ll> q;
    q.push(s);
    vis[s] = 1;
    while (!q.empty())
    {
        ll x = q.front();
        ans.push_back(x);
        q.pop();
        for (ll i = 0; i < t[x].size(); ++i)
        {
            if (!vis[t[x][i]])
            {
                q.push(t[x][i]);
                vis[t[x][i]] = 1;
            }
        }
    }
}

Dijkstra 最短路

求单源 (s) 到任意一点的最短路径。最短路径保存在数组 dis 中。

链式前向星

#include <queue>
priority_queue<pair<ll, ll>> q;
void dijkstra(int s)
{
    memset(dis, 0x3f, sizeof(dis)); //初始边无限大
    memset(vis, 0, sizeof(vis));          //结点初始均为访问
    dis[s] = 0;                           //起点到自己距离为0
    q.push(make_pair(0, s));              //起点进队
    while (!q.empty())
    {
        x = q.top().second;
        q.pop();                          //初始结点入队
        if (vis[x])
            continue;                     //如果走过,直接跳过
        vis[x] = 1;                       //标记已访问
        for (ll i = head[x]; i != -1; i = t[i].nxt)
        {
            ll y = t[i].to, z = t[i].w;
            if (dis[y] > dis[x] + z)
            {
                dis[y] = dis[x] + z;           //更新起点到y最短路
                q.push(make_pair(-dis[y], y)); //d[y]相反数入队,转小根堆
            }
        }
    }
}
int main()
{
    for (int i = 1; i <= n; ++i)
        head[i] = -1;
    ...
}
//后面省略

vector

void dj(int s)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof vis);
    dis[s] = 0;
    q.push(make_pair(0, s));
    while (!q.empty())
    {
        ll x = q.top().second;
        q.pop();
        if (vis[x])
            continue;
        vis[x] = 1;
        for (int i = 0; i < t[x].size(); ++i)
        {
            ll y = t[x][i].to, z = t[x][i].w;
            if (dis[y] > dis[x] + z)
            {
                dis[y] = dis[x] + z;
                q.push(make_pair(-dis[y], y));
            }
        }
    }
}

SPFA

SPFA能处理负边权,可以判断负环。也可以求最长路。

最短路

#include <queue>
queue<int> q;
void SPFA(int s)
{
    fill(dis + 1, dis + 1 + n, 2147483647); //初始边无限大
    memset(vis, 0, sizeof vis);
    dis[s] = 0;
    q.push(s);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int i = head[x]; i != -1; i = t[i].nxt)
        {
            int y = t[i].to, z = t[i].w;
            if (dis[y] > dis[x] + z)
            {
                dis[y] = dis[x] + z;
                if (vis[y] == 0)
                {
                    q.push(y);
                    vis[y] = 1;
                }
            }
        }
    }
}

最长路

可依据最短路代码进行修改。

1. `dis` 数组赋初值时,如果没有负边权就赋 $-1$ ,如果有负边权就赋无限小。
  1. dis[y]>dis[x]+z 中的 > 改成 <

判断负环

可在最短路代码基础上进行修改。需新加入一个数组 cnt ,专门记录负环。

补充代码:

ll cnt[maxn]; //专门记录负环
void SPFA().....if (dis[y] > dis[x] + z)
{
    dis[y] = dis[x] + z;
    cnt[y]++;
    if (cnt[y] >= n + 1) //出现超过n次表示就有负环
    {
        ans = 1; //ans=1代表有负环。
        return;
    }
    if (vis[y] == 0)
    {
        q.push(y);
        vis[y] = 1;
    }
}

Floyd 全源最短路

inline void floyd()
{
    for (k = 1; k <= n; k++)
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                if (e[i][j] > e[i][k] + e[k][j])
                    e[i][j] = e[i][k] + e[k][j];
}

并查集

(n) 代表元素个数,(m) 为操作数。

(opt=1) 时,合并集合 (a,b)(opt=2) 时,如果 (a,b) 在同一集合,输出 Y 否则输出 N

int find(int k)
{
    if (f[k] == k)
        return k;
    return f[k] = find(f[k]);
}

int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i)
        f[i] = i; //初始化自己的老大是自己

    for (int i = 1; i <= m; ++i)
    {
        int opt, a, b;
        opt = read();
        a = read();
        b = read();
        if (opt == 1)
            f[find(a)] = find(b);
        else
        {
            if (find(a) == find(b))
                printf("Yn");
            else
                printf("Nn");
        }
    }
    return 0;
}

LCA

P3379 【模板】最近公共祖先(LCA)

邻接表存图。

struct node{...};
void add(...){}

ll dep[500010], fa[500010][25];
ll head[500010], tot;
ll n, m, s;

ll dep[N], fa[N][23];
void dfs(ll now, ll fath)
{
    dep[now] = dep[fath] + 1;
    fa[now][0] = fath;
    for(int i = 1; i <= 22; ++i)
        fa[now][i] = fa[fa[now][i - 1]][i - 1];
    for(int i = head[now]; i; i = t[i].nxt)
        if(t[i].to != fath)
            dfs(t[i].to, now);
}

ll LCA(ll x, ll y)
{   
    if(dep[x] < dep[y]) swap(x, y);
    for(int k = 22; k >= 0; --k)
        if(dep[fa[x][k]] >= dep[y])
            x = fa[x][k];
    if(x == y) return x;
    for(int k = 22; k >= 0; --k)
        if(fa[x][k] != fa[y][k])
            x = fa[x][k], y = fa[y][k];
    return fa[x][0];    
}

int main()
{
    n = read();
    m = read();
    s = read();
    for (int i = 1; i <= n; ++i)
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
        
    for (int i = 1; i < n; ++i)
    {
        ll x = read(), y = read();
        add(x, y);
        add(y, x);
    }
    
    dfs(s, 0);
    for (int i = 1; i <= m; ++i)
    {
        ll x = read(), y = read();
        printf("%lldn", LCA(x, y));
    }
    return 0;
}

最小生成树

Kruskal

前置:并查集

const ll N = 2e5 + 3;
ll n, m, fa[N], ans;

struct node{
    ll x, y, w;
}t[N];

bool cmp(node a, node b)
{
    return a.w < b.w;
}

ll F(ll x)
{
    if(fa[x] == x) return x;
    return fa[x] = F(fa[x]);
}

int main()
{
    n = read(), m = read();

    for(int i = 1; i <= m; ++i)
        t[i].x = read(), t[i].y = read(), t[i].w = read();
    sort(t + 1, t + m + 1, cmp);
    for(int i = 1; i <= n; ++i)
        fa[i] = i;

    for(int i = 1; i <= m; ++i)
    {
        if(F(t[i].x) == F(t[i].y)) continue;
        fa[F(t[i].x)] = F(t[i].y);
        ans += t[i].w;
    }

    for(int i = 2; i <= n; ++i)
    {
        if(F(i) != F(1)) // if Lian Tong
        {
            puts("orz");
            return 0;
        }
    }

    printf("%lldn", ans);
    return 0;
}

Prim

int ans, cnt, now = 1; //Prim
void prim()
{
    for (int i = 2; i <= n; ++i)
        dis[i] = MAXN;

    for (int i = head[1]; i; i = t[i].nxt)
        dis[t[i].to] = min(dis[t[i].to], t[i].w);

    while (++cnt < n)
    {
        int minn = MAXN;
        vis[now] = 1;
        for (int i = 1; i <= n; ++i)
        {
            if (vis[i])
                continue;
            if (minn > dis[i])
            {
                minn = dis[i];
                now = i;
            }
        }

        ans += minn;

        for (int i = head[now]; i; i = t[i].nxt)
        {
            int y = t[i].to, z = t[i].w;
            if (vis[y])
                continue;
            if (dis[y] > z)
            {
                dis[y] = z;
            }
        }
    }
}

拓扑排序

ll ans[100] ,cnt; //拓扑序列及其元素个数
ll deg[100];       //所有点的入度

void topsort()
{
    queue<ll> q;
    for (int i = 1; i <= n; ++i)
        if (deg[i] == 0) //寻找最开始入度就为0的点
            q.push(i);   //入队

    while (!q.empty())
    {
        ll x = q.front();
        q.pop();
        ans[++cnt] = x; //把队首的元素放进拓扑序列
        for (int i = head[x]; i; i = t[i].nxt)
        {
            ll y = t[i].to;    //寻找邻边
            if (--deg[y] == 0) //邻边的入度-1,并且判断减后的入度是否为0
                q.push(y);     //如果为0就入队
        }
    }
}

int main()
{
    n = read();
    m = read(); //点,边
    for (int i = 1; i <= m; ++i)
    {
        ll x = read(), y = read();
        add(x, y);
        deg[v]++; //入度++
    }

    topsort(); //拓扑排序

    if (cnt < n) //拓扑序列的元素个数小于点数,说明有环
        puts("有环");
    else
        puts("无环");

    for (int i = 1; i <= cnt; ++i)
        printf("%lld ", ans[i]); //输出拓扑序列

    return 0;
}

Tarjan

P3387 【模板】缩点

const ll N = 10002;

ll head[N], tott, w[N], n, m;
ll dfn[N], low[N], st[N], top, totx, cntscc;
ll belong[N], in[N], f[N];
bool vis[N], vis_out[N];

struct node{
    ll to, nxt;
} t[N * 10];

void add(ll u, ll v)
{
    t[++tott].nxt = head[u];
    t[tott].to = v;
    head[u] = tott;
}

struct Scc{
    ll w;
    vector<ll> to;
    // vector<ll> have;
} SCC[N * 10];

void Tarjan(ll now)
{
    low[now] = dfn[now] = ++totx;
    st[++top] = now;
    vis[now] = 1;
    for(int i = head[now]; i;i = t[i].nxt)
    {
        ll y = t[i].to;
        if(!dfn[y])
        {
            Tarjan(y);
            low[now] = min(low[now], low[y]);
        }
        else if(vis[y])
            low[now] = min(low[now], low[y]);
    }
    if(dfn[now] == low[now])
    {
        ll y;
        ++cntscc;
        while(y = st[top--])
        {
            vis[y] = 0;
            belong[y] = cntscc;
            SCC[cntscc].w += w[y];
            // SCC[cntscc].have.push_back(y); 存放此 SCC 里有哪些点
            if(now == y) break;
        }
    }
    return;
}

ll topo()
{
    queue<ll> q;
    for(int i = 1; i <= cntscc; ++i)
        for(int j = 0; j < SCC[i].to.size(); ++j)
            ++in[SCC[i].to[j]];
    for(int i = 1; i <= cntscc; ++i)
        if(in[i] == 0)
            q.push(i), f[i] = SCC[i].w;
        
    while(!q.empty())
    {
        ll x = q.front();
        q.pop();
        for(int j = 0; j < SCC[x].to.size(); ++j)
        {
            ll y = SCC[x].to[j];
            f[y] = max(f[y], f[x] + SCC[y].w);
            if(--in[y] == 0)
                q.push(y);
        }
    }
    ll ans = 0;
    for(int i = 1; i <= cntscc; ++i)
        ans = max(f[i], ans);
    return ans;
}

int main()
{
    n = read(), m = read();

    for(int i = 1; i <= n; ++i)
        w[i] = read(); 

    for(int i = 1; i <= m; ++i)
    {
        ll x = read(), y = read();
        if(x == y) continue; //判断重边
        add(x, y);
    }
    
    for(int i = 1; i <= n; ++i)
    {
        if(!dfn[i])
            Tarjan(i);
    }

    for(int i = 1; i <= n; ++i) // 重构图
        for(int j = head[i]; j; j = t[j].nxt)
        {
            ll y = t[j].to;
            if(belong[i] != belong[y])
                SCC[belong[i]].to.push_back(belong[y]);
        }

    printf("%lldn", topo());
    return 0;
}

字符串

快速读入

可以根据题目描述自行修改。

void Init()
{
    char ch;
    ch = getchar();
    while (ch < 'A' || ch > 'Z')
        ch = getchar();
    while (ch >= 'A' && ch <= 'Z')
    {
        A[++lena] = ch;
        ch = getchar();
    }

    while (ch < 'A' || ch > 'Z')
        ch = getchar();
    while (ch >= 'A' && ch <= 'Z')
    {
        B[++lenb] = ch;
        ch = getchar();
    }
}

KMP

模板题

(A) 为大串,(B) 为小串。

(next) 数组

void make_nxt()
{
    j = 0;
    for (int i = 2; i <= lenb; ++i)
    {
        while (B[i] != B[j + 1] and j)
            j = nxt[j];
        if (B[i] == B[j + 1])
            ++j;
        nxt[i] = j;
    }
}

匹配

void check()
{
    j = 0;
    for (int i = 1; i <= lena; i++)
    {
        while (A[i] != B[j + 1] and j)
            j = nxt[j];
        if (A[i] == B[j + 1])
            ++j;
        if (j == lenb)
        {
            printf("%lldn", i - lenb + 1);
            j = nxt[j];
        }
    }
}

AC自动机

大佬博客

模板1

判断多个模式串 (s_i) 是否在样本串 (t) 里出现过。

const int N = 1000005;
int n, len, tot, ch[N][30], End[N], fail[N];
char s[N];
queue<int> q;

void insert()
{
    len = strlen(s + 1);
    int now = 0;
    for (int i = 1; i <= len; i++)
    {
        int c = s[i] - 'a';
        if (!ch[now][c])
            ch[now][c] = ++tot;
        now = ch[now][c];
    }

    End[now]++;
}

void make_AC()
{
    for (int i = 0; i < 26; i++)
    {
        if (ch[0][i])
        {
            fail[ch[0][i]] = 0; //特殊处理,避免跳回自己
            q.push(ch[0][i]);
        }
    }
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
        {
            if (ch[x][i])
            {
                fail[ch[x][i]] = ch[fail[x]][i];
                q.push(ch[x][i]);
            }
            else
                ch[x][i] = ch[fail[x]][i];
        }
    }
}

int check_tot()
{
    len = strlen(s + 1);
    int now = 0, ans = 0;
    for (int i = 1; i <= len; i++)
    {
        now = ch[now][s[i] - 'a'];
        for (int t = now; t > 0 && End[t] != -1; t = fail[t])
        {
            ans += End[t];
            End[t] = -1;
        }
    }
    return ans;
}

int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s + 1);
        insert();
    }

    make_AC();

    scanf("%s", s + 1);
    printf("%dn", check_tot());

    return 0;
}

模板2

输出模式串最多出现的次数,输出出现次数最多的模式串。

const int N = 1000005;
int n, len, cnt, tot, maxn;
int ch[N][30], End[N], fail[N];
int num[210], sum[210];
char t[N], s[210][210];
queue<int> q;

void C()
{
    while (q.size())
        q.pop();
    maxn = 0;
    cnt = 0;
    tot = 0;
    memset(ch, 0, sizeof(ch));
    memset(sum, 0, sizeof(sum));
    memset(End, 0, sizeof(End));
    memset(ch, 0, sizeof(ch));
}

void insert(ll k)
{
    len = strlen(s[k] + 1);
    int now = 0;
    for (int i = 1; i <= len; ++i)
    {
        int c = s[k][i] - 'a';
        if (!ch[now][c])
            ch[now][c] = ++tot;
        now = ch[now][c];
    }
    End[now] = k;
}

void make_AC()
{
    for (int i = 0; i < 26; i++)
    {
        if (ch[0][i])
        {
            fail[ch[0][i]] = 0; //特殊处理,避免跳回自己
            q.push(ch[0][i]);
        }
    }
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
        {
            if (ch[x][i])
            {
                fail[ch[x][i]] = ch[fail[x]][i];
                q.push(ch[x][i]);
            }
            else
                ch[x][i] = ch[fail[x]][i];
        }
    }
}

void check()
{
    len = strlen(t + 1);
    int now = 0;
    for (int i = 1; i <= len; i++)
    {
        now = ch[now][t[i] - 'a'];
        for (int t = now; t > 0; t = fail[t])
        {
            ++sum[End[t]];
        }
    }
}

int main()
{
    while (1)
    {
        n = read();
        if (n == 0)
            return 0;

        for (int i = 1; i <= n; ++i)
        {
            scanf("%s", s[i] + 1);
            insert(i);
        }

        make_AC();
        scanf("%s", t + 1);
        check();

        for (int i = 1; i <= n; ++i)
        {
            if (sum[i] > maxn)
            {
                maxn = sum[i];
                cnt = 1;
                num[cnt] = i;
            }
            else if (sum[i] == maxn)
            {
                num[++cnt] = i;
            }
        }

        printf("%dn", maxn);

        for (int i = 1; i <= cnt; i++)
        {
            len = strlen(s[num[i]] + 1);
            for (int j = 1; j <= len; j++)
            {
                printf("%c", s[num[i]][j]);
            }
            puts("");
        }

        C();
    }
    return 0;
}

模板3

求出多个模式串 (s_i) 是否在样本串 (t) 里出现的次数。

const int N = 2000005;
int n, len, cnt, tot, maxn;
int ch[N][30], End[N], fail[N], in[N], ans[N];
int num[210], sum[210], Map[N], f[N];
char t[N], t2[N];
queue<int> q, q2;
vector<char> s[N];

void insert(int k)
{
    int now = 0;
    for (int i = 0; i < s[k].size(); i++)
    {
        int c = s[k][i] - 'a';
        if (!ch[now][c])
            ch[now][c] = ++tot;
        now = ch[now][c];
    }
    if (!End[now])
        End[now] = k;
    Map[k] = End[now];
}

void make_AC()
{
    for (int i = 0; i < 26; i++)
    {
        if (ch[0][i])
        {
            fail[ch[0][i]] = 0;
            q.push(ch[0][i]);
        }
    }
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
        {
            if (ch[x][i])
            {
                fail[ch[x][i]] = ch[fail[x]][i];
                in[fail[ch[x][i]]]++;
                q.push(ch[x][i]);
            }
            else
                ch[x][i] = ch[fail[x]][i];
        }
    }
}

void check()
{
    int now = 0, len = strlen(t + 1);
    for (int i = 1; i <= len; i++)
    {
        int c = t[i] - 'a';
        now = ch[now][c];
        f[now]++;
    }
}

void top()
{
    for (int i = 1; i <= tot; i++)
    {
        if (in[i] == 0)
            q2.push(i);
    }

    while (!q2.empty())
    {
        int x = q2.front();
        q2.pop();
        in[fail[x]]--;
        ans[End[x]] += f[x];
        f[fail[x]] += f[x];
        if (in[fail[x]] == 0)
        {
            q2.push(fail[x]);
        }
    }
}

int main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s", t2 + 1);
        len = strlen(t2 + 1);
        for (int j = 1; j <= len; ++j)
            s[i].push_back(t2[j]);
        insert(i);
    }
    make_AC();
    scanf("%s", t + 1);
    check();
    top();
    for (int i = 1; i <= n; i++)
        printf("%dn", ans[Map[i]]);

    return 0;
}

扩展 KMP

对于一个长度为 (n) 的字符串 (s),定义函数 (z[i]) 表示 (s)(s[i,n-1]) (即以 (s[i]) 开头的后缀)的最长公共前缀(LCP)的长度。(z) 被称作为 (s)Z 函数。特别地,(z[0]=[0])

本代码中 (z[0]=|B|)


const int MAXN = 2e7 + 5;
char B[MAXN], A[MAXN];
int lenb, lena, z[MAXN], ext[MAXN];

void getZ() //求 z 数组
{
    z[0] = lenb;
    int now = 0;
    while (now + 1 < lenb && B[now] == B[now + 1])
        now++;
    z[1] = now;
    int p0 = 1;
    for (int i = 2; i < lenb; ++i)
    {
        if (i + z[i - p0] < p0 + z[p0])
        {
            z[i] = z[i - p0]; //第一种情况
        }
        else
        {
            now = p0 + z[p0] - i;
            now = max(now, 0);
            while (now + i < lenb && B[now] == B[now + i])
                now++;
            z[i] = now;
            p0 = i;
        }
    }
}

void exkmp() //求 B 与 A 的每一个后缀的 LCP 长度数组
{
    int now = 0;
    while (now < lenb && now < lena && B[now] == A[now])
        now++;
    ext[0] = now;
    int p0 = 0;
    for (int i = 1; i < lena; ++i)
    {
        if (i + z[i - p0] < p0 + ext[p0])
            ext[i] = z[i - p0];
        else
        {
            now = p0 + ext[p0] - i;
            now = max(now, 0);
            while (now < lenb && now + i < lena && B[now] == A[now + i])
                now++;
            ext[i] = now;
            p0 = i;
        }
    }
}

int main()
{
    scanf("%s%s", A, B);
    lena = strlen(A); //文本串
    lenb = strlen(B); //模式串

    getZ();
    exkmp();

    得到 z[], p[];
    
}

STL

string

#include<cstring>
string s1,s2;

s1 + s2;    // 将两个字符串拼接
[cur];      // 访问下标
s1.size();  // 返回字符串长度
s1.append(s2);          // 将 s2 添加到 s1 末尾
s1.replace(pos, n, s2); // 删除从 pos 开始的 n 个字符,然后在 pos 处插入串 s
s1.erase(pos, n);       // 删除从 pos 开始的 n 个字符
s1.insert(pos, s2);     // 在 pos 位置插入字符串 s
s1.substr(start, len);  // 从 start 截取一个长度为 len 的字符串
s1.find(char,st = 0);  // 查找并返回从 start 开始的字符 ch 的位置
s1.rfind(ch);           //从末尾开始,查找并返回第一个找到的字符 ch 的位置
// 找不到则返回 -1

queue

先进先出

#include<queue>

queue<int> q; 
// priority_queue<int> q(从大到小排序);

q.empty();      // 判断队列是否为空
q.size();       // 返回队列长度
q.push(item);   // 对于 queue,在队尾压入一个新元素
                // 对于 priority_queue,在基于优先级的适当位置插入新元素
q.pop();        // 弹出队首元素

// queue only:
q.front();      //返回队首元素的值,但不删除该元素
q.back();       //返回队尾元素的值,但不删除该元素
     
// priority_queue only:
q.top();        //返回具有最高优先级的元素值,但不删除该元素

stack

先进后出

#include<set>
stack<int> s; 
stack<int, vector<int> > stk;  // 覆盖基础容器类型,使用vector实现stk
s.empty();      // 判断 stack 是否为空,为空返回 true,否则返回 false
s.size();       // 返回 stack 中元素的个数
s.pop();        // 删除栈顶元素,但不返回其值
s.top();        // 返回栈顶元素的值,但不删除此元素
s.push(item);   // 在栈顶压入新元素 item

list

链表

list<ll> l, l2;
list<ll>::iterator it;

/* 操作 */
l.clear();      // 清空
l.insert(it, 0);// 在迭代器前面插入一个元素,迭代器指向原来的元素
l.erase(it);    // 删除迭代器指向的元素
l.remove(0);    // 在 list 删除某一种元素(全删)
l.push_back(0); // 在 list 的末尾添加一个元素   
l.push_front(0);// 在 list 的头部添加一个元素 
l.pop_back();   // 删除最后一个元素 
l.pop_front();  // 删除第一个元素 
l.merge(l2);    // 合并两个 list 
l.reverse();    // 把 list 的元素倒转 
l.sort();       // 给 list 排序 
l.swap(l2);     // 交换两个 list 
l.unique();     // 删除 list 中重复的元素

/* 查询 */
l.begin();      // 返回指向第一个元素的迭代器 
l.end();        // 返回末尾的迭代器 
l.front();      // 返回第一个元素 
l.back();       // 返回最后一个元素 
l.empty();      // 如果 list 是空的则返回 1
l.size();       // 返回 list 中的元素个数 

/* 遍历 */
for(it = l.begin(); it != l.end(); ++it)
    cout<<*it<<' ';

set

自动从小到大排序,自动去重。

set<int> s;
// multiset<int> s (不去重)
set<int>::const_iterator iter; // 迭代器 

s.insert();   // 插入
s.erase();    // 若参数为元素值,则删除所有该元素值
              // 若参数为迭代器,则删除该迭代器指向的值
s.empty();    // 判断 set 是否为空,为空返回 true,否则返回 false
s.count();    // 返回某个值元素的个数
s.clear();    // 清除所有元素
s.find();     // 查找某元素,找到则返回其迭代器,否则返回 s.end()
s.begin();    // 返回指向第一个元素的迭代器
--s.end();    // 返回指向最后一个元素的迭代器
*s.begin();   // 返回指向第一个元素的值
*--s.end();   // 返回指向最后一个元素的值
              // 区间形式为 [ begin , end ) ,所以 end 要自减
s.size();     // 返回集合中元素的个数
*s.lower_bound(k);    // 返回第一个大于等于k的元素值
*s.upper_bound(k);    // 返回第一个大于k的元素值 (后继)
              // 如果没有符合条件的值,则输出 s.size()

/* 遍历 */
for(iter = s.begin() ; iter != s.end() ; ++iter)
    cout<<*iter<<" "; // 使用迭代器遍历 

unordered_set

不排序,(O(1)) 查找

#include <unordered_set>
// #include <unordered_multiset>
unordered_set<ll> s;
// unordered_multiser<ll> s;

s.insert(); // 在开头插入某元素
s.find();   // 查找,返回迭代器
s.count();  // 返回某个值元素的个数

/* 遍历 */
for(iter = s.begin() ; iter != s.end() ; ++iter)
    cout<<*iter<<" "; 
// 注意:新插入的元素遍历时先被扫到。

map

#include<map>
map<string, int> m;// string 是 key,int 是 value。

/* 基本操作 */
m.size();   // 输出元素个数
m.empty();  // 如果 map 为空则返回 true
m.clear();  // 删除所有元素

/* 插入 */
m["AKIOI"] = 10;
m.insert(make_pair("AKIOI", 10));

/* 修改 */
m["AKIOI"] = 10;
m.find("AKIOI")->second = ...;

/* 查找 */
m["AKIOI"];
m.find("AKIOI")->second;

/* 遍历 */
它会按照 key 排序
for(auto it = mp.begin(); it != mp.end(); ++it) 
    cout << it->second << ' ';

multimap

#include <map>
multimap<int, string> mp; // 可重

mp.size(), mp.empty(), mp.clear(); // 常规操作
mp.count(k) // 找 key 为 k 的个数
mp.find(k)  // 返回第一个插入的 k 的迭代器
mp.erase(k) // 删除所有键值为 k 的元素

/* 插入 */
mp.insert(make_pair(int, string)); // 只能用 make_pair 构造键值对

/* 修改 */
m.find(k)->second = ...; // 修改第一个插入的 key 为 k 的
for(auto it = mp.find(k); it->first == k; ++it) // 修改 key 为 k,值为自己选的
    if(it->second == "I") it->second = "Love"; 

/* 查找 */
mp.find(k)->second;

/* 遍历 */
for(auto it = mp.begin(); it != mp.end(); ++it) 
    cout << it->second << ' ';

unordered_map

#include<unordered_map>
用法:与 map 差别不大。
优点:因为内部实现了哈希表,因此其查找速度非常的快
缺点:哈希表的建立比较耗费时间
适用处:对于查找问题,unordered_map会更加高效一些,因此遇到查找问题,常会考虑一下用 unordered_map

bitset

bitset<100> b;
bitset<100> f;

b = 10, f = 11;
b[0]; // 访问某一位

/* 相同大小的 bitset 可以进行运算符操作 */
/* == != & &= | |= ^ ^= ~ << <<= >> >>=  */

b.count();  // 返回 1 的数量
b.size();   // 返回 bitset 的大小
b.any();    // 若有 1, 返回 1
b.none();   // 若无 1, 返回 1
b.all();    // 若全是 1, 返回 1
b.set();    // 全部设为 1
b.set(0, 0);// 将第 pos 位设为 k
b.reset();  // 全部设为 0
b.flip();   // 翻转每一位
b.flip(0);  // 翻转某一位

rope

rope 的复制操作是 (O(log n)) 的,可以较轻松地实现可持久化。

想要使用 rope,需要在头文件中加入两行:

#include <ext/rope>
using namespace __gnu_cxx;

定义字符串类型的 rope,叫做 crope,要这样定义:

crope a;

支持的操作:

a.push_back(x);  // 在 a 的末尾添加字符串 x
a.insert(k, x);  // 在 a 的第 k 个字符后加入字符串 x
a.erase(k, x);   // 在 a 的第 k 个字符后删除 x 个字符
a.replace(k, x); // 将 a 的第 k 个字符后 x 的长度个字符删除,并插入 x
a.substr(k, x);  // 获取 a 的第 k 个字符后的长度为 x 的字符串
a.at(k);         // 获取 a 的第 k 个字符(从 0 开始)

程序员灯塔
转载请注明原文链接:OI 基础模板
喜欢 (0)