Algorithm

Kick Start 2020 Round D

题目：https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff08

A. Record Breaker

太简单，不说了

B. Alien Piano

一个简单的动态规划

C. Beauty of tree

题意

给定一棵N个点的树，根节点为1。Amadea会随机选择一个节点，将这个点涂黑，然后从这个点开始到根的路径上，每隔A个点涂黑一个。然后，Bilva随机选择一个节点，将这个点涂黑，然后从这个点到根的路径上，每隔B个点涂黑一个。设最终被涂黑的点的个数为X。求X的数学期望。$N\le5\times10^5$

做法

显然，子树中涂的点到子树根的距离不确定，所以没法用树形概率DP的方法。我们只能从期望的计算方法来思考。Amadea和Bilva的选择共有n^2种可能，所以答案等于每种选法中被涂黑的点数之和，然后除以$n^2$。

于是可以想到，我们不是按照每种选法计算，而是去计算每个点会在多少种选法中被涂黑。对于节点v，计算它的子树中到v的距离模A为0的节点个数（设为a），以及它的子树中到v的距离模B为0的节点个数（设为b）。由容斥原理，v会被涂黑的选法个数$=a\times n+b\times n-a\times b$。

那么如何得到每个节点的a和b呢？我们可以dfs，得到每个节点的深度。在dfs过程中，我们可以维护两个cnt数组，记录当前dfs过的点的深度分别模A和B结果的个数。那么dfs完一棵子树，根据cnt数组的变化即可得到当前节点的a和b。于是dfs一遍即可，时间复杂度$O(n)$。

暴力维护a和b

其实我刚开始没想到dfs一遍就可以。我想的是暴力维护。例如计算a。每个点维护一个map，map[x]表示v的子树中，到v的距离模A为x的点的个数。合并时，使用启发式合并。显然是能做的，应该也不会超时，用hash map，总复杂度O(nlogn)。

代码

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
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

int n, A, B;
vector<int> children[501111];
int deep[501111];
int rec[2][501111];
int ans[501111][2];

void Dfs(int v, int dep) {
    int a = rec[0][dep % A];
    int b = rec[1][dep % B];
    deep[v] = dep;
    rec[0][dep % A]++;
    rec[1][dep % B]++;
    for (int y: children[v]) {
        Dfs(y, dep + 1);
    }
    ans[v][0] = rec[0][dep % A] - a;
    ans[v][1] = rec[1][dep % B] - b;
}

double Work() {
    for (int i = 0; i < 2; i++) {
        for (int j = 1; j <= n; j++) rec[i][j] = 0;
    }
    for (int i = 1; i <= n; i++) {
        ans[i][0] = ans[i][1] = 0;
    }
    Dfs(1, 0);
    long long tot = 0;
    for (int i = 1; i <= n; i++) {
        tot += (long long)n * (ans[i][0] + ans[i][1]) - (long long)ans[i][0] * ans[i][1];
    }
    long long tmp = (long long)n * n;
    return 1.0 * tot / tmp;
}

void AAAAA() {
    int T;
    cin >> T;
    for (int  tt = 1; tt <= T; tt++) {
        cin >> n >> A >> B;
        for (int i = 1; i <= n; i++) children[i].clear();
        for (int i = 1; i <= n - 1; i++) {
            int x;
            cin >> x;
            children[x].push_back(i + 1);
        }
        printf("Case #%d: %.12f\n", tt, Work());
    }
}


int main() {
    AAAAA();
    return 0;
}

D. Locked Doors

题意

有一行n个房间，编号1到n。相邻房间之间有一扇门，门的编号为1到n-1。每个门有一个困难度Di。Di互不相同。开始时门都关着。

如果一个人开始时在房间x，那么他会在能打开的两扇门中选择一扇困难度小的门打开。打开的门会一直开着。然后他一直进行此流程，经过n-1步之后，他会打开所有的门。

现在有Q个询问，每个询问给定S和K，假设开始时人在房间S，那么他访问的第K个房间是哪个。$n,Q\le10^5$

做法

没法模拟，所以需要观察一些性质。

很容易发现，打开的门是从S开始往左右不断延伸的。如果左边要打开门L，那么此时，右边延伸到的位置R一定满足：D[R]>=max(D[L], D[L+1]…D[S])。于是二分这个L，找到对应的R，判断是否>=K即可。查询最大值用ST表。时间复杂度O(qlogn)。

代码

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
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <stack>
#include <map>

using namespace std;

int N, Q, S, K;
int D[101111];
int log[101111];
int go[101111];
int f[101111][20];
map<int, int> pos;

const int inf = 999999999;

void Prepare() {
    for (int i = 0; i <= N; i++) pos[D[i]] = i;
    for (int i = 0; i <= N; i++) f[i][0] = D[i];
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i <= N; i++) {
            int t = i + (1 << (j - 1));
            if (t < N) f[i][j] = max(f[i][j - 1], f[t][j - 1]);
        }
    }
    log[1] = 0;
    for (int i = 2; i <= N + 2; i++) {
        if (i == (i & -i)) log[i] = log[i - 1] + 1;
        else log[i] = log[i - 1];
    }
    stack<int> s;
    s.push(N);
    for (int i = N - 1; i >= 0; i--) {
        while (D[i] > D[s.top()]) s.pop();
        go[i] = s.top();
        s.push(i);
    }
}

int Getmax(int l, int r) {
    int len = r - l + 1;
    int t = log[len];
    return max(f[l][t], f[r - (1 << t) + 1][t]);
}

int Calc(int p) {
    int x = Getmax(p, S - 1);
    int a = pos[x];
    int b = go[a];
    return b - p;
}

int Work() {
    if (K == 1) return S;
    int l = 1, r = S - 1, res = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        int num = Calc(mid);
        if (num + 1 >= K) {
            res = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    int num = Calc(res);
    if (num + 1 == K) return res;
    else return res + K;
}

void AAAAA() {
    int T;
    cin >> T;
    for (int  tt = 1; tt <= T; tt++) {
        cin >> N >> Q;
        for (int i = 1; i <= N - 1; i++) cin >> D[i];
        D[0] = inf;
        D[N] = inf;
        Prepare();
        printf("Case #%d: ", tt);
        while (Q--) {
            cin >> S >> K;
            printf("%d ", Work());
        }
        printf("\n");
    }
}

int main() {
    AAAAA();
    return 0;
}