首页 模拟赛

主席树，树上dp + 分类讨论，最短路

# A. Specijacija

这道题还是非常有实力的。

讨论一下 lca\text{lca} 的位置：

  • 询问的点是祖先关系：那么哪个小是哪个。

  • 不是祖先关系： 只能是某个 aia_i（因为只有在 aia_i 处才有分叉）。

接下来只分析第二种情况。

现在我们知道了 lca\text{lca} 一定是 aia_i，我们还能观察到 aia_i 分别对应最底层两两叶子之间的空隙。

我们把 aia_i 映射到叶子的空隙中，那么 x,yx, y 的 lca\text{lca} 就是 x,yx, y 之间所有出现的 aia_i 的 ii 的最小值。

但是 x,yx, y 之间包含了哪些叶子并不好求。

有个小结论，设 sx,sysx, sy 分别是 x,yx, y 子树内的点，那么 lca(x,y)=lca(sx,sy)lca(x, y) = lca(sx, sy).

所以我们考虑把 x,yx, y 下放到它子树内的某个叶子上，就可以快速求区间最小值了。

这里是下放到 xx 子树内最靠左的叶子。

如何实现这个映射呢？

开一个主席树，从下往上每一层就是一个版本，在叶子层把所有叶子都插入到主席树里。

如果出现一个分叉，就把分叉的右儿子删掉即可。

那么 aia_i 的映射呢？

找到 ii 的右儿子映射的叶子节点编号再减 1 即可。

x,yx, y 是祖先关系的情况就是它们对应的叶子节点编号相同。

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
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define mid ((l + r) >> 1)

using namespace std;

const int N = 1e6 + 10;
int n, m, typ;
int a[N];

int siz[N << 5], ls[N << 5], rs[N << 5];
int rt[N], tot;
 
inline void ins(int &p, int l, int r, int x){
    if(!p) p = ++tot;
    siz[p]++;
    if(l == r) return;
    if(x <= mid) ins(ls[p], l, mid, x);
    else ins(rs[p], mid + 1, r, x);
}

inline void del(int &p, int pre, int l, int r, int x){
    if(!p) p = ++tot;
    siz[p] = siz[pre] - 1;
    if(l == r) return;
    if(x <= mid) rs[p] = rs[pre], del(ls[p], ls[pre], l, mid, x);
    else ls[p] = ls[pre], del(rs[p], rs[pre], mid + 1, r, x);
}

inline int kth(int p, int l, int r, int x){
    if(l == r) return l;
    if(x <= siz[ls[p]]) return kth(ls[p], l, mid, x);
    else return kth(rs[p], mid + 1, r, x - siz[ls[p]]);
}

int mn[N][20];

inline int get(int x){
    int d = sqrt(2 * x);
    if(d * (d + 1) / 2 < x) d++;
    return kth(rt[d], 1, n + 1, x - d * (d - 1) / 2);
}

inline void init(){
    for(int i = 1; i <= n; ++i) mn[get(a[i] + i + 1) - 1][0] = a[i];
    for(int j = 1; j <= 19; ++j)
        for(int i = 1; i + (1 << j) - 1 <= n; ++i)
            mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
}

inline int lca(int l, int r){
    if(l == r) return 1e18;
    if(l > r) swap(l, r); r--;
    int k = log2(r - l + 1);
    return min(mn[l][k], mn[r - (1 << k) + 1][k]);
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> n >> m >> typ;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n + 1; ++i) ins(rt[n + 1], 1, n + 1, i);
    for(int i = n; i >= 1; --i)
        del(rt[i], rt[i + 1], 1, n + 1, kth(rt[i + 1], 1, n + 1, a[i] - i * (i - 1) / 2 + 1));
    init();
    int ans = 0;
    while(m--){
        int x, y; cin >> x >> y;
        if(typ){
            x = (x - 1 + ans) % ((n + 1) * (n + 2) / 2) + 1;
            y = (y - 1 + ans) % ((n + 1) * (n + 2) / 2) + 1;
        }
        cout << (ans = min({x, y, lca(get(x), get(y))})) << '\n';
    }
    return 0;
}

# B. Svjetlo

巨大分类讨论。

设 fi,j,kf_{i, j, k} 表示子树 ii 内有 起点/终点 中的 jj 个，且当前 ii 的状态为 kk 时的最小操作次数。

找到一个 si=0s_i = 0 的 ii 跑一遍树形 dp\text{dp} 即可，因为这个点一定会被经过。

最后答案就是 fi,2,1f_{i, 2, 1}。

转移过程讨论接头如何合并，然后 0/1 状态是否需要改变。

就不细说了（

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

using namespace std;

const int N = 5e5 + 10;
int n;
char s[N];
vector <int> G[N];
int siz[N], f[N][3][2];

inline void Min(int &x, int y) {x = x < y ? x : y;}

