AtCoder Beginner Contest 268 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

ab 不说了

[ABC268C] Chinese Restaurant

题面

有 $N$$N$ 个人从 $0$$0$ 开始编号， 按逆时针顺序间隔均匀地坐在转盘周围。 在开始时， 第 $p_i$$p_{i}$ 盘菜在第 $i$$i$ 个人的前面。

现在， 你可以进行以下操作 $0$$0$ 次或多次。

• 将转盘逆时针旋转 $\frac{1}{N}$$\frac{1}{N}$ 圈。也就是说， 旋转前在第 $i$$i$ 号人面前的盘子现在在 $(i+1)modN$$(i+1)\bmod N$ 号人面前了。

当你结束操作后，如果第 $i$$i$ 盘菜在第 $(i-1)modN$$(i-1)\bmod N$ 个人、第 $i$$i$ 个人或第 $(i+1)modN$$(i+1)\bmod N$ 个人面前，第 $i$$i$ 个人就会感到高兴。

请求出你最多能使多少人感到高兴。

Solution

不难想到单向记录 $i$$i$ 到 $p_i$$p_i$ 的距离，然后每次枚举挨着的三个 $dis$$dis$ 求和即为本次的答案。取最大值即可。

Code

xxxxxxxxxx
55
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define pre(i) (i ? i - 1 : N - 1)
23
#define nxt(i) (i == N - 1 ? 0 : i + 1)
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N;
29
int cnt_dis[210000];
30
int ans(0);
31

32
int main(){
33
    N = read();
34
    for(int i = 0; i <= N - 1; ++i)cnt_dis[(i - read() + N) % N]++;
35
    for(int i = 0; i <= N - 1; ++i)ans = max(ans, cnt_dis[i] + cnt_dis[pre(i)] + cnt_dis[nxt(i)]);
36
    printf("%d\n", ans);
37
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
38
    return 0;
39
}
40

41
template < typename T >
42
inline T read(void){
43
    T ret(0);
44
    int flag(1);
45
    char c = getchar();
46
    while(c != '-' && !isdigit(c))c = getchar();
47
    if(c == '-')flag = -1, c = getchar();
48
    while(isdigit(c)){
49
        ret *= 10;
50
        ret += int(c - '0');
51
        c = getchar();
52
    }
53
    ret *= flag;
54
    return ret;
55
}

[ABC268D] Unique Username

题面

给定 $n$$n$ 各字符串，另外给定 $m$$m$ 个字符串。你需要对 $n$$n$ 个字符串进行排列，并在每相邻两个字符串中间插入至少一个下划线，并且最终字符串与给定的 $m$$m$ 个字符串均不同。输出任意一个长度在 $[3,16]$$[3, 16]$ 的方案。

Solution

第一眼没什么想法，看了一眼数据范围才反应过来这似乎就是个暴力，我们尝试分析一下：

令 $n$$n$ 个字符串总长度和为 $s$$s$，我们还要至少插入 $n-1$$n - 1$ 个下划线，那么剩下的可能长度就只有 $16-s-(n-1)=17-n-s$$16 - s - (n - 1) = 17 - n - s$，同时显然 $s\ge n$$s \ge n$。对于剩下的长度不难发现可以认为其是将下划线可空地放入 $n-1$$n - 1$ 个不同盒子里，显然这就是 $17-n-s$$17 - n - s$ 个可空的不同球盒问题。关于球盒问题可以去看我的 Blog：浅析排列组合、斯特林数、贝尔数、二项式定理与推论及其反演、子集反演、广义容斥。再加上枚举全排列的 $n!$$n!$，最终的复杂度大约是：

化简一下：

这一大坨东西我不知道我是否分析错了，不过大概也八九不离十，总之这个东西我们随便带入几个 $n$$n$ 算一下，或者感性理解一下发现显然是远小于 $1e8$$1e8$ 的，所以暴力即可通过。

做法的话先通过调用 $n!$$n!$ 次 next_permutation() 函数枚举全排列，此时还会多一个 $O(n)$$O(n)$ 的常数，不过区别不大。

然后每次跑一遍深搜，用 string 的本质是 basic_string，且 basic_string 支持 + 和 += 等的特性，即可十分便捷地实现一般的深搜思路，注意每两个之间至少插入一个下划线，且注意需要限制最多额外添加 $17-n-s$$17 - n - s$ 个下划线，否则复杂度是不正确的。

Code

