CF Round 1000 部分题解

OyamaMahiro

2025-01-23 11:51:56

发布于：山东

25阅读

0回复

0点赞

A

Solution

特判 $l=r=1$ 的情况输出 $1$ ，其余情况答案均为 $r-l+1$ 。

B

Solution

考虑翻转一个子序列对 $[l,r]$ 的和的贡献。很明显，若翻转的这个子序列，其左右端点分别在 $l$ 左侧， $r$ 右侧，则左右端点对 $[l,r]$ 区间都不会有贡献。因此只有两种情况：

$[1,l-1]$ 的一些数和 $[l,r]$ 的一些数做了交换
$[r+1,n]$ 的一些数和 $[l,r]$ 的一些数做了交换

很明显肯定每一次是拿 $[l,r]$ 区间中最大的换对面区间最小的，因此直接模拟即可，时间复杂度为 $O(n\log n)$ 瓶颈在排序。

Another Problem：如果翻转的是一个连续的子序列，那么应该怎么做？

C

Solution

考虑删除一个点 $u$ 对树连通块的贡献。

若删除该点之后树为空，则连通块数量为 $0$ 。
否则，删除该点后连通块数量会增加 $\deg u-1$ 。其中 $\deg u$ 表示 $u$ 点当前在树上的度数。

因此考虑枚举第一个点删除的是哪里，然后直接计算出第二个点删除哪里最优。具体的说，枚举删除第一个点 $u$ 之后， $u$ 点的 $\deg$ 会清零，而对于所有的 $v$ 满足 $T$ 中存在 <u,v> 一条边， $v$ 点的 $\deg$ 都会减 $1$ 。此时很显然只需要取 $\deg$ 最大的点即可。显然可以用线段树搞，时间复杂度为 $O(n\log n)$ 。

D

Solution

首先考虑若某一行上有 $a,b,c,d$ 四个点（ $a<b<c<d$ ），而另一行上至少有两个点。现在我们需要恰好选两个三角形把 $a,b,c,d$ 选完，则：

若两组分别选择 $a,b$ 和 $c,d$ ，则对答案的贡献为 $b+d-a-c$
若两组分别选择 $a,c$ 和 $b,d$ ，则对答案的贡献为 $c+d-a-b$
若两组分别选择 $a,d$ 和 $b,c$ ，则对答案的贡献为 $c+d-a-b$

其中二、三两种选择方法的值比第一种优秀。因为第三种最好处理所以全部选择第三种取法。

因此我们处理出两个序列 $c,d$ 分别表示 $a,b$ 两个序列按照上述左右选的贪心方法能够得到的贡献。显然此时 $c,d$ 两个序列均严格单调递减。而若此时选择 $i$ 个数，则必然在 $c$ 序列中选 $k$ 个数， $d$ 序列上选 $i-k$ 个数。显然肯定从前往后选答案最大。因此贡献即为 $\sum\limits_{j=1}^k c_i+\sum\limits_{j=1}^{i-k}d_i$ 。容易观察到这个东西随 $k$ 的变化是单峰的，因此使用二分或者三分都可以通过这个题，时间复杂度为 $O(n\log n)$ 。

E

Solution

可以简单证明 $f(i,j)=2\min(\text{dist(u,lca),dist(v,lca)})-1$ ，但是这个式子直接算最多只能做到 $O(n^2)$ ，因此考虑拆分之。

$\begin{aligned} f(i,j)&=2\min(\text{dist}(u,\text{lca}),\text{dist}(v,\text{lca}))-1\\ &=2\min(\text{dep}_u-\text{dep}_\text{lca},\text{dep}_v-\text{dep}_\text{lca})-1\\ &=2\min(\text{dep}_u,\text{dep}_v)-2\text{dep}_\text{lca}-1\\ \end{aligned}$

这样看起来舒服多了！答案即为

$\begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=i+1}^nf(i,j)&=\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[\text{(i, j) is good}](2\min(\text{dep}_u,\text{dep}_v)-2\text{dep}_\text{lca}-1)\\ &=2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[\text{(i, j) is good}](\min(\text{dep}_u,\text{dep}_v)-\text{dep}_\text{lca})-\frac{n(n-1)}{2}\\ &=2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\min(\text{dep}_i,\text{dep}_j)-2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\text{dep}_\text{lca(i, j)}-\frac{n(n-1)}{2}+\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[\text{(i, j) is not good}]\\ \end{aligned}$

此时等式被分为了四个互相独立的部分，考虑分开求解：

