头像

yxc的复读机之qxz


访客:5659

离线:9天前


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

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

using namespace std;

const int N = 1010;
int tr[N][4], ne[N], dar[N], idx;
int q[N];
char str[N];
int f[N][N];

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

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int t = get(str[i]);
        if (!tr[p][t]) 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) {
                p = tr[ne[t]][i];
            } else {
                q[++tt] = p;
                ne[p] = tr[ne[t]][i];
                dar[p] |= dar[ne[p]];
            }
        }
    }
}

int main()
{
    int T = 1;
    int n;
    while (scanf("%d", &n), n) {
        memset(tr, 0, sizeof tr);
        memset(ne, 0, sizeof ne);
        memset(dar, 0, sizeof dar);
        idx = 0;
        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            insert();
        }

        build();
        memset(f, 0x3f, sizeof f);
        f[0][0] = 0;
        scanf("%s", str + 1);
        int m = strlen(str + 1);
        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];
                    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]);
        if (res == 0x3f3f3f3f) res = -1;
        printf("Case %d: %d\n", T++, res);
    }
    return 0;
}


活动打卡代码 AcWing 1285. 单词

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 1e6 + 10;
int tr[N][26], f[N], ne[N], idx;
int q[N], id[N];
char str[N];

void insert(int x)
{
int p = 0;
for (int i = 0; str[i]; i) {
int &t = tr[p][str[i] - ‘a’];
if (!t) t =
idx;
p = t;
f[p]++;
}
id[x] = p;
}

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 &s = tr[t][i];
if (!s) {
s = tr[ne[t]][i];
} else {
ne[s] = tr[ne[t]][i];
q[++tt] = s;
}
}
}
}