xxxxxxxxxx
71
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N, M;
26
int mx(-1);
27
string S[10];
28
unordered_set < string > block;
29
string ans;
30

31
void dfs(int dep = 1, int lft = mx, string cur = string()){
32
    if(dep > N){
33
        if(3 <= (int)cur.length() && (int)cur.length() <= 16 && block.find(cur) == block.end())ans = cur;
34
        return;
35
    }
36
    if(dep == 1)return dfs(dep + 1, lft, cur + S[dep]);
37
    dfs(dep + 1, lft, cur + "_" + S[dep]);
38
    for(int i = 1; i <= lft; ++i)
39
        cur += "_", dfs(dep + 1, lft - i, cur + "_" + S[dep]);
40
}
41

42
int main(){
43
    N = read(), M = read();
44
    int slen(0);
45
    for(int i = 1; i <= N; ++i)cin >> S[i], slen += S[i].length();
46
    for(int i = 1; i <= M; ++i){string T; cin >> T; block.insert(T);}
47
    mx = 16 - slen - N + 1;
48
    if(mx < 0)printf("-1\n"), exit(0);
49
    int tot(1); for(int i = 1; i <= N; ++i)tot *= i;
50
    for(int i = 1; i <= tot; ++i)dfs(), next_permutation(S + 1, S + N + 1);
51
    if(ans.empty())printf("-1\n"), exit(0);
52
    cout << ans << endl;
53
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54
    return 0;
55
}
56

57
template < typename T >
58
inline T read(void){
59
    T ret(0);
60
    int flag(1);
61
    char c = getchar();
62
    while(c != '-' && !isdigit(c))c = getchar();
63
    if(c == '-')flag = -1, c = getchar();
64
    while(isdigit(c)){
65
        ret *= 10;
66
        ret += int(c - '0');
67
        c = getchar();
68
    }
69
    ret *= flag;
70
    return ret;
71
}

[ABC268E] Chinese Restaurant (Three-Star Version)

题面

$n$$n$ 个人进行圆排列，即围坐在圆桌周围，位置编号依次为 $[0,n-1]$$[0, n - 1]$，给定序列 $P_n$$P_n$ 表示第 $i$$i$ 个人喜欢的菜品在 $P_i$$P_i$ 处，$P_i\in [0,n-1]$$P_i \in [0, n - 1]$ 且各不相同。定义每个人的沮丧值为其位置与 $P_i$$P_i$ 的距离。你可以任意旋转圆桌，以最小化所有人的沮丧值之和，求最小值。

Solution

可以说是一道思路较为简单但细节巨多，非常难调的题，到处各种加加减减与分类讨论，这么一道水题最后我写了一个半点。

首先我们可以想到，我们认为初始状态为 $i$$i$ 在 $i-1$$i - 1$，然后认为初始状态之后转的格数为 $x$$x$ 轴，对于一个特定的人的沮丧值为 $y$$y$ 轴，不难想到图像应为至多三段斜率为 $1$$1$ 或 $-1$$-1$ 的线段组成，同时若点数为奇数，那么在距离 $P_i$$P_i$ $\lfloor {\displaystyle \frac{n}{2}}\rfloor$$\lfloor \dfrac{n}{2} \rfloor$ 和 $\lceil {\displaystyle \frac{n}{2}}\rceil$$\lceil \dfrac{n}{2} \rceil$ 的对应位置的值是相同的，也就是此时斜率应为 $0$$0$，但有且仅有这么一段。对于答案我们只需要将每个人的情况都合并起来求一下最小值即可，考虑如何维护。

于是我们直接考虑 $y$$y$ 轴的值，对于一个人的变化量显然是类似 $-1,-1,-1,1,1,1,0,1,\cdots$$-1, -1, -1, 1, 1, 1, 0, 1, \cdots$ 等，这个东西等于是做了个差分。不难发现这东西如果用线段树维护区间修改，那么最终复杂度应为 $O(n\log n)$$O(n \log n)$ 的，不过我不想写线段树，于是考虑另一种写法，不难发现这东西是很多个区间修改，所以可以对差分数组再次做差分，即二阶差分，此时我们只需要在转折点处做一下修改即可，这样最后做两次前缀和求个最大值即可。

