Cauphenuny's blog

20200116~17 考试总结

发表于 更新于 分类于 ，

这两天考了学长出的一套省选模拟题。（似乎是 Matthew99 /se

Day 1

A

建出 SAM 后就是在 parent tree 上找 LCA。

B

是 CF708c 的加强版。

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
//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma Gcc optimize(2)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdarg>
#include<typeinfo>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
template <class T> bool cmax(T &a, T b) {return b > a ? (a = b, 1) : 0;}
template <class T> bool cmin(T &a, T b) {return b < a ? (a = b, 1) : 0;}
void read(char *s) {scanf("%s", s);} void read(char &c) {scanf("%c", &c);}
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int fa = 0;
    while (!isdigit(c)) { fa ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= fa ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

const int MAXN = 1e6 + 10;

struct Line {
    int next;
    int to;
} e[MAXN << 1];

int n, tot, rt, siz[MAXN], head[MAXN], dep[MAXN];
int f[MAXN], g[MAXN];

void addEdge(int u, int v) {
    tot++;
    e[tot].to = v;
    e[tot].next = head[u];
    head[u] = tot;
}

void readin() {
    fastin >> n;
    for (int i = 1, u, v; i < n; i++) {
        fastin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }
}

void pre(int u, int fa) {
    siz[u]++;
    int maxsiz = 0;
    for (int i = head[u], v; i; i = e[i].next) {
        v = e[i].to;
        if (v == fa) continue;
        pre(v, u);
        siz[u] += siz[v];
        cmax(maxsiz, siz[v]);
    }
    if ((maxsiz <= n / 2) && (n - siz[u] <= n / 2)) {
        rt = u;
    }
}

void dfs(int u, int fa) {
    siz[u]++;
    dep[u] = dep[fa] + 1;
    for (int i = head[u], v; i; i = e[i].next) {
        v = e[i].to;
        if (v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
    }
}

int cnt, sum[MAXN];
struct Son {
    int siz, id;
    bool operator < (const Son &s) {
        return siz > s.siz;
    }
} son[MAXN];

void init() {
    for (int i = head[rt], v; i; i = e[i].next) {
        v = e[i].to;
        cnt++;
        son[cnt].siz = siz[v];
        son[cnt].id = v;
    }
    sort(son + 1, son + cnt + 1);
    for (int i = 1; i <= cnt; i++) {
        sum[i] = sum[i - 1] + son[i].siz;
    }
    int pos = lower_bound(sum + 1, sum + cnt + 1, n / 2) - sum;
    for (int i = 1, u; i <= pos; i++) {
        u = son[i].id;
        f[u] = pos - 1;
        g[u] = n - sum[pos];
    }
    for (int i = n, u, p = pos; i >= pos + 1; i--) {
        u = son[i].id;
        if (sum[p - 1] + siz[u] >= n / 2) {
            p--;
        }
        f[u] = p;
        g[u] = n - sum[f[u]] - siz[u];
    }
}

void calc(int u, int fa) {
    f[u] = f[fa] + 1;
    g[u] = siz[fa] - siz[u];
    if (g[fa] + siz[fa] - siz[u] <= n / 2) {
        f[u] = f[fa];
        g[u] = siz[fa] - siz[u] + g[fa];
    }
    for (int i = head[u], v; i; i = e[i].next) {
        v = e[i].to;
        if (v == fa) continue;
        calc(v, u);
    }
}

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

    readin();

    pre(1, 0);
    memset(siz, 0, sizeof(siz));
    dfs(rt, 0);

    init();
    for (int i = 1, u; i <= cnt; i++) {
        u = son[i].id;
        for (int j = head[u], v; j; j = e[j].next) {
            v = e[j].to;
            if (v == rt) continue;
            calc(v, u);
        }
    }

    for (int i = 1; i <= n; i++) {
        printf("%d\n", f[i]);
    }
    return 0;
}

T3

考虑将循环置换分解，dfs 枚举每个置换。

但是这样的复杂度是 O(250)O(2^{50}) 的，无法接受，但是考虑一个由两个元素组成的环，显然编号较小的一端放左括号更优。

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
//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdarg>
#include <vector>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
#define debugs(x) fputs(x"\n", stderr)
using namespace std;
template <class T> bool cmax(T &a, T b) { return b > a ? (a = b, 1) : 0; }
template <class T> bool cmin(T &a, T b) { return b < a ? (a = b, 1) : 0; }
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

const int MAXN = 110;

int n;
int p[MAXN];
int a[MAXN];
int vis[MAXN];
int st[MAXN];
int tot;
vector <int> rep[MAXN];

void clear() {
    n = tot = 0;
    memset(p, 0, sizeof(p));
    memset(a, 0, sizeof(a));
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < MAXN; i++) rep[i].clear();
}

void pre(int u) {
    if (vis[u]) return;
    vis[u] = 1;
    rep[tot].push_back(u);
    pre(p[u]);
}

bool check() {
    for (int i = 1, val = 0; i <= n; i++) {
        if (a[i]) val++;
        else      val--;
        if (val < 0) return false;
    }
    return true;
}

void print() {
    for (int i = 1; i <= n; i++) {
        if (a[i]) putchar('(');
        else      putchar(')');
    }
    putchar('\n');
}

void dfs(int now) {
    if (now == tot + 1) {
        if (check()) {
            print();
            exit(0);
        }
        return;
    }
    //debug(now);
    if (rep[now].size() > 2) {
        for (long unsigned int i = st[now] ^ 1; i < rep[now].size(); i += 2) {
            //if (i == 0) debugf("chosed [%d]-%d\n", rep[now][0], rep[now][1]);
            //else if (i == 1) debugf("chosed [%d]-%d\n", rep[now][1], rep[now][0]);
            a[rep[now][i]] = 1;
            a[rep[now][i ^ 1]] = 0;
            //cerr<<"small= "<<rep[now][i]<<" big= "<<rep[now][i^1]<<endl;
        }//cerr<<endl;
        dfs(now + 1);
        for (long unsigned int i = st[now] ^ 1; i < rep[now].size(); i += 2) {
            a[rep[now][i]] = 0;
            //if ((i ^ 1) >= rep[now].size())
            //    debugs("fuck2!");
            a[rep[now][i ^ 1]] = 1;
        }
        dfs(now + 1);
        for (long unsigned int i = 0; i < rep[now].size(); i++) {
            a[rep[now][i]] = 0;
        }
    } else {
        dfs(now + 1);
    }
}

int main() {
    fastin >> n;
    for (int i = 1; i <= n; i++) fastin >> p[i];
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            tot++;
            pre(i);
        }
    }
    for (int i = 1; i <= tot; i++) {
        int maxx = 0;
        //int minx = 0x3f3f3f3f;
        for (auto j = 0lu; j < rep[i].size(); j++) {
            if (cmax(maxx, rep[i][j])) {
                st[i] = j & 1;
            }
        }
        if (rep[i].size() == 2) {
            a[min(rep[i][0], rep[i][1])] = 1;
            a[max(rep[i][0], rep[i][1])] = 0;
        }
    }
    //debug(tot);
    //for (int i = 1; i <= tot; i++) {
    //    sort(rep[i].begin(), rep[i].end());
    //}
    //for (int i = 1; i <= tot; i++) {
    //    for (int j = 0; j < (int)rep[i].size(); j++) {
    //        debugf("%d ", rep[i][j]);
    //    }
    //    debugf("\n");
    //}
    dfs(1);
    clear();
    return 0;
}

Day 2