CSP-S 2022 游记

zhiyangfan · 2022-10-30 19:27:37 · 个人记录

啊？我没考。那没事了。不是 vp 的，考完之后忍不住水群了然后就没有然后了。/ng

upd. 在官方数据下都通过了。

[CSP-S 2022] 假期计划

给出一张 n 个点 m 条边的无向图，和正整数 k。定义 u,v 之间是可到达的，当且仅当存在一条 u 到 v 的路径，点数不超过 k+2。每个编号大于 1 的点都有一个权值 s_i。从所有编号大于 1 的点中选出 4 个互不相同的点 a,b,c,d 满足 1,a;a,b;b,c;c,d;d,1 之间均是可到达的，并最大化它们的权值和。求出这个权值。(5\le n\le 2500,1\le m\le 10^4,0\le k\le 100,1\le s_i\le 10^{18},\rm 2s,512MB，保证存在一个合法的选择方案)

首先，我们先来看一下 k=0 的部分分。显然在这个特殊要求下，两点之间可到达的标准就严格为有边直接相连。而我们又发现，四个点中，a,d 的要求是最为严格的，因为它们要和一个固定的点 1 有边相连，考虑把合法的 a,d 点标记一下。然后限制 a,d 点的就是 b,c 点，发现我们可以枚举限制较松的 b,c 点（可以看做枚举每一条边）然后用它们去找 a,d 点。如果没有互不相同的限制，我们只需要找到与 b,c 相邻的合法点中 s 最大的那两个作为 a,d 即可。但因为有了互不相同，要考虑最大值重复的可能，所以要记录次大值，但次大值也有可能分别和另一边的最大值或另一边的原点重复，所以再记录一个次次大值，然后就够了。至于选择方面，没有必要写分讨，只需要用 3^2 枚举即可。时间复杂度 \mathcal{O}(n+m)。

然后你惊奇的发现，对于 k>0 的数据，我们可以 \mathcal{O}(n^2) 对图进行一次重构，把所有可到达的点对之间建边，共 \mathcal{O}(n^2) 条。然后就变成 k=0 的情况了。时间复杂度 \mathcal{O}(n^2)。

关于为啥记录最大值，次大值，次次大值就对了：https://www.luogu.com.cn/discuss/521207。

#include <queue>
#include <cstdio>
#include <vector>
#include <functional>
const int N = 3e3 + 10; typedef long long ll; std::vector<int> E[N], G[N];
int vis[N], ok[N], mx[N], smx[N], ssmx[N], pre[3][N]; ll s[N];
int main()
{
    int n, m, k; scanf("%d%d%d", &n, &m, &k);
    for (int i = 2; i <= n; ++i) scanf("%lld", s + i);
    for (int i = 1, x, y; i <= m; ++i)
        scanf("%d%d", &x, &y), E[x].push_back(y), E[y].push_back(x);
    auto bfs = [&](int u)
    {
        std::queue<std::pair<int, int>> q; q.emplace(u, 0);
        while (!q.empty())
        {
            auto p = q.front(); int u = p.first, d = p.second; q.pop();
            if (d > k) continue;
            for (auto v : E[u])
                if (!vis[v]) vis[v] = 1, q.emplace(v, d + 1);
        }
    };
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j) vis[j] = 0;
        vis[i] = 1; bfs(i);
        for (int j = 1; j <= n; ++j) if (i != j && vis[j]) G[i].push_back(j);
    }
    for (auto v : G[1]) ok[v] = 1;
    for (int u = 2; u <= n; ++u)
    {
        for (auto v : G[u]) 
        {
            if (!ok[v]) continue;
            if (s[v] >= s[mx[u]]) ssmx[u] = smx[u], smx[u] = mx[u], mx[u] = v;
            else if (s[v] >= s[smx[u]]) ssmx[u] = smx[u], smx[u] = v;
            else if (s[v] >= s[ssmx[u]]) ssmx[u] = v;
        }
        pre[0][u] = mx[u]; pre[1][u] = smx[u]; pre[2][u] = ssmx[u];
    }
    ll ans = 0;
    for (int u = 2; u <= n; ++u)
        for (auto v : G[u])
            for (int a = 0; a < 3; ++a)
                for (int b = 0; b < 3; ++b)
                {
                    if (pre[a][u] && pre[b][v] && pre[a][u] != pre[b][v] && pre[a][u] != v && pre[b][v] != u)
                        ans = std::max(ans, s[u] + s[v] + s[pre[a][u]] + s[pre[b][v]]);
                }
    printf("%lld\n", ans); return 0;
}

