茶6.17-6.21

Mon

Good Array_521C

输入 n(2≤n≤2e5) 和长为 n 的数组 a(1≤a[i]≤1e6)。

对于数组 b，如果 b 中存在一个数 x，使得 x = b 中其余元素之和，则称 b 为「好数组」。

如果删除 a[i] 可以使剩余元素组成好数组，则称 i 为「好下标」。
输出 a 的好下标的个数，以及所有好下标（任意顺序）。注意下标从 1 开始。

输入
5
2 5 1 2 2
输出
3
4 1 5

输入
4
8 3 5 2
输出
2
1 4

输入
5
2 1 2 4 3
输出
0

Sol:

记录最大值，如果删除的不是最大值，检查总和是否是最大值的两倍即可。如果删除的是最大值，则看删除后的总和是否是第二大值的两倍。

Code：

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    ll sum = 0;
    int ma = 0;
    FOR(i, 0, n - 1) {
        cin >> a[i];
        sum += a[i];
        ma = max(ma,a[i]);
    }
    vi b = a;
    sort(b);
    vi ans;
    for(int i = 0; i < n; i++) {
        if(a[i]!=ma) {
            if(ma*2==(sum-a[i])){
                ans.pb(i+1);
            }
        } else if(a[i]==ma) {
            if(b[n-2]*2==(sum-a[i])) {
                ans.pb(i+1);
            }
        }
    }
    cout << ans.size() << endl;
    for(auto num:ans) {
        cout << num << " ";
    }
    cout << '\n';
}

Tue

Nested Segments_43C

输入 n(1≤n≤3e5) 和 n 个闭区间，区间的左右端点在 [1,1e9] 内。

从这 n 个区间中，选出两个区间 [L[i], R[i]] 和 [L[j], R[j]]，
满足 i ≠ j 且 L[j] <= L[i] <= R[i] <= R[j]，也就是区间 j 包含区间 i。

输出 i 和 j（按照输入的顺序，下标从 1 开始）。
如果不存在这样的区间，输出两个 -1。

输入
5
1 10
2 9
3 9
2 3
2 9
输出
2 1

输入
3
1 5
2 6
6 20
输出
-1 -1

Sol:

把区间按照左端点从小到大排序，左端点相同的，按照右端点从大到小排序。

排序后，遍历区间。 对于区间 i，如果区间 i 被区间 j 包含，那么区间 j 一定是我们之前遍历过的区间（因为左端点从小到大排序了）。

所以只要区间 j 的右端点 >= 区间 i 的右端点，那么区间 j 就可以包含区间 i。

那么维护遍历过的区间的右端点的最大值 mxR 即可。

这也说明为什么左端点相同时，要按照右端点从大到小排序。如果有左端点相同的情况，如此排序可以保证先把 mxR 更新成大的，然后遇到右端点小的，找到答案。

Code:

void solve()
{
    ll n;
    cin >> n;
    vector<pair<pii, int> > a(n);
    FOR(i, 0, n - 1) {
        cin >> a[i].F.F >> a[i].F.second;
        a[i].S = i;
    }
    sort(a.begin(), a.end(), [](const pair<pii, int>& x, const pair<pii, int>& y) {
        return x.F.F < y.F.F || (x.F.F == y.F.F && x.F.S > y.F.S);
    });
    ll mxR = 0, mxI = 0;
    for (auto p : a) {
        if (p.F.S <= mxR) {
            cout << p.S + 1 << " " << mxI + 1 << endl;
            return;
        }
        if (p.F.S > mxR) {
            mxR = p.F.S;
            mxI = p.S;
        }
    }
    cout << -1 << " " << -1 << endl;
}

Wed

0, 1, 2, Tree!_937F

输入 T(≤1e4) 表示 T 组数据。所有数据的 a+b+c 之和 ≤3e5。
每组数据输入 a,b,c (0≤a,b,c≤1e5 且 1≤a+b+c)。

有一棵二叉树，其中 a 个节点有两个儿子，b 个节点有一个儿子，c 个节点没有儿子。
输出这棵二叉树的最小高度。
注意这里的高度是根到最远叶节点的路径上的边的个数。
特别地，只有一个节点的二叉树的高度为 0。

进阶：做到 O(1) 时间。

输入
10
2 1 3
0 0 1
0 1 1
1 0 2
1 1 3
3 1 4
8 17 9
24 36 48
1 0 0
0 3 1
输出
2
0
1
1
-1
3
6
-1
-1
3

Sol:

把这三种节点（有两个/一个/零个儿子）分别记作 A B C。

