grade

分虽然好看但是还是有些失误。

A 越狱

给出一个字符串 S，定义一次操作为交换两个相邻的字符。求进行不超过 k 次操作得到的字典序最小的串。

|S| \leq 5\times 10^5。

一个显然的暴力是，考虑已经确定了 [1, i - 1] 的字符。接下来要确定第 i 个字符。即找到 [i, \min(n, i + k)] 中最小的字符。

这个东西可以用个数据结构维护一下。复杂度是 O（n \log n） 的。

感谢 yijan 学长教我 O(n \times 26) 的解法。

假设 k >> n，如果要把第 i 个字符向前移动，那么其位置是确定了的。因为对于所有 j < i, S(j) < S(i) 一定也都被移动了。所以 i 移动到的位置一定是这些字符确定了的后一位。

不过还是有可能因为 k 不够大，找到一个并非最小的字符。这个时候需要标记一下，之后判断位置就需要加上所有比自己大的字符的标记。

贴个 yijan 的代码吧。

void solve( ) {
    cin >> n >> k;
    scanf("%s",ch + 1);
    rep( i , 1 , n ) {
        ++ s[ch[i] - 'a'];
        int w = i;
        rep( k , 0 , ch[i] - 'a' ) w -= s[k];
        ps[ch[i] - 'a'].pb( w );
    }
    rep( i , 0 , 25 ) reverse( all( ps[i] ) );
    rep( i , 1 , n ) {
        int ok = 0;
        for( int t = 0 ; t < 26 ; ++ t ) {
            if( ps[t].size() && ps[t].back() - kl[t] <= k ) {
                k -= ps[t].back() - kl[t];
                ps[t].pop_back();
                re[i] = t + 'a';
                ++ del[t];
                ok = 1;
                rep( tr , 0 , t - 1 ) ++ kl[tr];
                break;
            }
        }
        if( !ok ) {
            int j = i;
            rep( t , 1 , n ) {
                -- del[ch[t] - 'a'];
                if( del[ch[t] - 'a'] < 0 ) re[j ++] = ch[t];
            }
            break;
        }
    }
    puts(re + 1);
}

B 骑行

给出一棵树。询问树上有多少个有序点对 (i, j)。满足 i 到 j 的最短路径上经过的点的标号依次先递增再递减。并且递增或递减的长度都不为 0。

n \leq 2 \times 10^5。

考虑枚举点 u，计算以这个点为 递增-递减 分界点的路径个数。

那么，路径可以被分为若干类。第一类是子树内的点到子树内的点，第二类是子树内的点到子树外的点。

up and down，记 f(u, 0) 表示子树内有多少点到 u 的路径是递增的（顺序为从该点到 u），f(u, 1) 表示子树外。

时间复杂度 O(n)。

typedef long long ll;

const int MAXN = 300000 + 10;

int n, f[MAXN][2], g[MAXN][2];
ll ans;
vector<int> e[MAXN];

void dfs1(int u, int fr) {
    for (auto v : e[u]) if (v != fr) {
        dfs1(v, u);
        if (v < u) {
            ans += 1ll * f[u][0] * (f[v][0] + 1);
            f[u][0] += f[v][0] + 1;
        }
        else {
//          ans += 1ll * g[u][0] * (g[v][0] + 1);
            g[u][0] += g[v][0] + 1;
        }
    }
}
void dfs2(int u, int fr) {
    for (auto v : e[u]) if (v != fr) {
        if (u > v) g[v][1] = g[u][1] + g[u][0] + 1;
        else f[v][1] = f[u][1] + f[u][0] + 1;
        dfs2(v, u);
    }
}

