https://acm.ecnu.edu.cn/contest/463/

D. 赌怪

 

题意：A，B两人轮流从 [1,1018][1, 10^{18}] 各抽取 nn 张牌，可能重复。抽完后，A 先打出一张牌，B 必须打出一张比 A 大的牌。打出就丢掉。若 B 无法出牌则 A 赢，否则 B 赢。问 A 赢的概率。

卡特兰数

数字范围很大，可以近似认为不会抽到重复的牌。

把 A，B 抽到的牌放一起从小到大排序，必须满足在任意位置 p，从开始位置到位置 p 这个区间中，A 牌的个数大于等于 B 牌的个数。也可以说 A 的最小的牌小于 B 的最小的牌，A 的次小牌小于 B 的次小牌。这两种说法等价。

这其实就和括号序列的合法性是一样的。A 视为左括号，B 为右括号。

所以牌的排列方式个数就是 n 对括号的合法序列数，也就是卡特兰数。

ans=1n+1(2nn)(2nn)=1n+1ans=\frac{\frac 1{n+1}\binom {2n}n}{\binom {2n}n}=\frac{1}{n+1} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int n;

int main(){
    scanf("%d", &n);
    printf("%.10lf\n", 1.0 - 1.0 / (n + 1));
    return 0;
}

 

E. 异或树

 

题意：给定一棵 1 为根的树，有点权 1≤ai≤231−11 \le a_i \le 2^{31} - 1，任意一对有祖先后代关系的点对 (u,v)(u, v)，产生价值 value(u,v)=av⊕auvalue_{(u,v)} = a_v \oplus a_u，问树上前 kk 大的价值。2≤n≤5×105,1≤k≤min⁡(∑vdepv−1,5×105)2 \le n \le 5 \times 10^{5},1 \le k \le \min(\sum_{v}dep_v - 1, 5\times 10^{5})

可持久化字典树

容易想到，对于点 uu，可以用字典树求出它与它的祖先产生的价值中的第 ii 大。（字典树上记录每个节点的个数，并从根往下走）

但由于预先不知道要求第几大，所以要存好在每个点时建的字典树，也就是可持久化字典树。

dfs遍历，建好可持久化字典树。

维护一个大根的优先队列，先把每个点与它祖先产生的最大价值压入优先队列。

循环 kk 次，每次弹出队首，若这个节点是第 ii 次被弹出，则查询它与祖先产生的第 i+1i+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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int n, k;
int a[N];
vector<int> G[N];

struct perTrie {
    int tot, rt[N], ch[N * 33][2], sum[N * 33];

    void insert(int o, int lst, int v) {
        for (int i = 31; i >= 0; i--) {
            sum[o] = sum[lst] + 1;
            int c = ((v >> i) & 1);
            if (!ch[o][c])ch[o][c] = ++tot;
            ch[o][c ^ 1] = ch[lst][c ^ 1];
            o = ch[o][c];
            lst = ch[lst][c];
        }
        sum[o] = sum[lst] + 1;
    }
} T;

void dfs(int u, int _fa) {
    T.rt[u] = ++T.tot;
    T.insert(T.rt[u], T.rt[_fa], a[u]);
    for (int v: G[u]) {
        if (v == _fa)continue;
        dfs(v, u);
    }
}

int qry(int u, int q) {
    int o = T.rt[u];
    int v = a[u];
    int res = 0;
    if (T.sum[o] < q)return -1;
    for (int i = 31; i >= 0; i--) {
        int c = (v >> i) & 1;
        if (T.sum[T.ch[o][c ^ 1]] >= q) {
            res |= (1 << i);
            o = T.ch[o][c ^ 1];
        } else {
            q -= T.sum[T.ch[o][c ^ 1]];
            o = T.ch[o][c];
        }
    }
    return res;
}

priority_queue<pii> q;
int cnt[N];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)scanf("%d", &a[i]);

    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        q.push({qry(i, 1), i});
        cnt[i] = 1;
    }
    for (int i = 1; i <= k; i++) {
        int u = q.top().second, val = q.top().first;
        q.pop();
        printf("%d\n", val);
        cnt[u]++;
        int nv = qry(u, cnt[u]);
        if (nv != -1)q.push({nv, u});
    }
    return 0;
}