图片.png

暴力进前五 /cy

选数

m 个正整数 a_i，两个人博弈。

Arisu 选一个数 x \in [0, 2^n)，并依次将 x \oplus a_i。

Bob 会在某个时刻，将 x 循环左移一位。

Arisu 想要最大化最后的 x，Bob 想最小化。

求最后的 x。

n \leq 30，m \leq 10^5。

记 pre_i 是前缀异或和，suf_i 是后缀疑惑和，如果在第 i 位 Bob 进行操作，那么值就是：

f(x \oplus pre_i) \oplus suf_{i + 1}

（f 是循环左移）

发现 f 是线性的，所以上式就是：

f(x) \oplus f(pre_i) \oplus suf_{i + 1}

问题变成了有若干个数，选一个数使得该数异或上这些数都某一个数的最小值最大。

把所有的 f(pre_i) \oplus suf_{i + 1} 扔到 trie 里头 dp 就行。

typedef pair<int, int> pii;

const int MAXN = 1e5 + 10, MAXLOG = 30;

int n, m, arr[MAXN], pre[MAXN], suf[MAXN], ans1 = -1, ans2;

int get(int x) {
    return ((x >> (n - 1)) | (x << 1)) & ((1ll << (n)) - 1);
}

#define get_bit(S, i) ((S >> i) & 1)
struct Trie {
    int node_cnt;
    struct Node { int ch[2], is_leaf, f, cnt; } t[MAXN << 4];
    void ins(int num) {
        int cur = 0;
        per(idx, 30, 0) {
            int val = get_bit(num, idx);
            if (!t[cur].ch[val]) t[cur].ch[val] = ++node_cnt;
            cur = t[cur].ch[val];
        }
        t[cur].is_leaf = true;
    }
    void dfs(int cur, int idx) {
        if (idx == 0) return t[cur].cnt = 1, void();
        if (t[cur].ch[0]) dfs(t[cur].ch[0], idx - 1);
        if (t[cur].ch[1]) dfs(t[cur].ch[1], idx - 1);
        if (!t[cur].ch[0] || !t[cur].ch[1]) {
            t[cur].f = t[t[cur].ch[0]].f + t[t[cur].ch[1]].f + ((idx < n) ? (1 << (idx - 1)) : 0);
            t[cur].cnt = t[t[cur].ch[1]].cnt + t[t[cur].ch[0]].cnt;
        } else {
            t[cur].f = max(t[t[cur].ch[0]].f, t[t[cur].ch[1]].f);
            t[cur].cnt = (t[t[cur].ch[0]].f == t[cur].f) * t[t[cur].ch[0]].cnt + (t[t[cur].ch[1]].f == t[cur].f) * t[t[cur].ch[1]].cnt;
        }
    }
} trie;

int main() {
    IO::read(n), IO::read(m);
    rep(i, 1, m) IO::read(arr[i]), pre[i] = pre[i - 1] ^ arr[i];
    per(i, m, 1) suf[i] = suf[i + 1] ^ arr[i];
    rep(i, 0, m) trie.ins(get(pre[i]) ^ suf[i + 1]);
    trie.dfs(0, 31);
    printf("%d\n%d\n", trie.t[0].f, trie.t[0].cnt);
    return 0;
}

模板

一棵树，每个节点有一个容量上限。每次操作 (x, c) 表示将 x 到根的路径上的所有点里放入一个颜色为 c 的球。如果该点放入的球的数量已经达到了该点的容量上限，则该次操作对该点没有影响。

最后询问每个点里面有多少种颜色的点。

n \leq 10^5, m \leq 10^5。

本题的大题思路非常明确：处理出每个点被装满的时刻，然后依次进行操作，并将该时刻对应装满的点答案求出来。点-根路径加颜色，求点颜色个数非常经典，set 和 BIT 就行。

问题是如何求出被装满的时刻。

这道题毒瘤之处在于，是父亲继承所有儿子，而不是儿子继承父亲。所以普通的可持久化线段树继承父亲在这里并不适用。

自然的，想到 dsu on tree。线段树该节点子树内第 i 个节点维护时刻 i 的操作个数。先处理出轻儿子，然后清空，然后处理重儿子，并合并轻儿子。

时间复杂度 O(n \log^2 n)。

更好的做法是，我们完全可以用可持久化线段树处理出每个时刻上的前缀区间的操作情况（同上面一样），并且查询的时候我们只关注该点的子树内的那个区间就行。这样区间求第 k 大是 O(n \log n) 的。好写很多。

typedef pair<int, int> pii;

const int MAXN = 1e5 + 10;

int n, m, q;

int head[MAXN], ecnt;
struct Edge { int nxt, to; } e[MAXN << 1];
void add(int u, int v) { e[++ecnt].nxt = head[u], e[ecnt].to = v, head[u] = ecnt; }

int dtp[MAXN], tim[MAXN];
struct Vertix { int dfn, sz, son, top, dep, fa; } vtx[MAXN];

