Asusetic
0%

2021.05.30模拟赛

发表于 分类于 Valine：
本文字数： 872 阅读时长 ≈ 1 分钟

原题场（确信）

2021.05.30 模拟赛

T1 识别子串

识别子串

考虑仅出现一次的子串在 SAM 上就是 endposendpos 大小为 11 的点

建出来 SAM 后找到所有大小为 11 的点 xx ，他们在原串上对应的点为 pospos

那么他能更新的是

[pos−minlen(x),pos]→minlen(x)[pos-\mathrm{minlen}(x),pos] \rightarrow \mathrm{minlen}(x) 和

[pos−maxlen(x)+1,pos−minlen(x)]→pos−i+1[pos-\mathrm{maxlen}(x)+1,pos-\mathrm{minlen}(x)] \rightarrow pos-i+1

后面那个 pos−i+1pos-i+1 不可能一个个更新去，但是可以开两个线段树，一个更新 minlen(x)\mathrm{minlen}(x) 的，另一个负责更新 pos−i+1pos-i+1 的

查询的时候把第二个线段树 −i-i 和第一个取 min⁡\min 即可

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
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
int n;
int siz[N * 2], c[N * 2], pos[N * 2], a[N * 2];
char s[N];
namespace SAM {
int nxt[N * 2][27], link[N * 2], len[N * 2];
int cnt = 1, last = 1;
void insert(int c) {
    int cur  = ++cnt;
    int p    = last;
    last     = cur;
    len[cur] = len[p] + 1;
    siz[cur] = 1;
    pos[cur] = len[cur];
    while (p && !nxt[p][c]) {
        nxt[p][c] = cur;
        p         = link[p];
    }
    if (!p) {
        link[cur] = 1;
    } else {
        int q = nxt[p][c];
        if (len[p] + 1 == len[q]) {
            link[cur] = q;
        } else {
            int cq  = ++cnt;
            len[cq] = len[p] + 1;
            memcpy(nxt[cq], nxt[q], sizeof(nxt[q]));
            link[cq] = link[q];
            link[q] = link[cur] = cq;
            while (p && nxt[p][c] == q) {
                nxt[p][c] = cq;
                p         = link[p];
            }
        }
    }
}
} // namespace SAM
using namespace SAM;
struct Segment_Tree {
#define ls(x) x * 2
#define rs(x) x * 2 + 1
    int tree[N << 2], tag[N << 2];
    Segment_Tree() {
        memset(tag, 0x3f3f, sizeof(tag));
        memset(tree, 0x3f3f, sizeof(tree));
    }
    void pushdown(int x) {
        tag[ls(x)]  = min(tag[ls(x)], tag[x]);
        tag[rs(x)]  = min(tag[rs(x)], tag[x]);
        tree[ls(x)] = min(tree[ls(x)], tag[x]);
        tree[rs(x)] = min(tree[rs(x)], tag[x]);
        tag[x]      = INF;
    }
    void update(int x, int l, int r, int L, int R, int d) {
        if (l > R || r < L)
            return;
        if (l >= L && r <= R) {
            tree[x] = min(tree[x], d);
            tag[x]  = min(tag[x], d);
            return;
        }
        pushdown(x);
        int mid = (l + r) >> 1;
        update(ls(x), l, mid, L, R, d);
        update(rs(x), mid + 1, r, L, R, d);
        tree[x] = min(tree[ls(x)], tree[rs(x)]);
    }
    int query(int x, int l, int r, int pos) {
        if (l == r) {
            return tree[x];
        }
        pushdown(x);
        int mid = (l + r) >> 1;
        if (pos <= mid) {
            return query(ls(x), l, mid, pos);
        } else {
            return query(rs(x), mid + 1, r, pos);
        }
    }
#undef ls
#undef rs
} A, B;
int main() {
    cin >> s + 1;
    n = strlen(s + 1);
    for (int i = 1; i <= n; ++i)
        SAM::insert(s[i] - 'a');
    for (int i = 1; i <= cnt; ++i)
        ++c[len[i]];
    for (int i = 1; i <= cnt; ++i)
        c[i] += c[i - 1];
    for (int i = 1; i <= cnt; ++i)
        a[c[len[i]]--] = i;
    for (int i = cnt; i; --i) {
        siz[link[a[i]]] += siz[a[i]];
        pos[link[a[i]]] = max(pos[link[a[i]]], pos[a[i]]);
    }
    for (int i = 1; i <= cnt; ++i) {
        if (siz[i] == 1) {
            int l = len[link[i]], r = len[i];
            A.update(1, 1, n, pos[i] - l, pos[i], l + 1);
            B.update(1, 1, n, pos[i] - r + 1, pos[i] - l, pos[i] + 1);
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << min(A.query(1, 1, n, i), B.query(1, 1, n, i) - i) << endl;
    }
    return 0;
}

T2 解密运算

原题 [THUSC2015] 解密运算

找规律题

先考虑 O(n2)O(n^2) 的暴力

对于

1
2
5 3 
3 0 2 1 1 2

这个数据

1
2
3
4
5
6
0????3
1????0
1????2
2????1
2????1
3????2

因为第一列和最后一列确定，加密排序之后的矩阵大概长这个样子

因为原字符串当作环处理，所以可以确定一些关系

上面的可以确定 x -> y 代表 x 后面可能是 y

1
2
3
4
5
3 -> 0
0 -> 1
2 -> 1
2 -> 3
1 -> 2

然后因为是字典序排序，可以推出来第二列

1
2
3
4
5
6
01???3
12???0
12???2
21???1
23???1
30???2

然后大力递推就能得到整个矩阵

1
2
3
4
5
6
012123
121230
123012
212301
230121
301212

考虑优化这个过程

发现暴力递推的时候，每一个串一定是同一个串的可能关系推出来的

比如第四行全是由第三行给出的可能的顺序推出来的，这样如果我们知道他是从那个串递推就可以 O(n)O(n) 解决了

画个图感性理解一下就是按照权值排序跳 idid 就是原串的递推过程

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
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 2e5 + 5;
int n, m;
struct Data {
    int val, rk;
} a[N];
int main() {
    cin >> n >> m;
    n++;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].val;
        a[i].rk = i;
    }
    sort(a + 1, a + 1 + n, [&](const Data &A, const Data &B) -> bool {
        if (A.val == B.val) {
            return A.rk < B.rk;
        }
        return A.val < B.val;
    });
    int now = a[1].rk;
    for (int i = 1; i < n; i++) {
        cout << a[now].val << " ";
        now = a[now].rk;
    }
    return 0;
}
//Asusetic eru quionours

