多校训练营3

C:Concatenation

LyFive

标签

trie树;exkmp;dfs;空间优化

题意

给定个字符串，求个字符串连接后字典序最小的。

思路

最简单的贪心思路能够想到，若的拼接顺序在的前面，则应满足。为此最简单的方案是以此为关键字排序，时间复杂度为。为将复杂度降低至线性，可以考虑如果排序。利用贪心思想，①若不是的前缀，则应直接比较的字典序，将字典序小的放在前面；②若是的前缀则利用O(1)进行比较。因此具体方案如下：构造树，根据树各串的序确定①排序，此时目标字符串的前缀集合已经排序完成，通过比较与每一个存在的前缀的排序关系进行插入排序即可。且不难证明，设所有排在前面的前缀集合为，排在后面的前缀集合为。则集合一定是连续的，即不存在元素在之间。因为且故顺序为。因此，核心实现难度为使用比较与的大小关系。 令通过我们探讨与前缀的排序关系：首先，的数组代表以下标开始的后缀与原字符串的最长公共前缀长度。我们将与拼接可得到与。比较与的字典序，若前者字典序小则前缀应属于集合，否则属于集合。 比较下面两种情况，$Z[|S|] < |a| $ imges 1. 左边：，此时红线左部分一致，若要比较的字典序关系应为红线右半部分字典序关系。此时红线位置上方相对于下标为，下方相对于下标为0。再次利用的数组，得到为此只需比较与的大小关系即可。 2. 右边：，此时红线上方相对于下标为。下方相对于下标为，同理比较与的大小关系即可。

参考代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define pb push_back
#define x first
#define y second

const LL S = 2e7 + 100;
const LL N = 2e6 + 100;

char str[S];
string s;
vector<string> v;

int cnt = 0;
int n;
int tr[S][6], idx;
int st[S];
int num[S];
int z[S];
pair<int, int> out[N];
int res;
bool yes[N];

void init()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
}

void insert()
{
    static int cnt = 0;
    int p = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int c = s[i] - '0';
        if (!tr[p][c])
        {
            tr[p][c] = ++idx;
        }
        p = tr[p][c];
    }
    st[p]++;
    if (num[p] == -1)
    {
        v[cnt] = s;
        num[p] = cnt++;
    }
}

void updateZ()
{
    memset(z, 0, sizeof(int) * (cnt + 1));
    for (int i = 1, l = 0, r = 0; i < cnt; i++)
    {
        if (i <= r && z[i - l] < r - i + 1)
            z[i] = z[i - l];
        else
        {
            z[i] = max(0, r - i + 1);
            while (i + z[i] < cnt && str[z[i]] == str[i + z[i]])
                z[i]++;
        }
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
}

void output(int up, int stu)
{
    out[res++] = {num[up], stu};
    vector<int> vv;
    for (int i = 0, p = 0; i < cnt - 1; i++)
    {
        p = tr[p][str[i] - '0'];
        if (st[p])
        {
            int len = v[num[p]].size();
            if (z[len] == cnt - len)
            {
                len = z[len];
                if (str[(len + z[len]) % cnt] > str[z[len] % cnt])
                {
                    yes[num[p]] = 1;
                    vv.push_back(num[p]);
                }
            }
            else if (str[(len + z[len]) % cnt] < str[z[len] % cnt])
            {
                yes[num[p]] = 1;
                vv.push_back(num[p]);
            }
        }
    }
    for (int k = res - 2; k >= 0; k--)
    {
        if (yes[out[k].x])
            swap(out[k + 1], out[k]);
        else
            break;
    }
    for (auto x : vv)
        yes[x] = 0;
}

int stack_p[S], stack_cnt[S], sid;
char stack_s[S];

void dfs(int u)
{
    stack_p[sid] = u;
    stack_cnt[sid] = 0;
    sid++;
    while (sid != 0)
    {
        int u = stack_p[sid - 1];
        cnt = stack_cnt[sid - 1];
        if (cnt)
        {
            str[cnt - 1] = stack_s[sid - 1];
        }
        sid--;
        if (st[u])
        {
            updateZ();
            output(u, st[u]);
        }
        for (int i = 4; i >= 0; i--)
        {
            if (tr[u][i])
            {
                stack_p[sid] = tr[u][i];
                stack_cnt[sid] = cnt + 1;
                stack_s[sid] = '0' + i;
                sid++;
            }
        }
    }
}

void solve()
{
    cin >> n;
    v.resize(n);
    memset(num, -1, sizeof num);
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        insert();
    }
    dfs(0);
    for (int i = 0; i < res; i++)
    {
        for (int j = 0; j < out[i].y; j++)
            cout << v[out[i].x];
    }
}

int main()
{
    init();
    solve();
}

F:Fief

H:Hacker

LyFive

标签

;线段树

题意

给定一个字符串，和一个权值数组。每次询问输入一个字符串，的权值为现求字符串与的所有公共子串的权值和最大为多少。

思路

首先通过可以遍历一遍就可以得到所有与匹配的最长子串，为此问题就转换为给定一个数组，求最大数组区间和。对于最大数组区间和，利用前缀和枚举选定一个右边界通过线段树找到最小的左边界就可以得到。而时间复杂度分析可以得到，匹配的子串涉及的长度最多为，保证每个右边界最多访问一次，每次查找左边界为，为此时间复杂度为。考虑实现细节，如何保证匹配得到最长子串。利用的性质，存储连续后缀长度信息(如:为连续后缀)。每次利用遍历串匹配得到最长串更新，并删除最长串的第一个字符即下一个连续后缀，判断该连续后缀是否属于当前状态即后缀长度是否大于等于状态集最小长度，若满足则当前匹配状态不变，否则通过边进入的下一个连续后缀。为此就能保证每次匹配可以得到最长匹配子串。再记录右边界更新情况，保证每个右边界只查询一次即可。