不难发现这东西思路显然看起来很简单，但是当实现的时候就会发现阴间的地方在哪了。首先我们发现有四种情况，即 $i$$i$ 与 $p_i$$p_i$ 的偏序关系，和 $(i-p_i)modn$$(i - p_i) \bmod{n}$ 与 $(p_i-i)modn$$(p_i - i) \bmod{n}$ 的偏序关系。但是经过讨论我们会发现，前者的偏序关系是无意义的，因为我们求距离时可以直接转正，即 $dis=(i-p_i+n)modn$$dis = (i - p_i + n) \bmod{n}$，所以此时优化情况为两种。

具体情况可以自己画一下然后看看代码，还是比较显然的，只是细节太多了。

Code

xxxxxxxxxx
69
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
int P[210000];
27
ll d[210000];
28
ll ans(LONG_LONG_MAX);
29

30
int main(){
31
    N = read();
32
    for(int i = 0; i <= N - 1; ++i)P[i] = read();
33
    for(int i = 0; i <= N - 1; ++i)d[0] += min((i - P[i] + N) % N, (P[i] - i + N) % N);
34
    d[1] = -d[0];
35
    for(int i = 0; i <= N - 1; ++i)
36
        if((P[i] - i + N) % N <= (i - P[i] + N) % N){
37
            int dis = (P[i] - i + N) % N;
38
            d[1]--, d[dis + 1]++;
39
            d[dis + 1]++, d[dis + (N >> 1) + 1]--;
40
            d[dis + (N >> 1) + 1 + (N & 1 ? 1 : 0)]--;
41
        }else{
42
            int dis = (i - P[i] + N) % N;
43
            d[1]++, d[(N >> 1) - dis + 1]--;
44
            d[(N >> 1) - dis + 1 + (N & 1 ? 1 : 0)]--;
45
            d[N - dis + 1]++, d[N - dis + 1]++;
46
        }
47
    for(int i = 1; i <= N - 1; ++i)d[i] = d[i - 1] + d[i];
48
    for(int i = 1; i <= N - 1; ++i)d[i] = d[i - 1] + d[i];
49
    for(int i = 0; i <= N - 1; ++i)ans = min(ans, d[i]);
50
    printf("%lld\n", ans);
51
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
52
    return 0;
53
}
54

55
template < typename T >
56
inline T read(void){
57
    T ret(0);
58
    int flag(1);
59
    char c = getchar();
60
    while(c != '-' && !isdigit(c))c = getchar();
61
    if(c == '-')flag = -1, c = getchar();
62
    while(isdigit(c)){
63
        ret *= 10;
64
        ret += int(c - '0');
65
        c = getchar();
66
    }
67
    ret *= flag;
68
    return ret;
69
}

[ABC268F] Best Concatenation

题面

给定 $n$$n$ 个由 X 和数字构成的字符串，你需要对其进行排列并拼接成新的字符串 $T$$T$ 以最大化其分数。定义其分数为对于字符串中每一个数字，使数字对应的数值乘上其之前 X 的数量，并求和。输出分数最大值。

Solution

首先一个显然的结论即为对于题目定义的分数，同一字符串内部的 X 对其数字的贡献，与字符串在排列中的顺序无关。

于是我们考虑其它字符串的 X 对字符串数字的贡献，我们考虑字符串 $S_i,S_j$$S_i, S_j$，令 $cn{t}_i$$cnt_i$ 表示字符串 $i$$i$ 中 X 的数目，令 $su{m}_i$$sum_i$ 表示字符串 $i$$i$ 中所有数字数值之和。显然若 $S_i$$S_i$ 在 $S_j$$S_j$ 之前，$j$$j$ 对 $i$$i$ 无贡献，$i$$i$ 对 $j$$j$ 的贡献为 $cn{t}_i\times su{m}_j$$cnt_i \times sum_j$。反之则为 $cn{t}_j\times su{m}_i$$cnt_j \times sum_i$。

则不难想到若我们要将 $S_i$$S_i$ 放在 $S_j$$S_j$ 之前，那么一定有这样的贡献更大一些，即 $cn{t}_i\times su{m}_j>cn{t}_j\times su{m}_i$$cnt_i \times sum_j \gt cnt_j \times sum_i$。

所以我们直接考虑对字符串进行排序，比较规则则按照刚才的式子跑一下即可。

同时我们也可以从意义上感性理解，显然只有前面的 X 对后面的数字产生贡献，所以我们将 X 更多数字更少的放在前面，则 ${\displaystyle \frac{cn{t}_i}{su{m}_i}}$$\dfrac{cnt_i}{sum_i}$ 可以作为一个类似估价函数的作用进行排序，转换一下即我们刚才证明的上式。