inline void dfs(int x, int fa){
    for(int j = 0; j < 3; ++j) f[x][j][siz[x]] = 1;
    for(auto y : G[x]){
        if(y == fa) continue;
        dfs(y, x), siz[x] += siz[y];
        if(!siz[y]) continue;
        int g[3][2];
        memset(g, 0x3f, sizeof(g));
        for(int k = 0; k < 2; ++k){
            Min(g[0][k], f[x][0][k] + f[y][0][0] + 3);
            Min(g[0][k], f[x][0][!k] + f[y][0][1] + 1);
            Min(g[1][k], f[x][1][k] + f[y][0][0] + 3);
            Min(g[1][k], f[x][1][!k] + f[y][0][1] + 1);
            Min(g[1][k], f[x][0][k] + f[y][1][1]);
            Min(g[1][k], f[x][0][!k] + f[y][1][0] + 2);
            Min(g[2][k], f[x][2][k] + f[y][0][0] + 3);
            Min(g[2][k], f[x][2][!k] + f[y][0][1] + 1);
            Min(g[2][k], f[x][1][k] + f[y][1][1]);
            Min(g[2][k], f[x][1][!k] + f[y][1][0] + 2);
            Min(g[2][k], f[x][0][k] + f[y][2][0] + 1);
            Min(g[2][k], f[x][0][!k] + f[y][2][1] + 3);
        }
        memcpy(f[x], g, sizeof(g));
    }
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> n >> (s + 1);
    for(int i = 1; i < n; ++i){
        int u, v; cin >> u >> v;
        G[u].pb(v), G[v].pb(u);
    }
    for(int i = 1; i <= n; ++i) siz[i] = (s[i] == '0');
    memset(f, 0x3f, sizeof(f));
    for(int i = 1; i <= n; ++i)
        if(s[i] == '0') {
            dfs(i, 0);
            cout << f[i][2][1] << '\n';
            return 0;
        }
    return 0;
}

# C. Portal

连边，跑最短路即可。

  1. 向四周连边权为 1 的边。

  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
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;

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

    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 = 510;
typedef pair<int, int> P;
int n, m, s, t;
char ch[N][N];
int id[N][N], idx;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
bool vis[N][N];
int d[N][N], to[N][N][4];

inline bool chk(int x, int y){
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

inline void bfs(){
    queue <P> q;
    memset(d, 0x3f, sizeof(d));
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(ch[i][j] == '#') q.push({i, j}), vis[i][j] = 1, d[i][j] = 0;
    while(!q.empty()){
        int x = q.front().fi, y = q.front().se; q.pop();
        for(int i = 0; i < 4; ++i){
            int tx = x + dx[i], ty = y + dy[i];
            if(chk(tx, ty) && !vis[tx][ty]){
                d[tx][ty] = d[x][y] + 1, vis[tx][ty] = 1, q.push({tx, ty});
            }
        }
    }
}

struct node{
    int v, w, nxt;
}edge[N * N * 10];
int head[N * N], tot;
int dis[N * N];

inline void add(int x, int y, int z){
    edge[++tot] = (node){y, z, head[x]}, head[x] = tot;
}

inline int dij(){
    memset(dis, 0x3f, sizeof(dis));
    priority_queue <P, vector<P>, greater<P> > q;
    q.push(P(0, s)), dis[s] = 0;
    while(!q.empty()){
        int x = q.top().se, d = q.top().fi; q.pop();
        if(dis[x] < d) continue;
        for(int i = head[x]; i; i = edge[i].nxt){
            int y = edge[i].v;
            if(dis[y] > dis[x] + edge[i].w)
                dis[y] = dis[x] + edge[i].w, q.push(P(dis[y], y));
        }
    }
    return dis[t];
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), m = read();
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) id[i][j] = ++idx;
    for(int i = 1; i <= n; ++i){
        scanf("%s", ch[i] + 1);
        for(int j = 1; j <= m; ++j){
            if(ch[i][j] == 'C') s = id[i][j];
            if(ch[i][j] == 'F') t = id[i][j];
        }
    }
    bfs();
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(ch[i][j] != '#'){
                to[i][j][0] = (ch[i - 1][j] == '#') ? id[i][j] : to[i - 1][j][0];
                to[i][j][3] = (ch[i][j - 1] == '#') ? id[i][j] : to[i][j - 1][3];
            }
    for(int i = n; i >= 1; --i)
        for(int j = m; j >= 1; --j)
            if(ch[i][j] != '#'){
                to[i][j][1] = (ch[i][j + 1] == '#') ? id[i][j] : to[i][j + 1][1];
                to[i][j][2] = (ch[i + 1][j] == '#') ? id[i][j] : to[i + 1][j][2];
            }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j){
            if(ch[i][j] == '#') continue;
            for(int k = 0; k < 4; ++k){
                int x = i + dx[k], y = j + dy[k];
                if(ch[x][y] != '#') add(id[i][j], id[x][y], 1);
                if(to[i][j][k] != id[i][j]) add(id[i][j], to[i][j][k], d[i][j]);
            }
        }
    int ans = dij();
    if(ans > 1e9) puts("nemoguce");
    else write(ans), puts("");
    return 0;
}

更新于 阅读次数 次