[CSP-S 2022] 策略游戏

给出一个长为 n 的数组 a 和长为 m 的数组 b。A 和 B 在做游戏，共 q 轮游戏，每轮游戏给出四个参数 l_1,r_1,l_2,r_2，A 先从 a_{l_1..r_1} 中选出一个数 x，B 再从 b_{l_2..r_2} 中选出一个数 y，则本轮游戏的结果是 x\times y。A 要最大化这个结果，B 要最小化这个结果，问二人都采取最优策略的情况下每轮游戏的结果。(1\le n,m,q\le 10^5,|a_i|,|b_i|\le 10^9,\rm 1s,512MB)

首先考虑最优策略是什么。因为是 B 后选，所以 B 知道的信息会更多。所以我们从 B 的角度切入。

• 如果 b_{l_2..r_2} 中有正有负，那 B 一定可以把结果变成负数。则 A 就要让这个负数的绝对值尽可能小。y 显然是应该是与 x 符号相反的数中绝对值最大的那个。而 x 应该是和它符号相同的数中绝对值最小的那个。把 x 取正和取负的情况取 \max 即可。
• 如果 b_{l_2..r_2} 中只有非负。那我们考虑 A 的选择，A 肯定能选非负数选非负数，而且是绝对值最大的非负数，此时 B 应该选绝对值最小的数。而 A 如果选不了非负数，那只能选绝对值最小的负数，此时 B 应该绝对值最大的数。
• 如果 b_{l_2..r_2} 中只有非正。类似上一种。

发现需要支持维护 a,b 中只考虑非负或者非正的静态区间最值。用 ST 表即可。时间复杂度 \mathcal{O}(n\log n+q)。

#include <cmath>
#include <cstdio>
#include <algorithm>
const int N = 1e5 + 10, inf = 2e9; typedef long long ll;
int a[2][N], mn[2][2][20][N], mx[2][2][20][N];
int main()
{
    int n[2], q; scanf("%d%d%d", n, n + 1, &q);
    for (int i = 1; i <= n[0]; ++i) scanf("%d", a[0] + i);
    for (int i = 1; i <= n[1]; ++i) scanf("%d", a[1] + i);
    for (int o = 0; o < 2; ++o)
        for (int i = 1; i <= n[o]; ++i)
        {
            mx[o][0][0][i] = (a[o][i] <= 0 ? a[o][i] : -inf);
            mn[o][0][0][i] = (a[o][i] <= 0 ? a[o][i] : inf);
            mx[o][1][0][i] = (a[o][i] >= 0 ? a[o][i] : -inf);
            mn[o][1][0][i] = (a[o][i] >= 0 ? a[o][i] : inf);
        }   
    for (int a = 0; a < 2; ++a)
        for (int b = 0; b < 2; ++b)
            for (int j = 1; j < 20; ++j)
                for (int i = 1; i + (1 << j) - 1 <= n[a]; ++i)
                    mx[a][b][j][i] = std::max(mx[a][b][j - 1][i], mx[a][b][j - 1][i + (1 << (j - 1))]),
                    mn[a][b][j][i] = std::min(mn[a][b][j - 1][i], mn[a][b][j - 1][i + (1 << (j - 1))]);
    auto Max = [&](int a, int b, int l, int r)
    {
        int s = log2(r - l + 1);
        return std::max(mx[a][b][s][l], mx[a][b][s][r - (1 << s) + 1]);
    };
    auto Min = [&](int a, int b, int l, int r)
    {
        int s = log2(r - l + 1);
        return std::min(mn[a][b][s][l], mn[a][b][s][r - (1 << s) + 1]);
    };
    for (int i = 1, l1, r1, l2, r2; i <= q; ++i)
    {
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (Min(1, 1, l2, r2) < inf && Min(1, 0, l2, r2) < inf)
        {
            ll a1 = -2e18, a2 = -2e18;
            if (Min(0, 1, l1, r1) < inf) 
                a1 = (ll)Min(0, 1, l1, r1) * Min(1, 0, l2, r2);
            if (Min(0, 0, l1, r1) < inf) 
                a2 = (ll)Max(0, 0, l1, r1) * Max(1, 1, l2, r2);
            printf("%lld\n", std::max(a1, a2));
        }
        else if (Min(1, 1, l2, r2) < inf)
        {
            if (Min(0, 1, l1, r1) < inf) 
                printf("%lld\n", (ll)Max(0, 1, l1, r1) * Min(1, 1, l2, r2));
            else printf("%lld\n", (ll)Max(0, 0, l1, r1) * Max(1, 1, l2, r2));
        }
        else if (Min(1, 0, l2, r2) < inf)
        {
            if (Min(0, 0, l1, r1) < inf)
                printf("%lld\n", (ll)Min(0, 0, l1, r1) * Max(1, 0, l2, r2));
            else printf("%lld\n", (ll)Min(0, 1, l1, r1) * Min(1, 0, l2, r2));
        }
        else puts("0");
    }
    return 0;
}