参考代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 4e6 + 10;
int tot = 1, last = 1;
struct Node
{
    int len, fa;
    int ch[26];
} node[N];

string s;
LL f[N], ans;
int n, m, k;
LL w[N];

void extend(int c)
{
    int p = last, np = last = ++tot;
    f[tot] = 1;
    node[np].len = node[p].len + 1;
    for (; p && !node[p].ch[c]; p = node[p].fa)
        node[p].ch[c] = np;
    if (!p)
        node[np].fa = 1;
    else
    {
        int q = node[p].ch[c];
        if (node[q].len == node[p].len + 1)
            node[np].fa = q;
        else
        {
            int nq = ++tot;
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq;
            for (; p && node[p].ch[c] == q; p = node[p].fa)
                node[p].ch[c] = nq;
        }
    }
}

LL tr[N], l[N], r[N], mid[N];
void create(int ll, int rr, int i)
{
    if (ll == rr)
    {
        l[i] = ll;
        r[i] = rr;
        mid[i] = ll;
        tr[i] = w[ll];
    }
    else
    {
        mid[i] = (ll + rr) >> 1;
        l[i] = ll;
        r[i] = rr;
        create(ll, mid[i], i * 2);
        create(mid[i] + 1, rr, 2 * i + 1);
        tr[i] = min(tr[2 * i], tr[2 * i + 1]);
    }
}

LL query(int L, int R, int i)
{
    if (L <= l[i] && R >= r[i])
    {
        return tr[i];
    }
    LL s = 1e18;
    if (L <= mid[i])
    {
        s = min(s, query(L, R, 2 * i));
    }
    if (mid[i] + 1 <= R)
    {
        s = min(s, query(L, R, 2 * i + 1));
    }
    return s;
}

void init()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
}

int main()
{
    init();
    cin >> n >> m >> k;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
        extend(s[i] - 'a');

    node[1].fa = 1;
    for (int i = 1; i <= m; i++)
        cin >> w[i];
    for (int i = 1; i <= m; i++)
    {
        w[i] += w[i - 1];
    }

    create(0, m, 1);

    for (int i = 0; i < k; i++)
    {
        cin >> s;
        LL ans = 0;
        s = " " + s + " ";
        int len = 0;
        LL lasti = 0;
        for (int p = 1, i = 1; i < s.size(); i++)
        {
            if (s[i] == ' ' || node[p].ch[s[i] - 'a'] == 0)
            {
                if (len == 0)
                    continue;
                LL L = i - len;
                for (int ii = max(L, lasti); ii < i; ii++)
                {
                    ans = max(ans, w[ii] - query(L - 1, ii, 1));
                }
                i--;
                lasti = i;
                len--;
                if (node[node[p].fa].len == len)
                    p = node[p].fa;
            }
            else
            {
                p = node[p].ch[s[i] - 'a'];
                len++;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

J:Journey

LyFive

标签

;最短路

题意

给定个十字路口，右转不会遇见红灯，其他方向都会遇到一次红灯。初始在的路上，求到达的路径上，最少遇见的多少红灯。

思路

不难发现，每次选定一个路径遇见的红灯次数为，为此可以直接使用进行遍历更新答案。设图为表示节点通过第条边达到的位置，处理时可以用队列存储右转同层路径使用栈/数组/队列存储下一层路径即可。维护过程中需要注意建图方式，若当前路径为需要找到的边位置，右转则表示到达边，枚举其他边则表示。

参考代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define x first
#define y second

const int N = 5e5 + 100;

int c[N][5];
bool st[N][5];
int n, m, x, y;
int s1, s2, t1, t2;

void init()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
}

int bfs()
{
    queue<pair<pii, int>> q;
    stack<pair<pii, int>> sc;
    q.push({{s1, s2}, 0});
    while (q.size() || sc.size())
    {
        if (q.size() == 0)
        {
            while (sc.size())
            {
                q.push(sc.top());
                sc.pop();
            }
        }
        if (!q.size())
            break;
        auto s = q.front();
        q.pop();
        if (s.x.x == t1 && s.x.y == t2)
        {
            return s.y;
        }
        int x = s.x.x;
        int y = s.x.y;
        int pos = 1;
        for (int i = 1; i <= 4; i++)
        {
            if (c[y][i] == x)
            {
                pos = i;
                break;
            }
        }
        if (st[y][pos])
            continue;
        st[y][pos] = 1;
        q.push({{y, c[y][pos % 4 + 1]}, s.y});
        for (int i = 2; i <= 4; i++)
        {
            int yy = (pos + i - 1) % 4 + 1;
            sc.push({{y, c[y][yy]}, s.y + 1});
        }
    }
    return -1;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= 4; j++)
        {
            cin >> c[i][j];
        }
    }
    cin >> s1 >> s2 >> t1 >> t2;
    cout << bfs() << "\n";
}

int main()
{
    init();
    solve();
}
build本页面最近更新：2022/7/31 17:24:24，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：Ir1d
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论