T3 树

原题 2020省选A卷 树

我还做过（然而是精妙的差分做法，考场上只会大力合并 Trie

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
#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10, K = 22;
typedef long long ll;
class EdgeNode {
  public:
    int v;
    EdgeNode *nxt;
    EdgeNode(EdgeNode *p) {
        nxt = p;
    }
};
template <class T> class ListIterator : public iterator<input_iterator_tag, T> {
  public:
    ListIterator(T *p) {
        _ptr = p;
    }
    ListIterator &operator=(const ListIterator &iter) {
        _ptr = iter._ptr;
    }
    bool operator!=(const ListIterator &iter) {
        return _ptr != iter._ptr;
    }
    bool operator==(const ListIterator &iter) {
        return _ptr == iter._ptr;
    }
    ListIterator &operator++() {
        _ptr = _ptr->nxt;
        return *this;
    }
    ListIterator operator++(int) {
        ListIterator tmp = *this;
        _ptr             = _ptr->nxt;
        return tmp;
    }
    T &operator*() {
        return *_ptr;
    }

  private:
    T *_ptr;
};
class Edge {
    typedef ListIterator<EdgeNode> iterator;

  public:
    EdgeNode *head;
    Edge() {
        head = nullptr;
    }
    void add(int v) {
        head    = new EdgeNode(head);
        head->v = v;
    }
    iterator begin() {
        return iterator(head);
    }
    iterator end() {
        return iterator(nullptr);
    }
};
Edge head[N];
void add(int u, int v) {
    head[u].add(v);
}
namespace Trie {
int ch[N * K][2], cnt[N * K], tot, dcnt[N][K];
void insert(int v, int rt, int x) {
    int now = rt;
    for (int i = 0; i < K; i++) {
        int u = (v >> i) & 1;
        dcnt[x][i] += u;
        if (!ch[now][u])
            ch[now][u] = ++tot;
        now = ch[now][u];
        cnt[now]++;
    }
}
void add1(int rt, int x) {
    int now = rt;
    for (int i = 0; i < K; i++) {
        if (!now)
            return;
        dcnt[x][i] += cnt[ch[now][0]];
        dcnt[x][i] -= cnt[ch[now][1]];
        swap(ch[now][1], ch[now][0]);
        now = ch[now][0];
    }
}
int merge(int x, int y) {
    if (!x || !y)
        return x + y;
    cnt[x] += cnt[y];
    ch[x][0] = merge(ch[x][0], ch[y][0]);
    ch[x][1] = merge(ch[x][1], ch[y][1]);
    return x;
}
} // namespace Trie
ll v[N], rt[N], val[N];
void dfs(int u) {
    using namespace Trie;
    rt[u] = ++tot;
    insert(v[u], rt[u], u);
    for (auto p : head[u]) {
        int v = p.v;
        dfs(v);
        merge(rt[u], rt[v]);
        for (int j = 0; j < K; j++) {
            dcnt[u][j] += dcnt[v][j];
        }
    }
    for (int i = 0; i < K; i++) {
        if (dcnt[u][i] & 1) {
            val[u] += (1 << i);
        }
    }
    add1(rt[u], u);
}
int n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        add(x, i);
    }
    ll ans = 0;
    dfs(1);
    for (int i = 1; i <= n; i++) {
        ans += val[i];
    }
    cout << ans << endl;
    return 0;
}