跳转至

250707 模拟赛

BOSS 树（boss）

给定一棵 \(n\) 个点的有根树，根节点是 \(1\) 号节点。你需要进行若干次操作，每次操作你可以删除至多 \(m\) 个没有父亲的节点。注意一次操作在一瞬间完成，即先选择 \(m\) 个符合要求的节点，再进行删除。问最少操作多少次可以将整棵树删空。

\(n\le 10^5\)

显然，我们优先删除更深的树。并且可以使用归纳证明在深度相同的情况下删除的顺序不影响最终的答案。

黄金树的召唤（tree）

给定一棵 \(n\) 个节点的有根树，点有两个点权 \(a_u\) 和 \(p_u\)，其中 \(p_u\) 是 \((0,1)\) 之间的实数。有一些节点将被选中，具体规则如下：

  • 若当前节点 \(u\) 存在一个直系儿子被选中了，那么 \(u\) 不可能被选中；
  • 否则 \(u\) 以 \(p_u\) 的概率被选中；

当一个节点 \(u\) 被选中，它会给子树内所有被选中的节点（不包含 \(u\)）增加 \(a_u\) 的价值（可能为负）。一个节点可以选择不接受祖先产生的价值（此时其价值为 \(0\)）。问总价值期望的最大值是多少。2

\(n\le 5\times 10^5,\ |a_i|\le 10^4\)

根据期望的线性性，问题转化为对每个节点 \(u\) 求出钦定 \(u\) 被选中的情况下其价值的期望 \(ans_u\)，以及每个节点被选中的概率 \(f_u\)。\(f_u\) 显然是容易求得的，转移如下：

\[ f_u=\Big(\prod_{v\in to[u]}1-f_v\Big)p_u \]

考虑如何求出 \(ans_u\)。注意到其价值只可能来源于其祖先，因此考虑 dfs，将链上的贡献合并。记事件 \(u\) 表示 \(u\) 节点被选中。先考虑一个祖先 \(t\) 对 \(u\) 的贡献，如下：

\[ P(t|u)a_t \]

我们希望从它转移到它的一个儿子 \(v\)，考虑 \(v\) 得到的贡献

\[ \begin{align*} P(t|v)a_t&=P(t\overline u|v)a_t+P(tu|v)a_t\\ &=P(t\overline u|v)a_t\\ &=P(t|\overline uv)P(\overline u|v)a_t\\ &=P(t|\overline u)P(\overline u|v)a_t\\ &=P(t|\overline u)a_t\\ \end{align*} \]

我们似乎需要额外维护 \(P(t|\overline u)a_t\) 来解决子节点的贡献。因此记

\[ e_{u,1}=P(t|u)a_t\\ e_{u,2}=P(t|\overline u)a_t \]

现在考虑如何转移 \(e_{v,2}\)：

\[ \begin{align*} e_{v,2}&=P(t|\overline v)a_t\\ &=P(tu|\overline v)a_t+P(t\overline u|\overline v)a_t\\ &=P(t|u\overline v)P(u|\overline v)a_t+P(t|\overline u\overline v)P(\overline u|\overline v)a_t\\ &=P(t|u)P(u|\overline v)a_t+P(t|\overline u)P(\overline u|\overline v)a_t\\ &=\frac{f[u]}{1-f[v]}e_{u,1}+(1-\frac{f[u]}{1-f[v]})e_{u,2} \end{align*} \]

枚举 \(u\) 的所有祖先 \(t\)，将它们的贡献求和，\(e_{u,1}\) 就是 \(u\) 钦定选时期望的价值。注意向 \(e_{v,2}\) 转移时要额外加上 \(u\) 的贡献 \(a_u\)。

代码 
 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
#include<iostream>
#include<iomanip>
#include<cstdio>
#define ld long double
using namespace std;
const int N = 5e5 + 10;

