头像

Mrhh

西南科技大学


访客:22962

离线:7天前


活动打卡代码 AcWing 1277. 维护序列

Mrhh
1个月前

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, p, m;
int w[N];
struct Node
{
    int l, r; // 存的是节点的区间左右端点的编号
    int sum, add, mul;
}tr[N * 4];

void pushup(int u)
{
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}

// 合并区间加和区间乘两个操作到一个函数里 加: eval(tr[i], add, 1), 乘: eval(tr[i], 0, mul)
void eval(Node &t, int add, int mul)
{
    t.sum = ((LL)t.sum * mul + (LL)(t.r - t.l + 1) * add) % p;
    t.mul = (LL)t.mul * mul % p;
    /* *** 
    对于一个序列来说, 操作之前其一直都是原序列没有变过. 所以这里的加需要累加.
    例如, 原序列为 1 2 3, 那么假如我们先将其整体加上10, 当我们后面对原序列乘上一个数时, 加的10就要**翻倍**了, 对于初始序列来说!!!
    */
    t.add = ((LL)t.add * mul + add) % p;
}

void pushdown(int u) // 下传懒标记
{
    eval(tr[u << 1], tr[u].add, tr[u].mul);
    eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
    tr[u].add = 0, tr[u].mul = 1;
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r], 0, 1};
    else
    {
        tr[u] = {l, r, 0, 0, 1};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int add, int mul)
{
    if (tr[u].l >= l && tr[u].r <= r) eval(tr[u], add, mul);
    else
    {
        pushdown(u); // 区间没被包含, 分裂区间下传懒标记, 见分享线段树详解.
        int mid = tr[u].l + tr[u].r >> 1;
        // 下面两行代码与查询操作中为何操作的区间为(l, r), 见上图
        if (l <= mid) modify(u << 1, l, r, add, mul);
        if (r > mid) modify(u << 1 | 1, l, r, add, mul);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(u); // 区间没被包含, 分裂区间下传懒标记(对于查询修改操作没有涉及的区间特性的查询)
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if (l <= mid) sum = query(u << 1, l, r);
    if (r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p;
    return sum;
}

int main()
{
    scanf("%d%d", &n, &p);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);

    scanf("%d", &m);
    while (m -- )
    {
        int t, l, r, d;
        scanf("%d%d%d", &t, &l, &r);
        if (t == 1)
        {
            scanf("%d", &d);
            modify(1, l, r, 0, d);
        }
        else if (t == 2)
        {
            scanf("%d", &d);
            modify(1, l, r, d, 1);
        }
        else printf("%d\n", query(1, l, r));
    }

    return 0;
}



Mrhh
1个月前

树状数组只能维护前缀区间的特性, 任意区间不行.

Analsis

  • 区间加减(懒标记只有在需要将区间所有数改变为某个数的时候才必须用, 当对区间加减操作时, 可以用线段树维护原数组的差分数组, 实现单点修改, 最后求一遍差分数组的前缀和就为修改后的数组了, 懒标记能不用尽量不用, 因为容易错且复杂)
  • 将一个区间分为两半, 两半的最大公约数的最大公约数为整个区间的最大公约数.

Thoughts

  • 区间修改之后, (a, b, c)与(a + x, b + x, c + x)无甚关系, 但是如果我们将区间修改边为单点修改(一个数的gcd就是其自己), 然后递归更新gcd.

Solutions

根据gcd(a, b, c) = gcd(a - 0, b - a, c - b), 即差分序列的gcd就为原序列的gcd, 将序列转换其对应的差分序列, 对差分序列建线段树, 这样我们就将区间修改变为了单点修改, gcd(差分区间) = gcd(原序列区间), 即无需写lazy标记 – 单点修改, 区间查询.
而对于gcd(a, b - a, c - b)中a的值, 对于差分序列求原序列的元素值, 我们只需要求一个前缀和即为该元素.

总结: 我们用线段树维护原序列的差分序列的两个特性: 前缀区间和(当然也可以用我们前面学到的树状数组来维护前缀区间和)与区间gcd

Segment tree Accepted Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

int n, m;
LL w[N];
struct Node
{
    int l, r;
    LL sum, d;
}tr[N * 4];

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

void pushup(Node &u, Node &l, Node &r)
{
    u.sum = l.sum + r.sum;
    u.d = gcd(l.d, r.d);
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    if (l == r)
    {
        LL b = w[r] - w[r - 1];
        tr[u] = {l, r, b, b};
    }
    else
    {
        tr[u].l = l, tr[u].r = r;
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, LL v)
{
    if (tr[u].l == x && tr[u].r == x)
    {
        LL b = tr[u].sum + v;
        tr[u] = {x, x, b, b};
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

/*
对于一个点来说, 我们直接返回就可.
对于一个区间来说, 它必定会被分成两半, 返回的时候我们用一个Node res记下查询区间的特性.
*/

// 形参u: 是指区间节点的编号
Node query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else
        {
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]);
    build(1, 1, n);

    int l, r;
    LL d;
    char op[2];
    while (m -- )
    {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'Q')
        {
            auto left = query(1, 1, l), right = query(1, l + 1, r);
            printf("%lld\n", abs(gcd(left.sum, right.d)));
        }
        else
        {
            scanf("%lld", &d);
            modify(1, l, d);
            if (r + 1 <= n) modify(1, r + 1, -d);
        }
    }

    return 0;
}

详解 写得实在是太好了



活动打卡代码 AcWing 368. 银河

Mrhh
1个月前

这道题和差分约束的糖果是一样的一道题, 因为spfa可能被卡成$O(nm)$, 但是tarjan算法能保证稳定线性, 所以这道题的正解应该是tarjan算法.

Analysis

首先, 我们先建图, 类似差分约束, 根据不等式和宿求最少建图.
然后, 最少就是求最长路, 因为只要大于最大值, 就能满足所有的不等式的约束条件.
然后, 最长路无解为存在正环, 建图所有边都是正权, 并且有向图的所有的环必定存在于有向图的强连通分量中, 故而, 我们只需要求出所有的强连通分量, 如果其中有一条边为正权, 那么就存在正环无解.
最后, 如果有解, 求出总亮度即可.

Time complexity

$O(n)$

Accepted Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, M = 600010;

int n, m;
int h[N], hs[N], e[M], ne[M], w[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, size[N];
int dist[N];

void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            size[scc_cnt] ++ ;
        } while (y != u);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);

    for (int i = 1; i <= n; i ++ ) add(h, 0, i, 1); // xi >= 1 -> xi >= x0 + 1

    while (m -- )
    {
        int t, a, b;
        scanf("%d%d%d", &t, &a, &b);
        if (t == 1) add(h, b, a, 0), add(h, a, b, 0);
        else if (t == 2) add(h, a, b, 1);
        else if (t == 3) add(h, b, a, 0);
        else if (t == 4) add(h, b, a, 1);
        else add(h, a, b, 0);
    }

    tarjan(0); // 0这个超级源点能走完所有的点, 所以无需for

    bool success = true;
    for (int i = 0; i <= n; i ++ )
    {
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a == b)
            {
                if (w[j] > 0) // 存在正环
                {
                    success = false;
                    break;
                }
            }
            else add(hs, a, b, w[j]);
        }
        if (!success) break;
    }

    if (!success) puts("-1");
    else
    {
        for (int i = scc_cnt; i; i -- )
        {
            for (int j = hs[i]; ~j; j = ne[j])
            {
                int k = e[j];
                dist[k] = max(dist[k], dist[i] + w[j]);
            }
        }

        LL res = 0;
        for (int i = 1; i <= scc_cnt; i ++ ) res += (LL)dist[i] * size[i]; // 求总亮度

        printf("%lld\n", res);
    }

    return 0;
}