[CSP-S 2022] 星战

给出一张 n 个点 m 条边的有向图。定义一个有向图是合法的，当且仅当：

• 从任意一点出发均可到达一个环。
• 每个点的出度为 1。

有 q 次操作，共四种：

• 删除一条边。
• 恢复一条边。
• 删除终点是某个点的所有边。
• 恢复终点是某个点的所有边。

每次操作后求现在的图是否合法。(1\le n,m,q\le 5\times 10^5,\rm 2s,512MB)

转化一下题意，我们需要判断原图是不是一个内向基环树森林。这里对于有向图定义的内向基环树是这样的：如果把环缩为一个点，则原图是一个内向树。每个点的出度为 1 保证了 n=m，不妨设图弱连通（否则对于每个弱连通块考虑），则因为弱连通，所以是个基环树。为了保证所有点都能到达这个环，应该是内向基环树。

而是内向基环树森林的充要条件是所有点出度为 1。但你发现直接维护这个奇怪的东西实在太难了。

题外话。在群里有人询问下文这么神奇思路是怎么想到的。dottle 老师说，他考场上看了半个小时还不会，于是就觉得这玩意不像有确定性算法。然后发现这个条件限制特别强，所以考虑哈希。

你发现如果我们把每个边用它的起点代表。则所有点出度为 1 相当于把所有边转化成点后，每个点恰好出现了一次。考虑用哈希维护这个过程。具体来讲，就是给每个点赋一个随机权值，然后边的权值是它对应点的权值。我们只需要检查所有边权值的异或和是否等于所有点权值的异或和就好了。我们保证点数等于边数后，就不需要担心出现三次和出现一次的区别了。维护边权值的异或和和边数比较简单，考虑记录每个点删之前以它为终点边的权值异或和和和数量当前的异或和和数量即可。时间复杂度 \mathcal{O}(n+m+q)。

关于这个随机的正确性。我不会分析。对于线性基之类的不太了解，因为你考虑出问题是要有某个点的权值被其他点表示出来的。

#include <ctime>
#include <cstdio>
#include <random>
std::mt19937_64 rnd(time(0));
const int N = 5e5 + 10; typedef long long ll; 
ll c[N], v[N], rc[N]; int cnt[N], rcnt[N];
int main()
{
    int n, m, o = 0; scanf("%d%d", &n, &m); ll a = 0, b = 0;
    for (int i = 1; i <= n; ++i) v[i] = rnd(), a ^= v[i];
    for (int i = 1, x, y; i <= m; ++i)
    {
        scanf("%d%d", &x, &y);
        ++rcnt[y]; rc[y] ^= v[x]; b ^= v[x];
    }
    for (int i = 1; i <= n; ++i) cnt[i] = rcnt[i], c[i] = rc[i], o += cnt[i];
    int q; scanf("%d", &q);
    for (int t = 1, op, x, y; t <= q; ++t)
    {
        scanf("%d%d", &op, &x);
        if (op == 1)
        {
            scanf("%d", &y); --o;
            --cnt[y]; c[y] ^= v[x]; b ^= v[x];
        }
        else if (op == 2) o -= cnt[x], b ^= c[x], c[x] = 0, cnt[x] = 0;
        else if (op == 3)
        {
            scanf("%d", &y); ++o;
            ++cnt[y]; c[y] ^= v[x]; b ^= v[x];
        }
        else o += (rcnt[x] - cnt[x]), b ^= (c[x] ^ rc[x]), c[x] = rc[x], cnt[x] = rcnt[x];
        puts(o == n && a == b ? "YES" : "NO");
    }
    return 0;
} 