int main() {
    #ifdef LOCAL
        freopen("ex_ride3.in", "r", stdin);
    #endif
    IO::read(n);
    rep(i, 1, n - 1) {
        int u, v; IO::read(u), IO::read(v);
        e[u].push_back(v), e[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 0);
//  rep(i, 1, n) printf("%d %d %d %d\n", f[i][0], g[i][0], f[i][1], g[i][1]);
    rep(u, 1, n) {
        ans += 1ll * f[u][0] * f[u][1];
    }
    printf("%lld\n", 2ll * ans);
    return 0;
}

C 道路

给出一张图，边权为 1，q 次询问。每次询问是否存在一条 u 到 v 的路径（不一定简单，边、点都可以重复），满足长度为 d。

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

CSP-J 2019 T4 的多源版本。

考虑把点拆成经过奇数条边到该点，偶数条边到该点。bfs 处理出最短路。

注意判断一个孤立点到自身的最短路，存在当且仅当 d = 0。

时间复杂度 O((2n + m) + q)。

typedef pair<int, int> pii;
int dis[MAXN][MAXN][2], vis[MAXN][2];
void bfs(int s) {
    memset(vis, 0, sizeof vis);
    rep(i, 1, n) dis[s][i][0] = dis[s][i][1] = INT_MAX;
    dis[s][s][0] = 0;
    queue<pii> q;
    q.push(make_pair(s, 0));
    while (!q.empty()) {
        pii u = q.front(); q.pop();
        for (auto v : e[u.first]) {
            if (dis[s][v][u.second ^ 1] > dis[s][u.first][u.second] + 1) {
                dis[s][v][u.second ^ 1] = dis[s][u.first][u.second] + 1;
                q.push(make_pair(v, u.second ^ 1));
            }
        }
    }
}

void solve() {
    rep(i, 1, n) bfs(i);
    rep(i, 1, q) {
        int u, v, d; IO::read(u), IO::read(v), IO::read(d);
        if (u == v && e[u].empty()) puts(d == 0 ? "Yes" : "No");
        else if (d < min(dis[u][v][0], dis[u][v][1])) puts("No");
        else {
            bool ok = false;
            if (d >= dis[u][v][1]) ok |= ((d - dis[u][v][1]) % 2 == 0);
            if (d >= dis[u][v][0]) ok |= ((d - dis[u][v][0]) % 2 == 0);
            puts(ok ? "Yes" : "No");
        }

    }
}

D 一道树题

给出一个有 n 个点的树（2 | n）。

定义一组匹配为，将 n 个树划分为 \dfrac{n}{2} 组，每个点恰好在一组中。

定义两个匹配是不同的，当且仅当存在某个点，在两个匹配中与他同组的点不同。

定义一组匹配的权值为 f(S) = \displaystyle (\sum_{(u, v) \in S} \text{dis}(u, v))^2，其中 S 表示所有组形成的集合。

对于所有匹配组成的集合 U，求 \displaystyle\sum_{S \in U} f(S)。

n \leq 300000。

化化式子。

\begin{aligned} \text{LHS} &= \sum_{S \in U} (\sum_{(u, v) \in S} \text{dis(u, v)})^2 \\ &= \sum_{S \in U} (\sum_{u \leq v} \text{dis}(u, v)^2 + \sum_{(u, v) 与 (x, y) 无公共点} \text{dis}(u, v) \times \text{dis}(x, y)) \\ &= \sum_{S \in U} \sum_{u \leq v} \text{dis}(u, v)^2 + \sum_{S \in U} \sum_{(u, v) 与 (x, y) 无公共点} \text{dis}(u, v) \times \text{dis}(x, y) \end{aligned}

由于第二个和号里头 (u, v), (x, y)。这两组之间是有序的（(u, v), (x, y) 和 (x, y), (u, v) 都会算一遍），所以没有 2 的系数。

考虑分开算两个部分。

方便起见，记 \displaystyle A = \sum_{u} \sum_{v \leq u} \text{dis(u, v)},\ B = \sum_{u} \sum_{v \leq u} \text{dis}(u, v)^2,\ C = \sum_{u}( \sum_{v \neq u} \text{dis}(u, v))^2。

第一部分

就是 B 乘上一个系数。

考虑每对匹配的系数，就是 F(\dfrac{n}{2} - 1)，F(x) 代表匹配 x 组的方案数。把这一组确定以后剩下的任意匹配就好。

所以第一部就是 B \times F(\dfrac{n}{2} - 1)。

第二部分

容斥。

A \times A 可以得到任选四个点的方案，减去 C 代表至少有一个点是公共点的方案。

由于有两个点（即两组路径完全重合）是公共点的方案在 A\times A 中数了一次，在 C 中数了两次，所以还要加上一个 B 来补回来。

仅有一个点是重复的方案数在 A\times A 中数了两次，在 C 中数了两次，刚好减掉了。

没有重复的则在 A 中数了两次。因为我们要求的是有序的，所以这样也没啥问题。

所以第二部分就是 F(\dfrac{n}{2} - 2) \times (A \times A - C + B)。

现在考虑如何求出 A, B。无序有些难以处理，所以我们考虑求出有序的 A, B, C，然后乘上 \dfrac{1}{2}。

记 f(u), g(u) 分别表示 \displaystyle \sum_{v} \text{dis}(u,v) 和 \displaystyle \sum_{v} \text{dis}(u, v)^2。

考虑换根，给 u 加入 v 的子树，和给 u 删去 v 的子树。

加入子树

\displaystyle \text{sz}(u) \leftarrow \text{sz}(u) + \text{sz}(v)\\ f(u) \leftarrow f(u) + f(v) + \text{sz}(v)\\ g(u) \leftarrow g(u) + g(v) + 2\times f(v) + \text{sz}(v)

删除子树

把上面的加号改成减号就好。

typedef long long ll;

const int MAXN = 300000 + 10;
const int P = 998244353;
const int INV2 = 998244354 >> 1;

int n;
vector<int> e[MAXN];

ll sz[MAXN], f[MAXN], g[MAXN], A, B, C;
inline void add(int u, int v) { sz[u] += sz[v], f[u] = (f[u] + f[v] + sz[v]) % P, g[u] = (g[u] + g[v] + 2ll * f[v] % P + sz[v]) % P; }
inline void del(int u, int v) { sz[u] -= sz[v], f[u] = ((f[u] - f[v] - sz[v]) % P + P) % P, g[u] = ((g[u] - g[v] - 2ll * f[v] % P - sz[v]) % P + P) % P; }

void dfs1(int u, int fr) {
    sz[u] = 1;
    for (int v : e[u]) if (v != fr) dfs1(v, u), add(u, v);
}

void dfs2(int u, int fr) {
    A = (A + f[u]) % P, B = (B + g[u]) % P, C = (C + 1ll * f[u] * f[u] % P) % P;
    for (int v : e[u]) if (v != fr) del(u, v), add(v, u), dfs2(v, u), del(v, u), add(u, v);
}

ll F(int x) { ll ret = 1; rep(i, 1, x) ret = 1ll * ret * (2 * i - 1) % P; return ret; }

int main() {
    IO::read(n);
    rep(i, 1, n - 1) {
        int u, v; IO::read(u), IO::read(v);
        e[u].push_back(v), e[v].push_back(u);
    }
    dfs1(1, 0), dfs2(1, 0); ll ans = 0;
    B = 1ll * B * INV2 % P, A = 1ll * A * INV2 % P;
    ans += 1ll * B * F(n / 2 - 1) % P;
    ll cnt = F(n / 2 - 2);
    if (n > 2) (ans += 1ll * cnt * (1ll * A * A % P) % P) %= P, (ans += 1ll * cnt * B % P) %= P, ans = ((ans - 1ll * cnt * C % P) % P + P) % P;
    printf("%lld\n", ans);
    return 0;
}

复盘

本次考试共 4h。

开场看题，看了 46min。

0h16min：T1 有了个 O(n^2) 的想法。去看后面的题。

0h46min：T2 T3 都看了看，没啥思路（事实上两道题都看错了部分题意。尤其是 T3 对题目理解偏差很大）。决定码 T1。

1h42min：写完了 T1。期间各种奇怪的错误，以及开始没想清楚怎么搞导致写了很久。

2h13min：会 T2 了（虽然这个时候对于题目还是有点小误解）。

2h48min：调过了 T2。因为对于题目的小误解导致调试有点久。

2h58min：T3 rush 了一个 30 pts 的暴力。

3h07min：T3 补到了 45 pts。开始检查之前的题。

3h31min：突然会了 T3。开始码。

3h49min：T3 过了样例。此后 10min 一直在检查。

感觉自己大概都是一道题 1h 能写出来。挺稳定。这次也没怎么挂分（主要记得有大样例了）。不过至少有 1h 的时间是不必要花费的：T1 开始的时候没想清楚，导致写了很久，自己码力也不太狗。T2 存在一些小误解，没发现自己读错题了。T3 没能秒掉很可惜。

还有 T3 没特判，规避这个只能如果想到某个东西要特判提前写在纸上提醒自己了。

还有提升和努力的空间，在保证正确性的基础上加快自己做题的速度。

对 CSP-S T1 儒略日 的三份代码的分析与题解
上一篇 «
10-23 赛后题解
» 下一篇