struct Edge {
    int v, next;
} pool[N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n;
int a[N];
ld p[N], f[N];
ld ans[N]; // e1
ld sum;

void dfs1(int u) {
    f[u] = p[u];
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        dfs1(v);
        f[u] *= (1 - f[v]);
    }
}

void dfs2(int u, ld e1, ld e2) {
    ans[u] = e1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        dfs2(v, e2, (e1 + a[u]) * (f[u] / (1 - f[v])) + e2 * (1 - f[u] / (1 - f[v])));
    }
}

#define FIO

int main() {

    #ifdef FIO
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    #endif

    cin >> n;
    for(int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        addEdge(x, i);
    }
    for(int i = 1; i <= n; i++) cin >> p[i];
    for(int i = 1; i <= n; i++) cin >> a[i];

    dfs1(1);
    dfs2(1, 0, 0);

    for(int i = 1; i <= n; i++) ans[i] *= f[i];
    for(int i = 1; i <= n; i++) if(ans[i] > 0) sum += ans[i];

    printf("%.6Lf\n", sum);

    return 0;
}

二进制回文字符串（manacher）

给定一个长为 \(n\) 的仅有小写字母组成的字符串 \(s\)，有 \(q\) 次询问，每次询问给定 \(p,k\)，表示询问 \(s\) 的 \([p,p+2^k-1]\) 子串进行位逆序变换后是否和原来相同。

\(n,q\le 5\times 10^5\)

观察到似乎没有很直接的维护方法，因此考虑位逆序变换的性质。注意到我们可以将一个长度为 \(2^k\) 的序列分成两个长度为 \(2^{k-1}\) 的序列，分别进行位逆序变换，然后再交叉合并起来，形成原序列的位逆序变换。

那么这个性质有什么用呢？对于快速判断两个字符串是否相等的问题，考虑哈希。考虑求出一个区间位逆序变换之后的哈希值。注意到区间 \([l,r]\)（\(r=l+2^k-1\)）进行位逆序变换之后，在底数为 \(B\) 时的哈希值 \(\operatorname{hash}(l,r,B)\) 等于 \(B\times \operatorname{hash}(l,mid,B^2)+\operatorname{hash}(mid+1,r,B^2)\)。可证明如下表：

\(\operatorname{hash}(l,r,B)\)

\(i\) 0 1 2 \(\cdots\) \(n-4\) \(n-3\) \(n-2\) \(n-1\)
\(weight\) \(B^n-1\) \(B^n-2\) \(B^n-3\) \(\cdots\) \(B^3\) \(B^2\) \(B^1\) \(B^0\)
\(i\bmod 2\) 0 1 0 \(\cdots\) 0 1 0 1