Mrhh
1个月前

Analysis

  • u→v 或 v→u

    对于一个图中任意两点u, v, 可以只有一个上面关系, 也可以两个都有 – 半连通 强连通的必然是半连通的

  • 导出子图

    从一个图中选出一些点, 并将图中边的两个顶点在选出的点集中的边加入选出点集, 形成的图就称为该图的导出子图

  • 半连通子图

    对于子图来说, 是半连通的, 我们就称其为半连通子图.

  • 最大半连通子图

    对于一个图的所有半连通子图来说, 节点数最多的图, 我们称其为最大半连通子图.

Solution

对scc缩点, 求dag的最长链(不能分叉)即为最大半联通子图, 注意, 如果不同方案是指的有一个点不同, 由于导出子图的定义, 需将两个点之间在原图中的所有边选出来, 所以我们dag之间的边, 只有两种情况, 有或是没有, 所以最大半连通子图, 不会有点相同, 边不同的情况的. 所以算方案数的时候, 对于重边, 我们应该判重为一条边, 不要重复累加.

Accepted Code

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 200010, M = 2000010;

int n, m, mod;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], tt;
bool in_stk[N];
int id[N], sz[N], scc_cnt; // sz数组维护每个强连通分量中的节点数
unordered_set<int> uset[N];
int dist[N], cnt[N]; // 最长路与方案数

