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)。满足 ij 的最短路径上经过的点的标号依次先递增再递减。并且递增或递减的长度都不为 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 道路

给出一张图,边权为 1q 次询问。每次询问是否存在一条 uv 的路径(不一定简单,边、点都可以重复),满足长度为 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 赛后题解
» 下一篇