同时对于此贪心的证明，考虑若满足偏序关系 $S_1,S_2$$S_1, S_2$ 和 $S_2,S_3$$S_2, S_3$，那么一定也有 $cn{t}_1\times su{m}_3>cn{t}_3\times su{m}_1$$cnt_1 \times sum_3 \gt cnt_3 \times sum_1$，所以也有偏序关系 $S_1,S_3$$S_1, S_3$，也就是 $S_1,S_2,S_3$$S_1, S_2, S_3$，扩展到整个序列依然满足。

存在双倍经验 LG-P1080 [NOIP2012 提高组] 国王游戏。

Code

xxxxxxxxxx
61
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
struct Node{string S; int sum, cnt;}d[210000];
27
ll ans(0);
28

29
int main(){
30
    N = read();
31
    for(int i = 1; i <= N; ++i){
32
        cin >> d[i].S;
33
        for(auto c : d[i].S)
34
            if(c == 'X')++d[i].cnt;
35
            else d[i].sum += c - '0';
36
    }sort(d + 1, d + N + 1, [](const Node &a, const Node &b)->bool{return (ll)a.sum * b.cnt < (ll)b.sum * a.cnt;});
37
    ll cur(0);
38
    for(int i = 1; i <= N; ++i)
39
        for(auto c : d[i].S)
40
            if(c == 'X')++cur;
41
            else ans += cur * (c - '0');
42
    printf("%lld\n", ans);
43
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
44
    return 0;
45
}
46

47
template < typename T >
48
inline T read(void){
49
    T ret(0);
50
    int flag(1);
51
    char c = getchar();
52
    while(c != '-' && !isdigit(c))c = getchar();
53
    if(c == '-')flag = -1, c = getchar();
54
    while(isdigit(c)){
55
        ret *= 10;
56
        ret += int(c - '0');
57
        c = getchar();
58
    }
59
    ret *= flag;
60
    return ret;
61
}

[ABC268G] Random Student ID

题面

给定 $n$$n$ 名学生的名字 $S_i$$S_i$，保证不重复。现在随机一个 $a\to z$$a \rightarrow z$ 的排列作为字典序的偏序关系，求每个同学排名的期望，对 $998244353$$998244353$ 取模。

Solution

这一题可以说确实很高妙，确实没想到还可以这么处理。

第一眼以为是一些类似 期望DP 的东西，然后想了半天也没想到什么复杂度正确的做法，实际上这道题是从期望的意义去找性质。

首先我们考虑对于一个串 $S$$S$ 的期望排名，若存在串 $S$$S$ 的前缀串 $T$$T$，那么显然串 $T$$T$ 无论字典序的偏序关系如何都会在 $S$$S$ 之前，所以一定会贡献 $1$$1$。

而若存在 $S$$S$ 是 $T$$T$ 的前缀，那么显然 $T$$T$ 在 $S$$S$ 之后，则贡献一定为 $0$$0$。

对于其它的情况，显然会由 $\mathtt{\text{LCP}}$$\texttt{LCP}$ 之后的第一个不同的字符决定，而对于这种显然在所有字典序关系中两者的偏序关系的概率是相同的，所以此时的贡献为 ${\displaystyle \frac{1}{2}}$$\dfrac{1}{2}$。那么对于字符串 $S$$S$，若其前缀串有 $x$$x$ 个，满足有 $S$$S$ 前缀的串有 $y$$y$ 个，那么答案即为：

然后对于求前缀，显然可以通过 Trie树 解决，同时也可以考虑一些更简单的方法：

开一个 unordered_set，往里面丢每个串的哈希值，然后对于每个串的每个前缀的哈希在里面查一下然后记录即可，最终复杂度 $O(\sum |S_i|)$$O(\sum \lvert S_i \rvert)$。

Code

xxxxxxxxxx
79
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (998244353ll)
23
#define BASE (31ll)
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N;
29
int cntx[510000], cnty[510000];
30
ll inv_2;
31
string S[510000];
32
unordered_map < unll, int > idx;
33

34
ll qpow(ll a, ll b){
35
    ll ret(1), mul(a);
36
    while(b){
37
        if(b & 1)ret = ret * mul % MOD;
38
        b >>= 1;
39
        mul = mul * mul % MOD;
40
    }return ret;
41
}
42

