久违地冲了一局。。。无悬念的差点爆 0 了。

Problem A. Copil Copac Draws Trees

题意：给定一个树，和边，初始根节点是点亮的，每回合你可以按照边地顺序扫一遍所有边，如果其中一个点是点亮的，那么点亮另一个点。问多少回合后所有点被点亮。

分析：显然不考虑边顺序的话，就是求树的深度，这个过程也可以看作树 dp。。
dp[i] 存两个值，分别表示最少被点亮所需的回合数，和被点亮时所用边的编号。转移的时候讨论一下编号即可。

Problem C. Hyperregular Bracket Strings

题意：问有多少长度 n 的合法括号序列，满足给定的所有区间也时合法的括号序列。

分析：个人感觉非常棒的题目。首先不考虑区间的话就是卡塔兰数 {C_i}。

然后考察 [1,4] [2,3] 和 [1,3] [2,4] 两种情况，前者比较容易分析，[2,3] 现在一定是一个独立的合法括号序列，[1]-[4] 然后两个位置虽然不连续，但是也构成一个独立的合法括号序列。而后者 [2,3] 则要求 [1] [2,3] [4] 分别是三组独立的卡塔兰序列，因为中间重合的部分对前缀和的 delta 一定是 0（反证法）。

这样看的话最后结果一定是若干 {C_i} 相乘，难点就是分解出这些独立的区间的测度，看起来结构简单，写起来却并不容易，我们无法像表达式解析那样简单的递归或者用一个栈，考虑到还有区间共享端点的情况就更麻烦了。

然后有一个非常巧妙地思路。。。给每个区间随机分配一个 uint 数，然后把前缀和改成 xor 前缀和，然后用 hash[] 记录每种区间集合影响下的测度数，就能轻易处理不连续的状态，并区分上面说到的嵌套和重叠两种情况了。

这种 hash 的思想非常实用，比如去年 FHQ R2 的 A 题 也出现过类似的思路。

具体说来就是开三个东西：

map<int, uint64_t> H; // 记录每个区间的随机 hash 映射
map<uint64_t, int> cnt; // 记录每个区间交的格子数
uint64_t S[N]; // 记录前缀和对应的区间交

如果区间稀疏的话，还需要对前缀和离散化。

#include <lastweapon/poly>
#include <bits/stdc++.h>
using namespace lastweapon;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<uint64_t> rnd(0, ULLONG_MAX);

const int N = int(3e5) + 9;
Mint C[N]; uint64_t S[N];
int n, k;

Mint binom(int n, int m) {
    return fac[n] * invFac[m] * invFac[n-m];
}

map<int, uint64_t> H;
map<uint64_t, int> cnt;
uint64_t h(int x) {
    if (!CTN(H, x)) H[x] = rnd(gen);
    return H[x];
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    FOR(i, 1, N/2) C[i*2] = binom(2*i,  i) - binom(2*i, i+1);

    Rush {
        RD(n, k);

        H.clear(), cnt.clear(); fill(S+1, S+n+1, 0);

        REP(i, k) {
            int a, b; RD(a, b);
            S[a] ^= h(i); S[b+1] ^= h(i);
        }

        REP_1(i, n) ++cnt[S[i] ^= S[i-1]];
        Mint z = 1; for (auto it: cnt) z *= C[it.se];

        cout << z << endl;
    }
}

Posted by xiaodao
Category: 日常