[CSP-S 2022] 数据传输

给出一棵 n 个点的树和正整数 k，每个点有权值 c_i。有 q 次询问，每次询问给出 s,t，找出一个路径序列 \left<p_1,p_2,p_3,\cdots,p_m\right>，满足 p_1=s,p_m=t，且 \mathrm{dis}(p_i,p_{i+1})\le k,i<m，距离定义为边数。并最小化 \sum\limits_i c_{p_i}，求出最小的权值和。(1\le n,q\le 2\times 10^5,1\le k\le 3,\rm 3s,1GB)

我自己想的 \rm dp 做法比较麻烦，分讨很多，对于我非常不友好。（你就考虑设 f_{u,0/1/2} 表示当前所在点距离 u 为 0/1/2，然后写好转移后用矩乘倍增优化一下，再在 \rm lca 处合并）所以学习了 dottle 老师的神奇做法。

考虑对题意转化，每次可以选择一个相邻的点走，可以计入权值，也可以不计入权值，但每次连续不计入权值的点数不能超过 k-1，问从 s 到 t 的最小权值和。一个暴力做法是建分层图跑最短路。

考虑对这玩意优化，还是回到 \rm dp，考虑设 f_{u,0/1/2} 表示当前在点 u，已经连续 0/1/2 个点没计入权值了。我们发现，因为树上简单路径是唯一的，所以无论如何，这条路径上的点都会被经过（不一定计入权值），所以我们只对于路径上的点做这个 \rm dp 没有问题。

设 l=\operatorname{lca}(s,t)，我们考虑分别对 s,l 和 t,l 这两条链计算，当然有时候链可能退化成点不过无所谓。假如我们通过某种方法，得到了 s,l 链从 s 开始 \rm dp 对应的 f_{l,0/1/2}，不妨记为 S_{0/1/2}，和 t,l 链从 t 开始 \rm dp 对应的 f_{l,0/1/2}，不妨记为 T_{0/1/2}。考虑通过合并 S,T 得到答案。

• 对于 S_0,T_0，因为最后都停在了 l，所以 c_l 多算了一次，答案为 S_0+T_0-c_l。
• 对于 S_i,T_j，如果 i+j\le k，则可以直接接上，答案为 S_i+T_j，否则需要找一个中转点，答案为 S_i+T_j+v_l。其中 v_l 表示与与 l 距离 \le 1 的中权值最小的。我来画个图说明这时候是什么情况。
  • 这是 i+j\le k 的情况。红色的代表 u，绿色的代表 j，黄色和黄绿色代表当前实际在的点。则我们一步就能接上。\le k 是因为重叠了一个。
  • 这是 i+j>k 的情况。此时我们需要一个中转站。显然只能是与 l 距离不超过 1 的点。

会合并之后我们来看看 \rm dp 的计算。我们先考虑怎么从 f_{u,0/1/2} 更新到 f_{\mathrm{fa}_u,0/1/2}。

我们考虑从 u 到 \mathrm{fa}_u 能怎么走。

• 首先比较简单的，不管之前怎么说，我们直接走到 \mathrm{fa}_u 并计入权值。长这样：

  这个转移形如：

  f_{\mathrm{fa}_u,0}\leftarrow\min_{i=0}^{k-1}\{f_{u,i}\}+c_{\mathrm{fa}_u}

• 然后是，不管之前怎么说，我们直接走到 \mathrm{fa}_u 但不计入权值。长这样：

  这个转移形如：

  f_{\mathrm{fa}_u,i}\leftarrow f_{u,i-1}