整体思路： 一层一层地放置，先放 A，然后 B，最后 C。

先判断 -1。 由于 a 个节点 A 会产生 a+1 个「插座」，可以插入恰好 a+1 个节点，所以必须满足 a+1=c。

B 节点由于插入插座后自己又产生了一个插座，所以无需判断 b。

对于节点 A 来说，一层一层地放置，可以放 a 的二进制长度层，设其为 h1。 最后一层还留有 k = 2^h1 - 1 - a 个「插座」，可以放一部分节点 B。

如果 b-k > 0，那么剩下的 b-k 个节点需要 h2 = ceil((b-k)/(a+1)) 层。

最后一层放节点 C。

所以树高为 h1 + h2 + 1 - 1 = h1 + h2，减一是因为按照题目规定，高度等于层数减一。

Code：

void solve()
{
    int a,b,c;
    cin >> a >> b >> c;
    if (a+1 != c) {
        cout << -1 << endl;
        return;
    }
    int h = a == 0? 0 : log2(a) + 1;
    b -= (1<<h) - c;
    if (b > 0) {
        h += (b-1)/c + 1;
    }
    cout << h << endl;
}

Thu

Vlad and Trouble at MIT_928G

输入 T(≤1e3) 表示 T 组数据。所有数据的 n 之和 ≤1e5。
每组数据输入 n(2≤n≤1e5) 和 n-1 个数 a2,a3,…,an (1≤ai<i)，表示节点 i 和节点 ai 之间有一条无向边。
这 n-1 条无向边形成了一棵树，节点编号从 1 到 n。
然后输入长为 n 的字符串 s，只包含字母 P S C，表示节点 i 的类型是 s[i]。

最少要切断多少条边，使得类型为 P 的节点都无法到达任意类型为 S 的节点？

输入
3
3
1 1
CSP
4
1 2 2
PCSS
4
1 2 2
PPSS
输出
1
1
2

Sol：

首先简单分析一下性质：

如果树上至少有一个非 C 节点，那么对于类型为 C 的节点，它要么和 S 连通，要么和 P 连通（不能都连通）。

对于其他类型的节点也是一样的，S 只能和 S 连通，不能和 P 连通；P 只能和 P 连通，不能和 S 连通。

定义 f[x] [0] 表示节点 x 和 S 连通（相当于和 P 不连通）最少需要切断的边。如果 s[x]=P，则 f[x] [0] = inf。

定义 f[x] [1] 表示节点 x 和 P 连通（相当于和 S 不连通）最少需要切断的边。如果 s[x]=S，则 f[x] [1] = inf。

假设 1 是树的根。从 1 开始 DFS，跑一个树形 DP。

遍历 x 的儿子 y，如果 x 要和 S 连通，那么分类讨论：

如果 y 也和 S 连通，则 f[x] [0] += f[y] [0]。

如果 y 和 P 连通，则 f[x] [0] += f[y] [1] + 1，因为需要断开 x 和 y 之间的边。

二者取最小值，得

f[x] [0] += min(f[y] [0], f[y] [1] + 1)。

同理得

f[x] [1] += min(f[y] [1], f[y] [0] + 1)。

代码实现时，无需建树，直接从 i=n 开始倒着遍历，转移到其父节点 a[i] 上。

答案为 min(f[1] [0], f[1] [1])。

如果假设 1 的父节点是 0，答案也可以是 min(f[0] [0], f[0] [1])。

void solve()
{
    int n;
    string s;
    cin >> n;
    vi a(n+1);
    for(int i = 2; i <= n; i++) {
        cin >> a[i];
    }
    cin >> s;
    vector<vector<int> > f(n+1,vector<int>(2));
    for (int i = n; i > 0; i--) {
        vector<int> g = f[i];
        if (s[i-1] != 'C') {
            g[s[i-1]&1] = 1e9;
        }
        f[a[i]][0] += min(g[0],g[1]+1);
        f[a[i]][1] += min(g[0]+1,g[1]);
    }
    cout << min(f[0][0], f[0][1]) << endl;
}

Fri

Mercenaries_94G

输入 n(1≤n≤3e5) 和 m(0≤m≤min(20,n*(n-1)/2))。
解释：有 n 个雇佣兵，从中选择一些人（至少一个人），组成一支部队。m 的含义见下。

然后输入 n 个闭区间的左右端点 [Li,Ri]，范围 [1,n]。
解释：如果选了第 i 位雇佣兵，那么部队的大小必须在闭区间 [Li,Ri] 中。

