首页 模拟赛

树的重心 + 二分，后缀自动机 + LCT + 树状数组，搜索

# A. 跳蚤王国的宰相

一上来就冲了个换根 dp\text{dp}，然后过了小样例和自己手造的样例，感觉还挺稳的，考到一半发现题看假了，样例也算假了，想成要删多少个点了（我就说这题怎么这么水 QwQ）。

回到本题，首先重心的答案肯定是 0。

考虑重心的性质：如果一个点为重心，那么它的所有子树的大小都不大于 n2\frac n2，

所以我们只要把一个点为根的情况下它所有子树的大小全部减到 n2\frac n2 以下即可。

详细过程：

  • 先把重心拎出来，把它的所有子树从大到小排序，并做个前缀和存到 sumisum_i 里。然后依次递归处理每一棵子树。

  • 对于每棵子树进行分类讨论，设 idid 为子树的根，xx 为每棵字数内的点：

    • 如果 idid 本身就是重心（重心可能有多个），直接更新答案 ansx=(x !=id)ans_x = (x\ != id)，如果当前的 xx 不是 idid 只需要切一条边即可。
    • 如果减去 sumpos[x]−1sum_{pos[x] - 1} 之后 xx 可以成为重心，那么在 1∼pos[x]−11 \sim pos[x] - 1 之间二分需要切掉多少条边（也就是切多少棵子树，然后把这些子树接到 xx 下面）。
    • 如果减去之后 xx 依然不能成为重心，那么就去 pos[x]+1∼totpos[x] + 1 \sim tot 里面二分找答案。

    各种边界什么的就不细讲了，比较繁琐，直接看代码吧。

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
#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