void add(int h[], int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++tt] = u, in_stk[u] = true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (in_stk[j]) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int v;
        do {
            v = stk[tt--];
            in_stk[v] = false;
            id[v] = scc_cnt;
            sz[scc_cnt]++;
        } while (v != u);
    }
}

int main() {
    cin >> n >> m >> mod;
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(h, a, b);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = h[i]; ~j; j = ne[j]) {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b && !uset[a].count(b)) {
                add(hs, a, b);
                uset[a].insert(b);
            }
        }
    }
    for (int i = scc_cnt; i; i--) {
        if (!dist[i]) {
            dist[i] = sz[i]; // 到假想超级源点的距离, 将点权值(scc中的节点数量), 转化为边权值
            cnt[i] = 1;
        }
        for (int j = hs[i]; ~j; j = ne[j]) {
            int k = e[j];
            if (dist[k] < dist[i] + sz[k]) {
                dist[k] = dist[i] + sz[k];
                cnt[k] = cnt[i];
            } else if (dist[k] == dist[i] + sz[k]) {
                (cnt[k] += cnt[i]) %= mod;
            }
        }
    }
    int maxv = 0, max_cnt = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (dist[i] > maxv) {
            maxv = dist[i];
            max_cnt = cnt[i];
        } else if (dist[i] == maxv) {
            (max_cnt += cnt[i]) %= mod;
        }
    }
    printf("%d\n%d\n", maxv, max_cnt);
    return 0;
}


分享 树的遍历

Mrhh
1个月前

这三种遍历顺序主要取决于, 当前节点遍历的顺序位置.

先序遍历

当前节点 -> 左儿子 -> 右儿子

中序遍历(将树映射到一维上面)

左儿子 -> 当前节点 -> 右儿子

后序遍历

左儿子 -> 右儿子 -> 当前节点



活动打卡代码 AcWing 352. 闇の連鎖

Mrhh
1个月前

Analysis

  • Dark 有 N – 1 条主要边,并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。
根据题目描述, 主要边所构成的就是一棵树. 其余边就是非树边.

那么如何解决将树的两点之间的所有边加上一个权值? -> 树上差分

给树上两点之间的所有边加上一个权值.

  • 树的差分数组的含义: d[i]表示i与其父节点之间的边, 而d[i]的值为以i为根的子树中所有边权之和.
  • 操作实现: 我们给x, y的所有边+c $\rightarrow$ d[x] + c, d[y] + c, d[p] - 2c. (p为x, y的最近公共祖先)

Accepted Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][17];
int d[N];
int q[N];
int ans;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// LCA预处理
void bfs()
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;
    int hh = 0, tt = 0;
    q[0] = 1;

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                q[ ++ tt] = j;
                fa[j][0] = t;
                for (int k = 1; k <= 16; k ++ )
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

// 求最近公共祖先
int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 16; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 16; k >= 0; k -- )
        if (fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}

// 树上差分求前缀和, 得到树边的边权值
int dfs(int u, int father)
{
    int res = d[u];
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != father)
        {
            int s = dfs(j, u); // 差分数组的含义
            if (s == 0) ans += m;
            else if (s == 1) ans ++ ;
            res += s; // 差分求前缀和 -> 原数组(求出树边权值)
        }
    }

    return res; // 累积
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    bfs();

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);
        d[a] ++, d[b] ++, d[p] -= 2;
    }
    dfs(1, -1);
    printf("%d\n", ans);

    return 0;
}


活动打卡代码 AcWing 356. 次小生成树

Mrhh
1个月前

Accepted Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, M = 300010, INF = 0x3f3f3f3f;

int n, m;
struct Edge
{
    int a, b, w;
    bool used; // 判断非树边
    bool operator< (const Edge &t) const
    {
        return w < t.w;
    }
}edge[M];
int p[N]; // kruscal的p数组
int h[N], e[M], w[M], ne[M], idx; // 存最小生成树
int depth[N], fa[N][17], d1[N][17], d2[N][17];
int q[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 求出最小生成树和次大边(非树边)集合
LL kruskal()
{
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    sort(edge, edge + m);
    LL res = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = find(edge[i].a), b = find(edge[i].b), w = edge[i].w;
        if (a != b)
        {
            p[a] = b;
            res += w;
            edge[i].used = true;
        }
    }

    return res;
}

// 存最小生成树
void build()
{
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
        if (edge[i].used)
        {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            add(a, b, w), add(b, a, w);
        }
}