$2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\min(\text{dep}_i,\text{dep}_j)$ ：考虑对 $\text{dep}$ 数组从小到大排序，此时 $\forall i,j\in[1,n],i<j,\text{dep}_i\le\text{dep}_j$ 。答案即为 $2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\text{dep}_i=2\sum\limits_{i=1}^n\text{dep}_i\sum\limits_{j=i+1}^n1=2\sum\limits_{i=1}^n\text{dep}_i(n-i)$ 。
$2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\text{dep}_\text{lca(i, j)}=2\sum\limits_{\text{lca}=1}^n\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[\text{lca(i, j)}=\text{lca}]\text{dep}_{\text{lca}}=2\sum\limits_{\text{lca}=1}^n\text{dep}_\text{lca}\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[\text{lca}(i, j)=\text{lca}]$ 。问题变为计数对于每一个 $\text{lca}$ ，有多少对 $(i,j)$ 使得 $\text{lca}(i,j)=\text{lca}$ 。考虑树上 dp 得到 $\text{siz}_i$ 表示以 $1$ 结点为根， $i$ 点子树的大小是多少。那么显然只有子树内选点才能使得其 $\text{lca}$ 为 $i$ ，答案为 $\dfrac{\text{siz}_i(\text{siz}_i-1)}{2}$ 。但是这个可能会多统计答案。因此对于 $i$ 的每一个儿子结点 $j$ ，都需要容斥掉 $j$ 子树内选两点的答案 $\dfrac{\text{siz}_j(\text{siz}_j-1)}{2}$ 。因为树上所有点的儿子结点的数量是 $O(n)$ 级别的，因此该部分时间复杂度也为 $O(n)$ 。
$\dfrac{n(n-1)}{2}$ ，这个直接算就行了。
$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[\text{(i, j) is not good}]$ 。因为 $(i,j)$ 是 $\text{not good}$ 的，当且仅当 $i$ 是 $j$ 的祖先或 $j$ 是 $i$ 的祖先。因此考虑让 $i,j$ 无序，此时只需要计数 $i$ 是 $j$ 祖先的方案数即可。显然 $i$ 是 $j$ 祖先的时候， $j$ 只能在 $i$ 的子树内取，有 $\text{siz}_j$ 种方案。因此答案即为 $\sum\limits_{i=1}^n\text{siz}_i$ 。

于是这个问题就解决了，时间复杂度为 $O(n\log n)$ ，瓶颈在于第一步的对 $\text{dep}$ 从小到大排序。

Code

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500010;
const int mod = 998244353;
vector<int> adj[N];
int dep[N], up[N], siz[N];
void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    up[u] = fa;
    siz[u] = 1;
    for (int &v : adj[u])
        if (v != fa) dfs(v, u), siz[u] += siz[v];
}
signed main() {
    cin.tie(0)->sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) adj[i].clear();
        for (int i = 1; i < n; ++i) {
            int x, y;
            cin >> x >> y;
            adj[x].emplace_back(y);
            adj[y].emplace_back(x);
        }
        dfs(1, 0);
        int sum = 0;
        sort(dep + 1, dep + n + 1);
        for (int i = 1; i <= n; ++i) sum += dep[i] * (n - i) * 2;
        dfs(1, 0);
        for (int d = 1; d <= n; ++d) {
            vector<int> cha;
            for (int &j : adj[d])
                if (j != up[d]) cha.emplace_back(siz[j]);
            sum -= siz[d] * (siz[d] - 1) * dep[d];
            for (int &j : cha) sum += j * (j - 1) * dep[d];
        }
        sum -= n * (n - 1) / 2;
        for (int i = 1; i <= n; ++i) sum += siz[i] - 1;
        cout << sum << '\n';
    }
    return 0;
}

F1

Solution

首先考虑每一个位置任意选择左括号 / 右括号，答案是多少。显然一个长度为 $2n$ 的序列而言，不同的合法序列数为 $\text{Catalan}(n)$ 即卡特兰数第 $n$ 项，答案为 $\binom{2n}{n}/(n+1)$ 。问题是目前确定一些位置为左括号，一些位置为右括号，方案数是多少。此时可以把序列分为若干段。这个地方画图解释：

其中相同颜色的部分为一组，一组之内可以任意匹配括号，但是需要保证每一组的所有括号单独拿出来还是匹配的。

因此可以用栈线性模拟出每一个不同颜色块的长度，然后对每一段单独计算卡特兰数，使用乘法原理将其相乘。因为组合数 / 逆元都可以在 $O(n)-O(1)$ 时间复杂度内预处理 / 求解，所以总时间复杂度为 $O(n^2)$ ，可以通过。

Code

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500010;
const int mod = 998244353;
int l[N], r[N], vis[N];
int depth[N];
int fac[N], inv[N], ifac[N];
int binom(int x, int y) {
    return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
int catalan(int x) {
    if (!x) return 1;
    return binom(x + x, x) * inv[x + 1] % mod;
}
signed main() {
    int T;
    cin >> T;
    fac[0] = inv[0] = ifac[0] = 1;
    fac[1] = inv[1] = ifac[1] = 1;
    for (int i = 2; i < N; ++i) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        ifac[i] = ifac[i - 1] * inv[i] % mod;
    }
    while (T--) {
        int n;
        cin >> n;
        cout << catalan(n) << '\n';
        vis[n + n + 1] = 1;
        for (int i = 1; i <= n + n; ++i) vis[i] = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> l[i] >> r[i];
            for (int j = 0; j <= n; ++j) depth[j] = 0;
            vis[l[i]] = 2, vis[r[i]] = 1;
            int res = 1, nowdep = 0;
            for (int j = 1; j <= n + n; ++j) {
                if (vis[j]) {
                    if (vis[j] == 1) {
                        res = res * catalan(depth[nowdep] >> 1) % mod;
                        depth[nowdep--] = 0;
                    } else ++nowdep;
                } else ++depth[nowdep];
            }
            res = res * catalan(depth[0] >> 1) % mod;
            cout << res << ' ';
        }
        cout << '\n';
    }
    return 0;
}

F2

暂时不会，下午更新

有帮助，赞一个

去预览

0/2000

全部评论 2

复仇者_零
佬

2025-01-27 来自浙江
0
OyamaMahiro
图怎么炸了，点进去可以看

2025-01-23 来自山东
0
- アイドル
  回复OyamaMahiro
  Acgo 不能直接显示外部链接的图片哦，可以选择编辑框中的图片上传。
  
  2025-01-24 来自浙江
  0

A

B

C

D

E

F1

F2

全部评论 2

热门讨论