43
int main(){
44
    inv_2 = qpow(2, MOD - 2);
45
    N = read();
46
    for(int i = 1; i <= N; ++i){
47
        cin >> S[i];
48
        unll cur(0);
49
        for(auto c : S[i])(cur *= BASE) += c;
50
        idx.insert({cur, i});
51
    }
52
    for(int i = 1; i <= N; ++i){
53
        unll cur(0);
54
        for(auto c : S[i]){
55
            (cur *= BASE) += c;
56
            if(idx.find(cur) != idx.end())++cntx[i], ++cnty[idx[cur]];
57
        }cntx[i]--, cnty[i]--;
58
    }
59
    for(int i = 1; i <= N; ++i)
60
        printf("%lld\n", (cntx[i] + (N - cntx[i] - cnty[i] - 1) * inv_2 % MOD + 1) % MOD);
61
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
62
    return 0;
63
}
64

65
template < typename T >
66
inline T read(void){
67
    T ret(0);
68
    int flag(1);
69
    char c = getchar();
70
    while(c != '-' && !isdigit(c))c = getchar();
71
    if(c == '-')flag = -1, c = getchar();
72
    while(isdigit(c)){
73
        ret *= 10;
74
        ret += int(c - '0');
75
        c = getchar();
76
    }
77
    ret *= flag;
78
    return ret;
79
}

[ABC268Ex] Taboo

题面

给定仅有英文小写字母的字符串 $S$$S$，可以对其进行若干次操作，每次将 $S$$S$ 中某个字符替换为 *。给定 $n$$n$ 个仅有英文小写字母的模式串，要求进行操作使得 $S$$S$ 中不存在任意子串与模式串相同。最小化操作次数，输出最小值。

Solution

提供一个理论复杂度正确但因常数以及哈希原因无法通过的做法，同时略提正解。

首先我们不难想到，我们若对 $S$$S$ 匹配模式串 $T$$T$，显然若匹配到了，那么我们直接将匹配到的部分的最后一位改为 * 即可，贪心正确性显然，若改前面的可能会存在后面再次匹配使得不优。

然后对于所有匹配，我们也不难想到处理的顺序可以是先处理长度较小的串，然后再处理较长的。此处的贪心正确性仍显然，因为短的串处理时一定会尽量地破坏长的串，总之感性理解一下。

所以就不难想到一个做法，开一个 map < int, unordered_set < unsigned long long > >，对每个长度的串映射一个 set 存储所有该长度的模式串的哈希值，然后按序跑一遍，通过维护哈希来 $O(n)$$O(n)$ 跑一遍并匹配与替换。

分析一下这个的复杂度，显然每种长度都会跑一遍 $O(n)$$O(n)$，那么卡此做法的构造应使长度为等差数列，而等差数列求和是 $O(n^2)$$O(n^2)$ 级别的，所以最多的长度种类为 $O(\sqrt{\sum T_i})$$O(\sqrt{\sum T_i})$，也就是说最终复杂度是根号级别的。不过此时我们会发现这俩都是 5e5 级别的，似乎过不了？但是再看一眼时限 $4\mathtt{\text{s}}$$4\texttt{s}$，又似乎刚好能过。

不过实现之后会发现，部分测试点 WA，部分 TLE，TLE 的部分大概用了 $10\mathtt{\text{s}}$$10\texttt{s}$，若改为 unsigned int 时间可以到 $7\mathtt{\text{s}}$$7\texttt{s}$，但是同时也存在问题即哈希碰撞。我们自然可可以通过手写挂链或双模数等以使得满足正确性，但是时间上理性分析一下，等差数列实际是 ${\displaystyle \frac{n^2}{2}}$$\dfrac{n^2}{2}$ 的，所以此时还有个 $2$$2$ 倍常数，所以时间两倍之后寄掉也就很合理了。如果卡的不够死的话理论上还是可以改过的，但是也只是理论上，有兴趣可以尝试一下。

这里浅提一下正解，考虑刚才提到的贪心策略之后对于将所有模式串匹配掉直接写一个 AC自动机 即可，具体实现可以考虑如果一个节点的 fail 存在模式串那么该节点也认为是可以匹配的，也就是按照之前的贪心，优先去匹配更短的串。

Code

理论复杂度正确但无法通过的代码

xxxxxxxxxx
82
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define BASE (31ll)
23
#define S(i) (S.at(i - 1))
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N;
29
string S;
30
map < int, unordered_set < unll > > pat;
31
unll pow_base[510000];
32
int ans(0);
33