int main()
{
int n;
scanf(“%d”, &n);
for (int i = 0; i < n; i) {
scanf(“%s”, str);
insert(i);
}
build();
for (int i = idx - 1; i >= 0; i–) {
f[ne[q[i]]] += f[q[i]];
}
for (int i = 0; i < n; i
) printf(“%d\n”, f[id[i]]);
return 0;
}
```



活动打卡代码 AcWing 1052. 设计密码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 55, mod = 1e9 + 7;
int f[N][N], ne[N], trans[N][26];
char str[N];
int n;

int main()
{
    cin >> n >> str + 1; 
    int m = strlen(str + 1);
    for (int i = 2, j = 0; i <= m; i++) {
        while (j && str[i] != str[j + 1]) j = ne[j];
        if (str[i] == str[j + 1]) j++;
        ne[i] = j;
    }

    // 先预处理状态机所有可能的转移路径

    for (int i = 0; i < m; i++) {
        for (int j = 'a'; j <= 'z'; j++) {
            int t = i;
            while (t && str[t + 1] != j) t = ne[t];
            if (str[t + 1] == j) t++;
            trans[i][j - 'a'] = t;
        }
    }

    // f[i][j]代表字符串长度为i且状态机状态为j的方案数
    // 初始状态有f[0][0] = 1, f[0][1 ~ (m - 1)] = 0

    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 'a'; k <= 'z'; k++) {
                int t = trans[j][k - 'a'];
                if (t < m) {
                    f[i][t] = (f[i][t] + f[i - 1][j]) % mod;
                }
            }
        }
    }

    int res = 0;
    for (int i = 0; i < m; i++) res = (res + f[n][i]) % mod;
    cout << res << endl;

    return 0;
}

作者:yxc的复读机之qxz
链接:https://www.acwing.com/solution/content/13198/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



算法1

(kmp状态机 + dp)

定义:
* f[i][j]代表字符串长度为i且状态机状态为j的方案数。
初始状态有f[0][0] = 1, f[0][1 ~ (m - 1)] = 0
* 状态转移方程为:
markdown学好了再写,具体参考代码,其实只要搞清楚转态定义了,后面的就不难了。

时间复杂度

O(26 * N * N)

参考文献

参考了这位大佬解答里面的点睛之笔,茅塞顿开。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 55, mod = 1e9 + 7;
int f[N][N], ne[N], trans[N][26];
char str[N];
int n;

int main()
{
    cin >> n >> str + 1; 
    int m = strlen(str + 1);
    for (int i = 2, j = 0; i <= m; i++) {
        while (j && str[i] != str[j + 1]) j = ne[j];
        if (str[i] == str[j + 1]) j++;
        ne[i] = j;
    }

    // 先预处理状态机所有可能的转移路径

    for (int i = 0; i < m; i++) {
        for (int j = 'a'; j <= 'z'; j++) {
            int t = i;
            while (t && str[t + 1] != j) t = ne[t];
            if (str[t + 1] == j) t++;
            trans[i][j - 'a'] = t;
        }
    }

    // f[i][j]代表字符串长度为i且状态机状态为j的方案数
    // 初始状态有f[0][0] = 1, f[0][1 ~ (m - 1)] = 0

    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 'a'; k <= 'z'; k++) {
                int t = trans[j][k - 'a'];
                if (t < m) {
                    f[i][t] = (f[i][t] + f[i - 1][j]) % mod;
                }
            }
        }
    }

    int res = 0;
    for (int i = 0; i < m; i++) res = (res + f[n][i]) % mod;
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1184. 欧拉回路

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

using namespace std;

const int N = 100010, M = 400010;
int h[N], e[M], ne[M], idx;
int vis[M], ans[M], cnt;
int t, n, m;
int din[N], dout[N];

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

void dfs(int u) 
{
    for (int &i = h[u]; ~i; ) {
        int v = e[i];
        // cout << i << " " << v << endl;
        if (vis[i]) {
            i = ne[i];
            continue;
        }
        vis[i] = true;
        if (t == 1) vis[i ^ 1] = true;
        int temp;
        if (t == 1) {
            temp = i / 2 + 1;
            if (i & 1) temp = -temp;
        } else {
            temp = i + 1;
        }
        i = ne[i];
        dfs(v);
        ans[++cnt] = temp;
    }
}

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

    bool flag = true;
    if (t == 1) {
        for (int i = 1; i <= n; i++) {
            if ((din[i] + dout[i]) & 1) {
                flag = false;
                break;
            }
        }
    } else {
        for (int i = 1; i <= n; i++) {
            if (din[i] != dout[i]) {
                flag = false;
                break;
            }
        }
    }
    if (!flag) {
        puts("NO");
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        if (h[i] != -1) {
            dfs(i);
            break;
        }
    }
    if (cnt < m) {
        puts("NO");
        return 0;
    }

    puts("YES");
    for (int i = cnt; i; i--) printf("%d ", ans[i]);
    puts("");
    return 0;
}



活动打卡代码 AcWing 396. 矿场搭建

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

using namespace std;

typedef unsigned long long ULL;

const int N = 1010, M = 1010;
int h[N], ne[M], e[M], idx;
int dfn[N], low[N], stk[N], timestamp;
vector<int> dcc[N];
int dcc_cnt, top;
bool cut[N];
int root;
int n, m;

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

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u;
    if (u == root && h[u] == -1) {
        dcc_cnt++;
        dcc[dcc_cnt].push_back(u);
        return;
    }
    int cnt = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                cnt++;
                if (u != root || cnt > 1) cut[u] = true;
                dcc_cnt++;
                int y;
                do {
                    y = stk[top--];
                    dcc[dcc_cnt].push_back(y);
                } while (y != v);
                dcc[dcc_cnt].push_back(u);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main()
{
    int T = 1;
    while (cin >> m, m) {
        for (int i = 1; i <= dcc_cnt; i++) dcc[i].clear();
        n = timestamp = top = dcc_cnt = idx = 0;
        memset(cut, 0, sizeof cut);
        memset(dfn, 0, sizeof dfn);
        memset(h, -1, sizeof h);
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            n = max(n, max(a, b));
            add(a, b), add(b, a);
        }
        for (root = 1; root <= n; root++) {
            if (!dfn[root]) {
                tarjan(root);
            }
        }
        int res = 0;
        ULL num = 1;
        for (int i = 1; i <= dcc_cnt; i++) {
            int cnt = 0;
            for (int j = 0; j < dcc[i].size(); j++) {
                if (cut[dcc[i][j]]) cnt++;
            }
            if (cnt == 0) {
                if (dcc[i].size() == 1) res++;
                else {
                    res += 2, num *= dcc[i].size() * (dcc[i].size() - 1) / 2; 
                }
            } else if (cnt == 1) res ++, num *= (dcc[i].size() - 1);
        }
        printf("Case %d: %d %llu\n", T++, res, num);
    }
    return 0;
}


活动打卡代码 AcWing 368. 银河

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

using namespace std;

typedef long long LL;

const int N = 100010, M = 4 * N;
int h[N], hs[N], ne[M], w[M], e[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int scc, id[N], sz[N], dist[N];
int n, m;

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 v = e[i];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v]) {
            low[u] = min(low[u], low[v]);
        }
    }
    if (low[u] == dfn[u]) {
        scc++;
        int t;
        do {
            t = stk[top--];
            in_stk[t] = false;
            id[t] = scc;
            sz[scc]++;
        } while (t != u);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    for (int i = 0; i < m; i++) {
        int t, a, b;
        scanf("%d%d%d", &t, &a, &b);
        if (t == 1) add(h, a, b, 0), add(h, b, a, 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);
    }
    for (int i = 1; i <= n; i++) {
        add(h, 0, i, 1);
    }
    tarjan(0);
    bool success = true;
    for (int i = 0; i <= n; i++) {
        for (int j = h[i]; ~j; j = ne[j]) {
            int v = e[j], d = w[j];
            if (id[i] == id[v]) {
                if (d > 0) {
                    success = false;
                    break;
                }
            } else {
                add(hs, id[i], id[v], d);
            }
        }
        if (!success) break;
    }
    if (!success) puts("-1");
    else {
        for (int i = scc; i; i--) {
            for (int j = hs[i]; ~j; j = ne[j]) {
                int v = e[j];
                dist[v] = max(dist[v], dist[i] + w[j]);
            }
        }
        LL res = 0; 
        for (int i = 1; i <= scc; i++) res += (LL)sz[i] * dist[i];
        printf("%lld\n", res);
    }
    return 0;
}


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

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

using namespace std;

const int N = 100010, M = 2 * N;
int h[N], ne[M], e[M], idx;
int q[N], d[N], depth[N], f[N][18];
int n, m;
int ans;

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

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 u = q[hh++];
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (depth[v] > depth[u] + 1) {
                depth[v] = depth[u] + 1;
                q[++tt] = v;
                f[v][0] = u;
                for (int j = 1; j < 18; j++) {
                    int anc = f[v][j - 1];
                    f[v][j] = f[anc][j - 1];
                }
            }
        }
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 17; k >= 0; k--) {
        if (depth[f[a][k]] >= depth[b]) {
            a = f[a][k];
        }
    }
    if (a == b) return a;
    for (int k = 17; k >= 0; k--) {
        if (f[a][k] != f[b][k]) {
            a = f[a][k];
            b = f[b][k];
        }
    }
    return f[a][0];
}

int dfs(int u, int fa)
{
    int s = d[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;
        int t = dfs(v, u);
        if (t == 0) ans += m;
        else if (t == 1) ans++;
        s += t;
    }
    return s;
}

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);
        d[a]++, d[b]++, d[lca(a, b)] -= 2;
    }
    dfs(1, -1);
    printf("%d\n", ans);
    return 0;
}



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

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

using namespace std;

typedef long long LL;

const int N = 100010, M = 3e5 + 10, INF = 0x3f3f3f3f;
int n, m;
int h[N], ne[M], e[M], w[M], idx;
int p[N];
int f[N][17], d1[N][17], d2[N][17], depth[N], q[N];

struct Edges {
    int a, b, w;
    bool used;
    bool operator < (const Edges &t) const {
        return w < t.w;
    }
} edges[M];

int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}

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

void init()
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;
    int hh = 0, tt = 0; 
    q[0] = 1;
    while (hh <= tt) {
        int u = q[hh++];
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (depth[v] > depth[u] + 1) {
                depth[v] = depth[u] + 1;
                f[v][0] = u;
                d1[v][0] = w[i], d2[v][0] = -INF;
                q[++tt] = v;
                for (int k = 1; k < 17; k++) {
                    int anc = f[v][k - 1];
                    f[v][k] = f[anc][k - 1];
                    int distance[4] = {d1[v][k - 1], d2[v][k - 1], d1[anc][k - 1], d2[anc][k - 1]};
                    d1[v][k] = d2[v][k] = -INF;
                    for (int j = 0; j < 4; j++) {
                        int d = distance[j];
                        if (d > d1[v][k]) {
                            d2[v][k] = d1[v][k];
                            d1[v][k] = d;
                        } else if (d != d1[v][k] && d > d2[v][k]) {
                            d2[v][k] = d;
                        }
                    }
                }
            }
        }
    }
}

int lca(int a, int b, int w)
{
    int cnt = 0;
    static int distance[2 * N];
    if (depth[a] < depth[b]) swap(a, b);
    // 先将深度较大的节点a上移
    for (int i = 16; i >= 0; i--) {
        if (depth[f[a][i]] >= depth[b]) {
            distance[cnt++] = d1[a][i];
            distance[cnt++] = d2[a][i];
            a = f[a][i];
        }
    }

    // a, b同时往上移动
    if (a != b) {
        for (int i = 16; i >= 0; i--) {
            if (f[a][i] != f[b][i]) {
                distance[cnt++] = d1[a][i];
                distance[cnt++] = d2[a][i];
                distance[cnt++] = d1[b][i];
                distance[cnt++] = d2[b][i];
                a = f[a][i];
                b = f[b][i];
            }
        }
        distance[cnt++] = d1[a][0];
        distance[cnt++] = d1[b][0];
    }

    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);
        edges[i] = {a, b, c, false};
    }
    sort(edges, edges + m);
    LL sum = 0;
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 0; i < m; i++) {
        int a = find(edges[i].a), b = find(edges[i].b), w = edges[i].w;
        if (a != b) {
            sum += w;
            p[a] = b;
            edges[i].used = true;
        }
    }

    // 建树
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        if (edges[i].used) {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;
            add(a, b, w), add(b, a, w);
        }
    }

    // 初始化f, d1, d2数组
    init();

    // 倍增求环上的最大值和严格次大指
    LL res = 1e18;
    for (int i = 0; i < m; i++) {
        if (!edges[i].used) {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;
            res = min(res, sum + lca(a, b, w));
        }
    }
    printf("%lld\n", res);
    return 0;
}


活动打卡代码 AcWing 345. 牛站

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

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;
int idx, n, t, S, E;
int g[N][N], res[N][N];
map<int, int> ver;

void mul(int c[][N], int b[][N], int a[][N])
{
    static int t[N][N];
    memset(t, 0x3f, sizeof t);
    for (int k = 1; k <= idx; k++) {
        for (int i = 1; i <= idx; i++) {
            for (int j = 1; j <= idx; j++) {
                t[i][j] = min(t[i][j], b[i][k] + a[k][j]);
            }
        }
    }
    memcpy(c, t, sizeof t);
}

void qmi()
{
    memset(res, 0x3f, sizeof res);
    for (int i = 1; i < N; i++) res[i][i] = 0;
    while (n) {
        if (n & 1) mul(res, res, g);
        mul(g, g, g);
        n >>= 1;
    }
}

int main()
{
    cin >> n >> t >> S >> E;
    if (!ver.count(S)) ver[S] = ++idx;
    if (!ver.count(E)) ver[E] = ++idx;
    memset(g, 0x3f, sizeof g);
    while (t--) {
        int a, b, c;
        cin >> c >> b >> a;
        if (!ver.count(a)) ver[a] = ++idx;
        if (!ver.count(b)) ver[b] = ++idx;
        g[ver[a]][ver[b]] = g[ver[b]][ver[a]] = min(g[ver[a]][ver[b]], c);
    }
    qmi();
    cout << res[ver[S]][ver[E]] << endl;
    return 0;
}