int dfsclock;
void dfs(int u, int fr) {
    vtx[u].sz = 1, dtp[ vtx[u].dfn = ++dfsclock ] = u, vtx[u].dep = vtx[ vtx[u].fa = fr ].dep + 1;
    for (int _ = head[u], v; _; _ = e[_].nxt) {
        v = e[_].to;
        if (v == fr) continue;
        dfs(v, u);
        if (vtx[vtx[u].son].sz < vtx[v].sz) vtx[u].son = v;
        vtx[u].sz += vtx[v].sz;
    }
}
void getTop(int u, int top) {
    vtx[u].top = top;
    if (vtx[u].son) getTop(vtx[u].son, top);
    for (int _ = head[u], v; _; _ = e[_].nxt) {
        v = e[_].to;
        if (v == vtx[u].fa || v == vtx[u].son) continue;
        getTop(v, v);
    }
}
int LCA(int u, int v) {
    while (vtx[u].top != vtx[v].top) {
        if (vtx[vtx[u].top].dep < vtx[vtx[v].top].dep) swap(u, v);
        u = vtx[vtx[u].top].fa;
    }
    return vtx[u].dep < vtx[v].dep ? u : v;
}

struct PersistentSegmentTree {
    #define mid ((l + r) >> 1)
    #define qls t[cur].ls, l, mid
    #define qrs t[cur].rs, mid + 1, r
    int node_cnt, rt[MAXN];
    int& operator [](const int& x) { return rt[x]; }
    struct Node { int ls, rs, dat; } t[MAXN * 20];
    void ins(int pre, int& cur, int l, int r, int pos, int val) {
        cur = ++node_cnt;
        t[cur] = t[pre], t[cur].dat += val;
        if (l == r) return ;
        if (pos <= mid) ins(t[pre].ls, qls, pos, val);
        else ins(t[pre].rs, qrs, pos, val);
    }
    int query(int pre, int cur, int l, int r, int k) {
        if (l == r) return k > 1 ? m : l;
        int cnt = t[t[cur].ls].dat - t[t[pre].ls].dat;
        if (cnt < k) return query(t[pre].rs, qrs, k - (t[t[cur].ls].dat - t[t[pre].ls].dat));
        else return query(t[pre].ls, qls, k);
    }
} sgt;

struct BIT {
    int bit[MAXN];
    void add(int x, int val) { for (; x < MAXN; x += x & -x) bit[x] += val; }
    int query(int x) { if (!x) return 0; int ret = 0; for (; x; x -= x & -x) ret += bit[x]; return ret; }
} bit;

int ans[MAXN], table[MAXN], R[MAXN];
pii opt_arr[MAXN];

int r_num[MAXN], k[MAXN];
vector<int> opt[MAXN];
vector<int> tim_vtx[MAXN];
set<int> col_dfn[MAXN];

int main() {
    IO::read(n);
    rep(i, 1, n - 1) {
        int u, v; IO::read(u), IO::read(v);
        add(u, v), add(v, u);
    }
    dfs(1, 0), getTop(1, 1);
    rep(i, 1, n) IO::read(k[i]);
    IO::read(m);
    rep(i, 1, m) {
        int x, c; IO::read(x), IO::read(c), table[i] = c;
        opt_arr[i] = make_pair(x, c);
        opt[vtx[x].dfn].push_back(i);
    }
    rep(i, 1, n) {
        R[i] = R[i - 1];
        for (auto cur_opt : opt[i]) {
            ++R[i];
            sgt.ins(sgt[R[i] - 1], sgt[R[i]], 0, m, cur_opt, 1);
        }
    }
    rep(i, 1, n) {
        tim[i] = sgt.query(sgt[R[vtx[i].dfn - 1]], sgt[R[vtx[i].dfn + vtx[i].sz - 1]], 0, m, k[i]);
        tim_vtx[tim[i]].push_back(i);
    }
    sort(table + 1, table + m + 1); int tablesize = unique(table + 1, table + m + 1) - table - 1;
    rep(i, 1, m) {
        int cur_col = lower_bound(table + 1, table + tablesize + 1, opt_arr[i].second) - table, cur_u = opt_arr[i].first;
        if (!col_dfn[cur_col].count(vtx[cur_u].dfn)) {
            col_dfn[cur_col].insert(vtx[cur_u].dfn); int pre_node = 0, nxt_node = 0;
            auto p = col_dfn[cur_col].find(vtx[cur_u].dfn);
            if (p != col_dfn[cur_col].begin()) pre_node = *(--p), ++p;
            ++p;
            if (p != col_dfn[cur_col].end()) nxt_node = *p;
            bit.add(vtx[cur_u].dfn, 1);
            if (pre_node) bit.add(vtx[LCA(dtp[pre_node], cur_u)].dfn, -1);
            if (nxt_node) bit.add(vtx[LCA(dtp[nxt_node], cur_u)].dfn, -1);
            if (pre_node && nxt_node) bit.add(vtx[LCA(dtp[pre_node], dtp[nxt_node])].dfn, 1);
        }
        for (auto cur : tim_vtx[i]) {
            ans[cur] = bit.query(vtx[cur].dfn + vtx[cur].sz - 1) - bit.query(vtx[cur].dfn - 1);
        }
    }
    IO::read(q);
    rep(i, 1, q) {
        int x; IO::read(x);
        printf("%d\n", ans[x]);
    }
    return 0;
}

总结

这场全是暴力，进了前五。暴力都是用了一些普及组的数据结构之类的。

原来只要没挂分分数就会很高。

11-2 赛后题解与复盘
上一篇 «
10-26 赛后题解
» 下一篇