34
int main(){
35
    // freopen("in.txt", "r", stdin);
36
    pow_base[0] = 1;
37
    for(int i = 1; i <= 501000; ++i)pow_base[i] = pow_base[i - 1] * BASE;
38
    ios::sync_with_stdio(false);
39
    cin >> S;
40
    cin >> N;
41
    for(int i = 1; i <= N; ++i){
42
        string T;
43
        cin >> T;
44
        unll hashv(0);
45
        for(auto c : T)(hashv *= BASE) += c;
46
        pat[(int)T.length()].insert(hashv);
47
    }
48
    for(auto mp : pat){
49
        if(mp.first > (int)S.length())continue;
50
        unll cur(0);
51
        bool newStr(true);
52
        for(int i = 1; i <= mp.first - 1; ++i)(cur *= BASE) += S(i);
53
        for(int i = mp.first; i <= (int)S.length(); ++i){
54
            if(!newStr)cur -= S(i - mp.first) * pow_base[mp.first - 1];
55
            cur *= BASE; cur += S(i); newStr = false;
56
            if(mp.second.find(cur) != mp.second.end()){
57
                S(i) = '*', cur = 0, newStr = true, ++ans;
58
                if(i + mp.first > (int)S.length())break;
59
                for(int j = i + 1; j <= i + mp.first - 1; ++j)(cur *= BASE) += S(j);
60
                i = i + mp.first - 1;
61
            }
62
        }
63
    }printf("%d\n", ans);
64
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
65
    return 0;
66
}
67

68
template < typename T >
69
inline T read(void){
70
    T ret(0);
71
    int flag(1);
72
    char c = getchar();
73
    while(c != '-' && !isdigit(c))c = getchar();
74
    if(c == '-')flag = -1, c = getchar();
75
    while(isdigit(c)){
76
        ret *= 10;
77
        ret += int(c - '0');
78
        c = getchar();
79
    }
80
    ret *= flag;
81
    return ret;
82
}

正解代码

xxxxxxxxxx
99
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Node::operator new(size_t){static Node* P = nd; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define d(c) (c - 'a')
23

24
template < typename T = int >
25
inline T read(void);
26

27
struct Node{
28
    Node* son[26];
29
    Node* fail;
30
    int cnt;
31
    OPNEW;
32
}nd[510000];
33
ROPNEW;
34
Node* root;
35

36
int N;
37
int ans(0);
38
string S;
39
basic_string < Node* > tmp;
40

41
void Insert(string S){
42
    Node* cur = root;
43
    for(auto c : S){
44
        if(!cur->son[d(c)])cur->son[d(c)] = new Node();
45
        cur = cur->son[d(c)];
46
    }cur->cnt++;
47
}
48
void Build(void){
49
    queue < Node* > cur; cur.push(root);
50
    while(!cur.empty()){
51
        auto p = cur.front(); cur.pop();
52
        for(int i = 0; i <= 25; ++i)
53
            if(p->son[i]){
54
                cur.push(p->son[i]), tmp += p->son[i];
55
                if(p == root)p->son[i]->fail = root;
56
                else p->son[i]->fail = p->fail->son[i];
57
            }else{
58
                if(p == root)p->son[i] = root;
59
                else p->son[i] = p->fail->son[i];
60
            }
61
    }
62
}
63
void SetFail(void){
64
    for(auto p : tmp)p->cnt += p->fail->cnt;
65
}
66
void Accept(void){
67
    Node* cur = root;
68
    for(auto c : S){
69
        cur = cur->son[d(c)];
70
        if(cur->cnt)++ans, cur = root;
71
    }
72
}
73

74
int main(){
75
    root = new Node();
76
    cin >> S;
77
    N = read();
78
    for(int i = 1; i <= N; ++i){string T; cin >> T; Insert(T);}
79
    Build(), SetFail(), Accept();
80
    printf("%d\n", ans);
81
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
82
    return 0;
83
}
84

85
template < typename T >
86
inline T read(void){
87
    T ret(0);
88
    int flag(1);
89
    char c = getchar();
90
    while(c != '-' && !isdigit(c))c = getchar();
91
    if(c == '-')flag = -1, c = getchar();
92
    while(isdigit(c)){
93
        ret *= 10;
94
        ret += int(c - '0');
95
        c = getchar();
96
    }
97
    ret *= flag;
98
    return ret;
99
}

UPD

update-2023_01_18 初稿