namespace IO{
    inline ll read(){
        ll x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e6 + 10;
int n, rt;
vector <int> g[N];
int siz[N], mx[N];
int ans[N];

inline void getroot(int x, int fa){
    siz[x] = 1, mx[x] = 0;
    for(auto y : g[x]){
        if(y == fa) continue;
        getroot(y, x);
        siz[x] += siz[y], mx[x] = max(mx[x], siz[y]);
    }
    mx[x] = max(mx[x], n - siz[x]);
    if(mx[x] < mx[rt] || !rt) rt = x;
}

int s[N], tot, id;
int pos[N], sum[N];

inline bool cmp(int x, int y) {return siz[x] > siz[y];}

inline void dfs(int x, int fa, int id){
    int w = n - siz[x];
    if(n - siz[id] <= n / 2) ans[x] = (x != id);
    else if(w - (sum[pos[id] - 1]) <= n / 2){
        int l = 0, r = pos[id] - 1;
        while(l < r){
            int mid = (l + r) >> 1;
            if(w - sum[mid] <= n / 2 || n - siz[id] - sum[mid - 1] <= n / 2) r = mid;
            else l = mid + 1;
        }
        ans[x] = l;
    }else{
        int l = pos[id] + 1, r = tot;
        while(l < r){
            int mid = (l + r) >> 1;
            if(w - sum[mid] + siz[id] <= n / 2 || n - sum[mid - 1] <= n / 2) r = mid;
            else l = mid + 1;
        }
        ans[x] = l - 1;
    }
    for(auto y : g[x]) if(y != fa) dfs(y, x, id);
}

inline void solve(){
    for(auto y : g[rt]) s[++tot] = y;
    sort(s + 1, s + 1 + tot, cmp);
    for(int i = 1; i <= tot ; ++i) sum[i] = sum[i - 1] + siz[s[i]], pos[s[i]] = i;
    for(auto y : g[rt]) dfs(y, rt, y);
}

signed main(){
    n = read();
    for(int i = 1; i < n; ++i){
        int u = read(), v = read();
        g[u].pb(v), g[v].pb(u);
    }
    getroot(1, 0), getroot(rt, 0);
    solve();
    for(int i = 1; i <= n; ++i) write(ans[i]), puts("");
    return 0;
}
// X.K.

# B. 事情的相似度

考场上完全没思路，暴力也懒得打了（其实是没时间）。

首先转换一下题意：建出后缀自动机，题目就是求 l∼rl \sim r 内两个串的最长公共后缀，就是所代表节点的 lcalca 的 lenlen。

把询问离线下来，对于每个 rr 依次处理。

每加进去一个字符，我们把 SAM\text{SAM} 中相应的点到根的路径覆盖上颜色 ii（ii 为字符编号），这个过程使用 LCT\text{LCT} 维护。

然后用树状数组统计从根到每个点的最大值（这里由于是从根到每个点，所以在树状数组上是一段后缀，插入和查询的循环要反过来）。查询的时候直接查询就可以了。

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>
#define ll long long
#define pb push_back
#define fi first
#define se second

using namespace std;

namespace IO{
    inline ll read(){
        ll x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e5 + 10;
typedef pair<int, int> P;
int n, m, lst = 1, tot = 1;
char s[N];
vector <P> q[N];
int pos[N], len[N], fa[N];

namespace SAM{
    int siz[N], ch[N][27];
    inline int insert(int c){
        int p = lst, np = ++tot;
        lst = np;
        len[np] = len[p] + 1, siz[np]++;
        while(p && !ch[p][c]) ch[p][c] = np, p = fa[p];
        if(!p) fa[np] = 1;
        else{
            int q = ch[p][c];
            if(len[q] == len[p] + 1) fa[np] = q;
            else{
                int nq = ++tot;
                len[nq] = len[p] + 1, fa[nq] = fa[q], siz[nq] = 0;
                for(int i = 0; i < 26; ++i) ch[nq][i] = ch[q][i];
                while(p && ch[p][c] == q) ch[p][c] = nq, p = fa[p];
                fa[q] = fa[np] = nq;
            }
        }
        return np;
    }
}
using SAM :: insert;

namespace BIT{
    int c[N], mx[N];

    inline void add(int x, int v){
        for(; x; x -= x & (-x)) c[x] = max(c[x], v);
    }

    inline int query(int x){
        int res = 0;
        for(; x < N; x += x & (-x)) res = max(res, c[x]);
        return res;
    }
}
using BIT :: add;
using BIT :: query;

namespace LCT{
    #define ls ch[x][0]
    #define rs ch[x][1]

    int ch[N][2], col[N], tag[N];

    inline bool nroot(int x) {return ch[fa[x]][0] == x || ch[fa[x]][1] == x;}

    inline void pushdown(int x){
        if(tag[x]){
            if(ls) col[ls] = tag[ls] = tag[x];
            if(rs) col[rs] = tag[rs] = tag[x];
            tag[x] = 0;
        }
    }

    inline void push(int x){
        if(nroot(x)) push(fa[x]);
        pushdown(x);
    }

    inline void rotate(int x){
        int y = fa[x], z = fa[y], k = ch[y][1] == x, w = ch[x][k ^ 1];
        if(nroot(y)) ch[z][ch[z][1] == y] = x;
        ch[x][k ^ 1] = y, ch[y][k] = w;
        if(w) fa[w] = y;
        fa[y] = x, fa[x] = z;
    }

    inline void splay(int x){
        push(x);
        int y = x, z;
        while(nroot(x)){
            y = fa[x], z = fa[y];
            if(nroot(y)) rotate((ch[z][1] == y) ^ (ch[y][1] == x) ? x : y);
            rotate(x);
        }
    }

    inline void access(int x, int c){
        int y;
        for(y = 0; x; x = fa[y = x]) splay(x), add(col[x], len[x]), rs = y;
        col[y] = tag[y] = c;
    }
}
using LCT :: access;

int ans[N];

signed main(){
    n = read(), m = read();
    scanf("%s", s + 1);
    for(int i = 1; i <= n; ++i) pos[i] = insert(s[i] - '0');
    for(int i = 1; i <= m; ++i){
        int l = read(), r = read();
        q[r].pb(P(l, i));
    }
    for(int i = 1; i <= n; ++i){
        access(pos[i], i);
        for(auto x : q[i]) ans[x.se] = query(x.fi);
    }
    for(int i = 1; i <= m; ++i) write(ans[i]), puts("");
    return 0;
}
// X.K.

# C. 蛐蛐国的修墙方案

一开始写了个 O(n)O(n) 的做法（贪心左边能填括号时就填左括号），然后过小样例了，手造了几组样例也都过了，感觉自己非常 nbnb。

然后生成了 (()())() 的所有合法序列，放到代码里跑了跑，结果一大堆最后一位是 ( 的，于是知道自己想假了。又想了想，感觉报搜找环就行，然后找到环之后让环中编号最小的点为 (，剩下的依次推过去，测了一车小样例都过了，感觉自己非常稳。

离比赛结束的时候教练给大样例了，测了一发，然后 WA\text{WA} 了？？？

立马意识到还得 2cnt2^{cnt} 枚举哪些边为 (，哪些边为 )，cntcnt 是环的个数。

一顿乱改总算是过了。

由于一个环只有两种填左右括号的情况，所以复杂度就是 O(2cnt)O(2^{cnt}) 的，2 元环可以直接令小的为 (，所以我们只需要考虑 4 元环及以上，所以复杂度最大是 O(2n4)O(2^{\frac n4}) 的。

本题保证有解（虽然没写），无解的情况是出现奇环。

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
#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

namespace IO{
    inline ll read(){
        ll x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 110;
int n, cnt, top, flag, tot;
int p[N], stk[N], a[N];
char s[N];
bool vis[N];
vector <int> g[N];

inline void dfs(int x){
    if(vis[x]) return void();
    stk[++top] = x, vis[x] = 1, dfs(p[x]);
}

inline void prework(int x){
    top = 0, dfs(x);
    if(top == 2) a[min(stk[1], stk[2])] = 1;
    else{
        tot++;
        for(int i = 1; i <= top; ++i) g[tot].pb(stk[i]);
    }
}

inline bool check(){
    int cnt = 0;
    for(int i = 1; i <= n; ++i){
        cnt += (a[i] ? 1 : -1);
        if(cnt < 0) return 0;
    }
    for(int i = 1; i <= n; ++i) putchar(a[i] ? '(' : ')');
    puts("");
    return 1;
}

inline void solve(int x){
    if(flag) return;
    if(x == tot + 1){
        if(check()) flag = 1;
        return;
    }
    for(int i = 0; i < (int)g[x].size(); ++i) a[g[x][i]] = i & 1;
    solve(x + 1);
    for(int i = 0; i < (int)g[x].size(); ++i) a[g[x][i]] ^= 1;
    solve(x + 1);
}

signed main(){
    // freopen("C.in", "r", stdin);
    // freopen("C.out", "w", stdout);
    n = read();
    for(int i = 1; i <= n; ++i) p[i] = read();
    for(int i = 1; i <= n; ++i) if(!vis[i]) prework(i);
    solve(1);
    return 0;
}
// X.K.

阅读次数 次