// 预处理: 1. 最小生成树中任意两点之间边集中的最大权值边的权值, 次大权值边的权值. 2. LCA的depth数组. 3. LCA的fa数组
void bfs()
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;
    q[0] = 1;
    int hh = 0, tt = 0;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                q[ ++ tt] = j;
                fa[j][0] = t;
                d1[j][0] = w[i], d2[j][0] = -INF; // 一条边 由于是在一颗树中, 所以是不存在重边和环的, 所以d1[j][0] = w[i]
                for (int k = 1; k <= 16; k ++ )
                {
                    int anc = fa[j][k - 1];
                    fa[j][k] = fa[anc][k - 1];
                    // j ~ k 的最大权值边的权值 = max(j ~ k - 1的最大权值边, k - 1 ~ k的最大权值边的权值)
                    int distance[4] = {d1[j][k - 1], d2[j][k - 1], d1[anc][k - 1], d2[anc][k - 1]};
                    d1[j][k] = d2[j][k] = -INF;
                    for (int u = 0; u < 4; u ++ )
                    {
                        int d = distance[u];
                        if (d > d1[j][k]) d2[j][k] = d1[j][k], d1[j][k] = d;
                        else if (d != d1[j][k] && d > d2[j][k]) d2[j][k] = d;
                    }
                }
            }
        }
    }
}


// 求出次小生成树新加边与去掉边的差值
int lca(int a, int b, int w)
{
    static int distance[N * 2]; // 存储a, b之间所有的边 -- 边集
    int cnt = 0;
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 16; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
        {
            distance[cnt ++ ] = d1[a][k];
            distance[cnt ++ ] = d2[a][k];
            a = fa[a][k];
        }
    if (a != b)
    {
        for (int k = 16; k >= 0; k -- )
            if (fa[a][k] != fa[b][k])
            {
                // a, b都在跳
                distance[cnt ++ ] = d1[a][k];
                distance[cnt ++ ] = d2[a][k];
                distance[cnt ++ ] = d1[b][k];
                distance[cnt ++ ] = d2[b][k];
                a = fa[a][k], b = fa[b][k];
            }
        distance[cnt ++ ] = d1[a][0];
        distance[cnt ++ ] = d1[b][0];
    }

    // 求出a, b之间的最大边权与次大边权
    int dist1 = -INF, dist2 = -INF;
    for (int i = 0; i < cnt; i ++ )
    {
        int d = distance[i];
        if (d > dist1) dist2 = dist1, dist1 = d;
        else if (d != dist1 && d > dist2) dist2 = d;
    }

    if (w > dist1) return w - dist1;
    if (w > dist2) return w - dist2;
    return INF;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edge[i] = {a, b, c};
    }

    LL sum = kruskal(); // 最小生成树的边权之和
    build();
    bfs();

    LL res = 1e18;
    for (int i = 0; i < m; i ++ )
        if (!edge[i].used)
        {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            res = min(res, sum + lca(a, b, w));
        }
    printf("%lld\n", res);

    return 0;
}


活动打卡代码 AcWing 393. 雇佣收银员

Mrhh
1个月前

Analysis

无标题.png

  • 同时对于s24这个点来说, 由于我们是枚举它的值, 所以每次的s24的值都是确定的, 不像其他的s[i]是不确定的. 即s24 = c $\rightarrow$ s24 >= c && s24 <= c $\rightarrow$ s24 >= c + s0 && s0 >= s24 - c, 所以我们需要从0连一条权值为c的边, 同时从s24向s0连一条长度为-c的边.

Accepted Code

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30, M = 100, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], w[M], ne[M], idx;
int r[N], num[N];
int dist[N];
int q[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void build(int c)
{
    memset(h, -1, sizeof h);
    idx = 0;
    add(0, 24, c), add(24, 0, -c);
    for (int i = 1; i <= 7; i ++ ) add(i + 16, i, r[i] - c);
    for (int i = 8; i <= 24; i ++ ) add(i - 8, i, r[i]);
    for (int i = 1; i <= 24; i ++ )
    {
        add(i, i - 1, -num[i]);
        add(i - 1, i, 0);
    }
}

bool spfa(int c)
{
    build(c);

    memset(dist, -0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);

    int hh = 0, tt = 1;
    dist[0] = 0;
    q[0] = 0;
    st[0] = true;

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= 25) return false;
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    return true;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        for (int i = 1; i <= 24; i ++ ) cin >> r[i];
        cin >> n;
        memset(num, 0, sizeof num);
        for (int i = 0; i < n; i ++ )
        {
            int t;
            cin >> t;
            num[t + 1] ++ ; // 每个时间点的申请的工人人数
        }

        bool success = false;
        for (int i = 0; i <= 1000; i ++ )
            if (spfa(i))
            {
                cout << i << endl;
                success = true;
                break;
            }

        if (!success) puts("No Solution");
    }

    return 0;
}