最后输入 m 对数字 (ai, bi)，满足 1≤ai<bi≤n。
解释：这 m 对雇佣兵相互憎恨，如果选了第 ai 位雇佣兵，那么不能选第 bi 位雇佣兵，反之亦然。

输出有多少种选法，模 998244353。

输入
3 0
1 1
2 3
1 3
输出 3

输入
3 1
1 1
2 3
1 3
2 3
输出 2

Sol:

如果 m=0，要怎么做？

枚举部队人数 i=1,2,…,n，对于固定的 i，有多少种选法？

我们需要知道有多少个闭区间包含 i。

对于每个区间 [L,R]，把 [L,R] 内的数都加一。这可以用差分数组解决。

计算差分数组的前缀和，得到 cnt 数组，也就是有 cnt[i] 个区间包含 i，那么选法就是 C(cnt[i],i)。

所以 m=0 的时候，一共有

∑C(cnt[i],i)

种选法，其中 i=1,2,…,n。

回到原问题。

考虑容斥。

从不考虑 m 对约束的方案数中，减去不合法的方案数（选了 m 对约束中的）。

这可以用子集容斥计算。

枚举 m 对约束的子集，假设子集中有 j 个人，相当于这 j 个人一定要选，那么选法就是

∑C(cnt[i]-j,i-j)

其中 i=p,p+1,…,q，其中 p 和 q 是这 j 个人对应区间的交集的左右端点。

如何高效地计算上述和式？

由于 m 至多 20，所以 j 至多 40。

对 0~40 这 41 个不同的 j，计算 C(cnt[i]-j,i-j) 的前缀和。

组合数可以通过预处理阶乘及其逆元快速计算。

记得取模：组合数取模，前缀和取模，最后返回的答案要保证是非负数（因为容斥里面有负数）。

Code(抄自jls）:

#include <bits/stdc++.h>
constexpr int P = 998244353;
int power(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % P)
        if (b & 1)
            res = 1ll * res * a % P;
    return res;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> add(n + 1), del(n + 1);
    for (int i = 0; i < n; ++i) {
        int l, r;
        std::cin >> l >> r;
        add[l].push_back(i);
        del[r].push_back(i);
    }
    std::vector<int> a(m), b(m);
    std::vector<int> id(n, -1);
    int cnt = 0;
    for (int i = 0; i < m; ++i) {
        std::cin >> a[i] >> b[i];
        --a[i];
        --b[i];
        if (id[a[i]] == -1)
            id[a[i]] = cnt++;
        if (id[b[i]] == -1)
            id[b[i]] = cnt++;
    }
    std::vector<int> fac(n + 1), invFac(n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; ++i)
        fac[i] = 1ll * fac[i - 1] * i % P;
    invFac[n] = power(fac[n], P - 2);
    for (int i = n; i; --i)
        invFac[i - 1] = 1ll * invFac[i] * i % P;
    std::vector<int> ways(m + 1);
    std::vector<int> in(n);
    int64_t mask = 0;
    ways[0] = 1;
    int tot = 0, tp = 0;
    int ans = 0;
    auto C = [&](int n, int m) {
        if (n < m || m < 0)
            return 0;
        return (int)(1ll * fac[n] * invFac[m] % P * invFac[n - m] % P);
    };
    for (int i = 1; i <= n; ++i) {
        for (auto x : add[i]) {
            in[x] = 1;
            ++(id[x] == -1 ? tot : tp);
        }
        int64_t nMask = 0;
        for (int j = 0; j < m; ++j) {
            if (in[a[j]])
                nMask |= 1ll << id[a[j]];
            if (in[b[j]])
                nMask |= 1ll << id[b[j]];
        }
        if (nMask != mask) {
            mask = nMask;
            std::fill(ways.begin(), ways.end(), 0);
            std::function<void(int, int64_t, int)> dfs = [&](int x, int64_t s, int coef) {
                if (x == m) {
                    int p = __builtin_popcountll(s);
                    for (int j = 0; j <= m; ++j)
                        ways[j] = (ways[j] + 1ll * coef * C(tp - p, j - p)) % P;
                    return;
                }
                if (in[a[x]] && in[b[x]])
                    dfs(x + 1, s | 1ll << id[a[x]] | 1ll << id[b[x]], P - coef);
                dfs(x + 1, s, coef);
            };
            dfs(0, 0, 1);
        }
        for (int j = 0; j <= m; ++j)
            ans = (ans + 1ll * ways[j] * C(tot, i - j)) % P;
        for (auto x : del[i]) {
            in[x] = 0;
            --(id[x] == -1 ? tot : tp);
        }
    }
    std::cout << ans << "\n";
    return 0;
}