• 最后是一个比较复杂的情况，类似我们合并时的方案，如果不想在 \mathrm{fa}_u 处记录权值，但又已经连续两次不计入权值了怎么办？考虑中转站。即走到一个与 u 相邻的点，计入权值，然后再走到 \mathrm{fa}_u，不计入权值。长这样：

  这个转移形如：

  f_{\mathrm{fa}_u,2}\leftarrow f_{u,2}+v_u

  注意只有 k=3 的情况可能出现这种转移。这里 v_u 的意义与上文相同。用距离不超过 1 也没问题，反正恰好取到 u 的时候不会错。

容易发现单次转移可以用 3\times 3 的矩阵乘法表示。因为不带修改，直接倍增维护矩乘即可在 \mathcal{O}(k^3\log n) 的时间复杂度下回答单次询问，总时间复杂度 \mathcal{O}(k^3(n+q)\log n)。

#include <cstdio>
#include <vector>
#include <cstring>
#include <functional>
const int N = 5e5 + 10; typedef long long ll; const ll inf = 1e15; 
ll dis[3][3][20][N]; int fa[20][N], c[N], v[N], dep[N]; std::vector<int> T[N];
int main()
{
    int n, q, k; scanf("%d%d%d", &n, &q, &k); memset(dis, 0x3f, sizeof (dis));
    for (int i = 1; i <= n; ++i) scanf("%d", v + i), c[i] = v[i];
    for (int i = 1, x, y; i < n; ++i)
    {
        scanf("%d%d", &x, &y), T[x].push_back(y), T[y].push_back(x);
        c[x] = std::min(c[x], v[y]); c[y] = std::min(c[y], v[x]);
    }
    auto chkmn = [&](ll& a, ll b) { a = std::min(a, b); }; 
    std::function<void(int, int)> dfs = [&](int u, int f)
    {
        fa[0][u] = f; dep[u] = dep[f] + 1;
        for (int i = 1; i < 20; ++i) fa[i][u] = fa[i - 1][fa[i - 1][u]];
        if (k == 1) dis[0][0][0][u] = v[f];
        else if (k == 2) 
        {   
            dis[1][0][0][u] = dis[0][0][0][u] = v[f];
            dis[0][1][0][u] = 0;
        }
        else
        {
            dis[0][0][0][u] = dis[1][0][0][u] = dis[2][0][0][u] = v[f];
            dis[0][1][0][u] = dis[1][2][0][u] = 0;
            dis[2][2][0][u] = c[u];
        }
        for (int i = 1; i < 20; ++i) 
            for (int a = 0; a < k; ++a)
                for (int b = 0; b < k; ++b)
                    for (int c = 0; c < k; ++c)
                        chkmn(dis[a][c][i][u], dis[a][b][i - 1][u] + dis[b][c][i - 1][fa[i - 1][u]]);
        for (auto v : T[u]) if (v != f) dfs(v, u);
    }; dfs(1, 0);
    auto LCA = [&](int u, int v)
    {
        if (dep[u] < dep[v]) std::swap(u, v);
        for (int i = 19; ~i; --i)
            if (fa[i][u] && dep[fa[i][u]] >= dep[v]) u = fa[i][u];
        if (u == v) return u;
        for (int i = 19; ~i; --i)
            if (fa[i][u] != fa[i][v]) u = fa[i][u], v = fa[i][v];
        return fa[0][u];
    };
    auto calc = [&](int u, int l)
    {
        std::vector<ll> f(3); f[0] = v[u]; f[1] = f[2] = inf;
        for (int i = 19; ~i; --i)
            if (fa[i][u] && dep[fa[i][u]] >= dep[l])
            {
                std::vector<ll> g(3, inf);
                for (int a = 0; a < k; ++a)
                    for (int b = 0; b < k; ++b) 
                        chkmn(g[b], f[a] + dis[a][b][i][u]);
                f = g;
                u = fa[i][u];
            }
        return f;
    };
    auto work = [&](int x, int y)
    {
        int l = LCA(x, y); auto f = calc(x, l), g = calc(y, l);
        ll ans = inf;
        chkmn(ans, f[0] + g[0] - v[l]);
        for (int a = 0; a < k; ++a)
            for (int b = 0; b < k; ++b)
                chkmn(ans, f[a] + g[b] + (a + b > k ? c[l] : 0));
        return ans;
    };
    for (int i = 1, x, y; i <= q; ++i)
        scanf("%d%d", &x, &y), printf("%lld\n", work(x, y));
    return 0;
}