活动打卡代码 AcWing 1053. 修复DNA

Mrhh
1个月前

类似题目:
1. hdu 2243

降维打击:
1. 安徽19省赛 密信
2. acwing设计密码, GT考试

两个注意点:

  • 一个串的尾节点被标记了, 那么含其的其他串的对应尾节点也需要被标记
  • 含已被标记串的串的对应尾节点已经被标记了, 那么匹配到此终止, 只能选择其他分支. (因为标记是在建trie的同时进行的, 所以所有被标记节点都是叶子节点)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int tr[N][4], dar[N], idx;
int q[N], ne[N];
char str[N];

int f[N][N]; // 母串到了第i个位置, 此时匹配到了trie图的第j个位置的最小替换字母个数.

int get(char c)
{
    if (c == 'A') return 0;
    if (c == 'T') return 1;
    if (c == 'G') return 2;
    return 3;
}

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int t = get(str[i]);
        if (tr[p][t] == 0) tr[p][t] = ++ idx;
        p = tr[p][t];
    }
    dar[p] = 1; // 题目要求子串集合中, 对于母串一个单词都不能匹配到, 所以我们将单词的尾节点标记, 这样就可以了.
}

void build()
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 4; i ++ )
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = 0; i < 4; i ++ )
        {
            int p = tr[t][i];
            if (!p) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                q[ ++ tt] = p;
                dar[p] |= dar[ne[p]]; // 注意点1, 将包含已标记字串的其他串对应位置的尾节点标记上.
            }
        }
    }
}

int main()
{
    int T = 1;
    while (scanf("%d", &n), n)
    {
        memset(tr, 0, sizeof tr);
        memset(dar, 0, sizeof dar);
        memset(ne, 0, sizeof ne);
        idx = 0;

        for (int i = 0; i < n; i ++ )
        {
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str + 1);
        m = strlen(str + 1);

        memset(f, 0x3f, sizeof f);
        f[0][0] = 0;
        for (int i = 0; i < m; i ++ ) // 母串
            for (int j = 0; j <= idx; j ++ )
                for (int k = 0; k < 4; k ++ )
                {
                    int t = get(str[i + 1]) != k; // 是否需要更改, 一样的话直接往下走
                    int p = tr[j][k]; // 儿子节点的编号
                    // 与kmp中j < len一样, 匹配长度不能越界
                    if (!dar[p]) f[i + 1][p] = min(f[i + 1][p], f[i][j] + t);
                }

        int res = 0x3f3f3f3f;
        for (int i = 0; i <= idx; i ++ ) res = min(res, f[m][i]); // 必不可能母串中还有给定子串集合中的子串, 因为到了单词的尾节点我们就停止匹配了. 所以我们只需要将长度为m的母串集合中取个min即为答案.

        if (res == 0x3f3f3f3f) res = -1;
        printf("Case %d: %d\n", T ++ , res);
    }

    return 0;
}


活动打卡代码 AcWing 1285. 单词

Mrhh
1个月前

无标题.png

时间复杂度

$O(n)$

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n;
int tr[N][26], cnt[N], idx;
int q[N], ne[N];
char str[N];
int id[210]; // 200个单词的尾节点编号

void insert(int x)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int t = str[i] - 'a';
        if (!tr[p][t]) tr[p][t] = ++ idx;
        p = tr[p][t];
        cnt[p] ++ ; // 有多少个单词在该点有前缀
    }
    id[x] = p;
}

// 建fail指针
void build()
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i ++ )
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = 0; i < 26; i ++ )
        {
            int &p = tr[t][i];
            if (!p) p = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                q[ ++ tt] = p;
            }
        }
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ )
    {
        scanf("%s", str);
        insert(i);
    }

    build();

    for (int i = idx - 1; i >= 0; i -- ) cnt[ne[q[i]]] += cnt[q[i]]; // 原串ne[q[i]], 其他前缀q[i], 是指cnt[ne[q[i]]](原串在所有单词中的数量)加上原串为其他前缀的后缀的其他前缀的数量.

    for (int i = 0; i < n; i ++ ) printf("%d\n", cnt[id[i]]);

    return 0;
}