\(\operatorname{hash}(l,mid,B^2)\)，其中\(B_0\) 表示区间内哈希的采用的底数，此处为 \(B^2\)；\(weight'\) 表示对应位置在大区间中的权重；

\(i\) \(0\) \(1\) \(2\) \(\cdots\) \(n'-4\) \(n'-3\) \(n'-2\) \(n'-1\)
\(weight\) \({B_0}^{n'-1}\) \({B_0}^{n'-2}\) \({B_0}^{n'-3}\) \(\cdots\) \({B_0}^3\) \({B_0}^2\) \({B_0}^1\) \({B_0}^0\)
\(weight'\) \(B^{2n'-1}\) \(B^{2n'-3}\) \(B^{2n'-5}\) \(\cdots\) \(B^7\) \(B^5\) \(B^3\) \(B^1\)

类似的：\(\operatorname{hash}(mid+1,r,B^2)\)

\(i\) \(0\) \(1\) \(2\) \(\cdots\) \(n'-4\) \(n'-3\) \(n'-2\) \(n'-1\)
\(weight\) \({B_0}^{n'-1}\) \({B_0}^{n'-2}\) \({B_0}^{n'-3}\) \(\cdots\) \({B_0}^3\) \({B_0}^2\) \({B_0}^1\) \({B_0}^0\)
\(weight'\) \(B^{2n'-2}\) \(B^{2n'-4}\) \(B^{2n'-6}\) \(\cdots\) \(B^6\) \(B^4\) \(B^2\) \(B^0\)

由于长度为 \(2\) 的整数次幂的区间一共有 \(O(n\log n)\) 个，因此我们可以维护每个区间在 \(B,B^2,B^4\cdots\) 下的哈希值，然后进行转移，即可得到一个 \(O(n\log^2n)\) 的做法。

进一步的，我们发现如果第 \(i+1\) 层（更短）的底数恰是第 \(i\) 层底数的平方，则每层一个位置的哈希值 \(\operatorname{hash}(l,r)\) 就等于 \(B\times \operatorname{hash}(l,mid)+\operatorname{hash}(mid+1,r)\)，每层只需记录 \(O(n)\) 个值，并且可以做到 \(O(1)\) 转移。时间复杂度 \(O(n\log n)\)。

哈希冲突分析

注意到每次查询只会用到两个特定的 \(\operatorname{hash}\)，而不是用一个集合存储所有的 \(\operatorname{hash}\)。因此每次查询碰撞的概率为 \(\frac 1P\)，模数使用 \(10^9+7\) 即可。

高级哈希

哈希不仅可以处理序列连续段问题，还可以处理一些具有良好算术性质的变换。

和平精英（peace）

给定一个序列，称它的一个区间是合法的当且仅当可以将区间中的数划分为两个非空可重集合 \(A,B\)，满足 \(\operatorname{or}\{A\}=\operatorname{and}\{B\}\)。有 \(q\) 次询问，每次询问给定区间 \([l,r]\)，问其是否是合法的。

\(n\le 10^5,\ 0\le a_i<2^30\)

考虑合法的区间有什么性质。设答案为 \(ans\)，那么 \(A\) 集合中所有数字的二进制位都包含 \(ans\) 的二进制位，并且 \(B\) 集合中所有数字的二进制位都包含于 \(ans\) 的二进制位。

这样，我们就有一种朴素的判定方法：枚举区间中的每一个数，求出小于它的数字的按位或，以及大于它的数字的按位与，然后再分讨这个数字（若存在）向 \(A,B\) 集合的分配方案。时间复杂度 \(O(nq)\)。

但我们又注意到，固定 \(ans\) 之后 \(A\) 集合中数字的 \(\operatorname{popcnt}\) 都不多于 \(\operatorname{popcnt}(ans)\)；\(B\) 集合中数字的 \(\operatorname{popcnt}\) 都不少于 \(\operatorname{popcnt}(ans)\)。因此我们可以从 \(\operatorname{popcnt}\) 的角度考虑。

具体的，我们枚举 \(\operatorname{popcnt}(ans)=i\)：

  • 若存在两种不同的数字都满足其 \(\operatorname{popcnt}=i\)，则无解，继续枚举；
  • 若存在恰好一种数字 \(x\) 满足 \(\operatorname{popcnt}(x)=i\)，则检查 \(\operatorname{popcnt}\in [0,i-1]\) 的按位或 \(pre\) 是否包含于 \(x\)，以及 \(\operatorname{popcnt}\in [i+1,30]\) 的按位与 $suf $是否包含 \(x\)，然后再分讨 \(x\) 出现的次数，若 \([pre\ne x]+[suf\ne x]\le cnt(x)\) 则有解，否则无解；
  • 若不存在数字 \(x\) 满足 \(\operatorname{popcnt}(x)=i\)，则判断 \(pre=suf\) 即可；

按位与和按位或可以体现集合的运算，因此值和值的 \(\operatorname{popcnt}\) 在运算前后都具有单调性。

代码 
  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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;

int n, q;
int a[N];

inline int cnt(int x) { return __builtin_popcount(x); }

namespace SegT {
    struct Node {
        int s1[31], s2[31];
        int sgv[31], sgc[31];
        inline Node() {
            memset(s1, 0, sizeof(s1)); 
            memset(s2, -1, sizeof(s2));
            memset(sgv, 0, sizeof(sgv));
            memset(sgc, 0, sizeof(sgc));
        }
        inline void set(int x) {
            int c = cnt(x);
            s1[c] = s2[c] = x;
            sgv[c] = x;
            sgc[c] = 1;
        }
        inline Node operator+(const Node &b) const {
            Node res;
            for(int i = 0; i <= 30; i++) res.s1[i] = s1[i] | b.s1[i];
            for(int i = 0; i <= 30; i++) res.s2[i] = s2[i] & b.s2[i];
            for(int i = 0; i <= 30; i++) {
                if(!~sgc[i] || !~b.sgc[i]) res.sgc[i] = -1;
                else if(sgc[i] && b.sgc[i] && sgv[i] != b.sgv[i]) res.sgc[i] = -1;
                else res.sgc[i] = sgc[i] + b.sgc[i], res.sgv[i] = sgv[i] | b.sgv[i];
            }
            return res;
        }
        inline Node &operator+=(const Node &b) {
            for(int i = 0; i <= 30; i++) s1[i] |= b.s1[i];
            for(int i = 0; i <= 30; i++) s2[i] &= b.s2[i];
            for(int i = 0; i <= 30; i++) {
                if(!~sgc[i] || !~b.sgc[i]) sgc[i] = -1;
                else if(sgc[i] && b.sgc[i] && sgv[i] != b.sgv[i]) sgc[i] = -1;
                else sgc[i] += b.sgc[i], sgv[i] |= b.sgv[i];
            }
            return *this;
        }
    } tr[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) {
        tr[p] = tr[lc(p)] + tr[rc(p)];
    }
    void build(int p, int l, int r) {
        if(l == r) {
            tr[p].set(a[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        push_up(p);
    }
    void query(int p, int l, int r, int ql, int qr, Node &res) {
        if(ql <= l && r <= qr) { res += tr[p]; return; }
        int mid = (l + r) >> 1;
        if(ql <= mid) query(lc(p), l, mid, ql, qr, res);
        if(mid < qr) query(rc(p), mid + 1, r, ql, qr, res);
    }
}

// #define FIO

int main() {

    #ifdef FIO
    freopen("peace.in", "r", stdin);
    freopen("peace.out", "w", stdout);
    #endif

    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];

    SegT::build(1, 1, n);

    while(q--) {
        int l, r;
        cin >> l >> r;
        SegT::Node res;
        SegT::query(1, 1, n, l, r, res);
        static int pre[N], suf[N];
        pre[0] = res.s1[0];
        suf[30] = res.s2[30];
        for(int i = 1; i <= 30; i++) pre[i] = pre[i - 1] | res.s1[i];
        for(int i = 29; i >= 0; i--) suf[i] = suf[i + 1] & res.s2[i];
        if(res.sgc[0] > 0) {
            if(suf[1] == 0 || res.sgc[0] >= 2) { cout << "YES\n"; continue; }
        }
        if(res.sgc[30] > 0) {
            if(pre[29] == (1 << 30) - 1 || res.sgc[30] >= 2) { cout << "YES\n"; continue; }
        }
        bool flag = false;
        for(int i = 1; i <= 29; i++) {
            if(res.sgc[i] < 0) continue;
            if(res.sgc[i] == 0) {
                if(pre[i - 1] && ~suf[i + 1] && pre[i - 1] == suf[i + 1]) { flag = true; break; }
                continue;
            }
            int t = res.sgv[i];
            if((pre[i - 1] | t) != t) continue;
            if((suf[i + 1] & t) != t) continue;
            if((int)(pre[i - 1] != t) + (int)(suf[i + 1] != t) <= res.sgc[i]) { flag = true; break; }
        }
        cout << (flag ? "YES\n" : "NO\n");
    }

    return 0;
}