编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#8229 #1059. 张宇的1000题 Accepted 100 195 ms 22636 K C++ 17 / 2.8 K Non_User8 2024-03-07 22:28:06
显示原始代码
#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 10;

int n, m, q, f[N], T, tot, last, pre[N];

char s1[N], s2[N];

vector<int> e[N];

struct Node {
    int tr[26], fa, len, mn;
} t[N];

void init_(int x) {
    t[x].fa = 0, t[x].mn = 1e8;
    memset(t[x].tr, 0, sizeof(t[x].tr));
    e[x].clear();
}

void ext_(int k) {
    int p = last, x;

    /* if (t[p].tr[k]) {
         x = t[p].tr[k];
         t[x].mn = min(t[x].mn, m);
         last = x;
         return;
     }*/

    init_(x = ++tot);
    t[x].len = t[p].len + 1;
    t[x].mn = m;

    while (p && !t[p].tr[k]) {
        t[p].tr[k] = x;
        p = t[p].fa;
    }

    if (!p) {
        t[x].fa = 1;
    } else {
        int q = t[p].tr[k];

        if (t[p].len + 1 == t[q].len) {
            t[x].fa = q;
        } else {
            init_(++tot);
            t[tot] = t[q];
            t[tot].len = t[p].len + 1;
            t[q].fa = t[x].fa = tot;

            while (p && t[p].tr[k] == q) {
                t[p].tr[k] = tot;
                p = t[p].fa;
            }
        }
    }

    last = x;
}

void dfs1_(int u) {
    for (int v : e[u]) {
        dfs1_(v);
        t[u].mn = min(t[u].mn, t[v].mn);
    }
}

void dfs2_(int u) {
    for (int v : e[u]) {
        if (t[u].mn < t[v].mn) {
            pre[v] = u;
        } else {
            pre[v] = pre[u];
        }

        dfs2_(v);
    }
}

void solve_() {
    scanf("%d", &q);
    f[0] = 1e9;

    while (q--) {
        scanf("%s", s2 + 1), m = strlen(s2 + 1), last = 1;
        f[0] = min(f[0], m);

        for (int i = 1; i <= m; i++) {
            ext_(s2[i] - 'a');
        }
    }

    scanf("%s", s1 + 1);
    n = strlen(s1 + 1);

    for (int i = 2; i <= tot; i++) {
        e[t[i].fa].push_back(i);
    }

    dfs1_(1);
    dfs2_(1);

    for (int x = 1, len = 0, i = 1; i <= n; i++) {
        while (x && !t[x].tr[s1[i] - 'a']) {
            x = t[x].fa;
            len = t[x].len;
        }

        if (!x) {
            x = 1, len = 0;
        } else {
            x = t[x].tr[s1[i] - 'a'];
            len++;
        }

        f[i] = f[i - 1] + 1;

        int cnt = 0, y = x;

        f[i] = f[i - 1] + 1;

        while (y > 1) {
            f[i] = min(f[i],
                       min(f[i - min(t[y].len, len)], i - min(t[y].len, len)) + t[y].mn - min(t[y].len, len));

            if (f[i] < f[i - 1]) {
                break;
            }

            y = pre[y];
        }

        // printf("%d\n", f[i]);
        // assert(abs(f[i] - f[i - 1]) <= 1);
    }

    printf("%d\n", f[n]);
}

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

    T = 1;

    while (T--) {
        init_(tot = 1);
        solve_();
    }
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:12 ms
内存:9748 KiB

输入文件(in1.in

10
qzn
vpr
eib
khu
nsd
bli
glo
gjc
iyi
kep
zjrgesctzw

答案文件(in1.out

11

用户输出

11

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:12 ms
内存:9808 KiB

输入文件(in2.in

10
epd
qae
yrz
zfo
cjf
tck
gom
qvn
dgi
zvn
sskoiryqae

答案文件(in2.out

7

用户输出

7

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:12 ms
内存:9740 KiB

输入文件(in3.in

10
nuy
ddg
loa
jiw
zcp
uyw
oqq
pxb
iyj
ogh
jluejdqhqk

答案文件(in3.out

11

用户输出

11

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:12 ms
内存:9772 KiB

输入文件(in4.in

10
ezj
spk
qem
mgq
wth
yoz
abk
ztz
spw
sqy
exiyxnkayg

答案文件(in4.out

11

用户输出

11

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:13 ms
内存:9748 KiB

输入文件(in5.in

10
tfu
laf
zqb
qha
fti
lxn
zub
nlo
jip
ljh
rfzwlxsjph

答案文件(in5.out

9

用户输出

9

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:12 ms
内存:9804 KiB

输入文件(in6.in

10
chb
hao
iud
yzk
rny
mit
nbx
xqq
ibd
twr
bgroijzqld

答案文件(in6.out

11

用户输出

11

系统信息

Exited with return code 0
测试点 #7
Accepted
得分:100
用时:14 ms
内存:9820 KiB

输入文件(in7.in

10
bgd
ydc
siu
xvr
ymf
nkw
qso
wfu
dek
gxn
rvstydwzbz

答案文件(in7.out

9

用户输出

9

系统信息

Exited with return code 0
测试点 #8
Accepted
得分:100
用时:12 ms
内存:9756 KiB

输入文件(in8.in

10
msc
eza
cix
ojy
pgc
alo
khe
tcu
ktg
meb
vnycajzbvj

答案文件(in8.out

11

用户输出

11

系统信息

Exited with return code 0
测试点 #9
Accepted
得分:100
用时:48 ms
内存:22636 KiB

输入文件(in9.in

33333
pkp
dje
lip
uhg
sum
lpw
jmo
gnn
apj
ykw
fwe
stk
mre
iqp
jwg
djv
jzq
uzs
xfx
<199905 bytes omitted>

答案文件(in9.out

1141

用户输出

1141

系统信息

Exited with return code 0
测试点 #10
Accepted
得分:100
用时:48 ms
内存:22600 KiB

输入文件(in10.in

33333
wzk
ozo
xxw
rkh
bry
bvs
rzs
heq
ksl
abx
mvq
xpg
exr
hwu
hrt
bzn
qpv
zlf
rmx
<199905 bytes omitted>

答案文件(in10.out

1169

用户输出

1169

系统信息

Exited with return code 0