洛谷 CSP-J/S 2023 模拟赛题解

· · 个人记录

P9740 「KDOI-06-J」ION 比赛

难度：入门

设已有成绩为 s=\sum_{i=1}^n\frac{100b_i}{a_i}，若其 \geqslant t，输出 Already Au.。

否则，对于第 i 题：

#include <cstdio>
using namespace std;
int a[10], b[10];
inline int ceil(int x, int y) {
    return x % y ? x / y + 1 : x / y;
}
int main() {
    int n, au, pts = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[i], &b[i]),
        pts += 100 / a[i] * b[i];
    scanf("%d", &au);
    if (pts >= au) {
        puts("Already Au.");
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        if (pts + 100 / a[i] * (a[i] - b[i]) < au)
            puts("NaN");
        else
            printf("%d\n", ceil(au - pts, 100 / a[i]));
    }
    return 0;
}

P9741 「KDOI-06-J」翻转与反转

难度：普及-

找规律。第 i 个数将会被进行 (n-i+1) 次操作，其位置的变化是这样的：

i,1,i+1,2,i+2,3,i+3,\dots

具体而言，若 (n-i+1) 为偶数，那么它最后会在 i+\frac{n-i+1}2 的位置上；若 (n-i+1) 为奇数，那么它最后会在 1+\frac{n-i}2 的位置上。至于其值，若操作次数为奇数则需要取反。

#include <cstdio>
using namespace std;
int a[2000005], b[2000005];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (n - i + 1 & 1)
            b[(n - i + 1) / 2 + 1] = a[i] ^ 1;
        else
            b[i + (n - i + 1) / 2] = a[i];
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", b[i]);
    return 0;
}

P9742 「KDOI-06-J」贡献系统

难度：普及+/提高

贪心。首先把贡献为正的放在上面，贡献为负的放在下面，并保证贡献同号的相对位置不变。这样，上面有一段排名是没改变的，下面有一段也是。中间的部分排名都会改变，而且若是正数则排名一定上升，若是负数则排名一定下降。可以这么理解：把一个上面的负贡献抽了出来塞到下面，导致它前后位置之间的所有人全部向上一位；把一个下面的正贡献抽了出来塞到上面，导致它前后位置之间的所有人全部向下一位。又因为贡献同号的相对位置是不变的，导致我们抽出来再塞回去这个操作中，夹在中间改变排名的都是和被操作数异号的，因此中间的数我们已经实现了贡献最大化。

现在的问题是，上下各一段排名没有改变的人，如何使他们的贡献最大化。我们先考虑上面的正贡献人群。此时整一段里全部是正贡献。

引理 1：如果要对一个人进行操作，那么一定是把他往下面塞。

我们把一个人往下面塞，就是牺牲他自己的贡献，换取中间所有人的贡献，往上面塞就相反。有人就会问了，我们往上面塞，牺牲他上面的换他自己的，可能也会值得啊。是的，是会值得，但是还能更值得。我们想要让他正贡献，不需要牺牲那么多上面的，牺牲顶上一个就够了。而牺牲顶上一个，相当于把顶上那个往下面塞，所以又绕了回来，往下面塞一定不劣。

引理 2：如果要对一个人进行操作，那么一定是把他往下面塞到底。

把这个人往下塞，本来就是让他做活雷锋的，那既然做了活雷锋，就做到底嘛，让最多的人享受正贡献，反正不管他掉多少名，吃的负贡献都是不变的。明明可以让他下面的人全部吃到正贡献，为什么要在一半又塞回去呢？这样底下的人就吃不到正贡献了，血亏。

引理 3：最多只会对一个人进行操作。

如果有两个人，保留原排名高的那一个，把他塞到底，一定比两个人要更优，因为吃的正贡献是一样的，而且还少一个人的负贡献。

那么根据上面的结论，我们可以在整一段里面枚举要把哪个人塞到底，并计算把他塞到底时的总贡献。下面的负数段同理，枚举把哪一个人塞到顶。时间复杂度 \mathcal O(Tn)，但是我比较懒，没有手写分层而是直接用了 sort，于是多带了一只 \log。

#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
struct man {
    int rating, contrib, rank; // rank = rating rank
} a[200005];
inline bool comp(const man& a, const man& b) {
    return a.contrib * b.contrib > 0 ? a.rank < b.rank : a.contrib > b.contrib;
}
signed main() {
    int T;
    scanf("%lld", &T);
    while (T--) {
        int n;
        scanf("%lld", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i].rating);
            a[i].rank = i;
        }
        for (int i = 1; i <= n; i++)
            scanf("%lld", &a[i].contrib);
        sort(a + 1, a + n + 1, comp);
        int st = 0, ed = n + 1;
        while (st < n && a[st + 1].rank == st + 1 && a[st + 1].contrib > 0)
            st++;
        while (ed > 1 && a[ed - 1].rank == ed - 1 && a[ed - 1].contrib < 0)
            ed--;
        int ans = 0;
        if (a[1].contrib > 0) {
            int cost = 0, sum = 0;
            for (int i = 1; i <= st; i++)
                sum += a[i].contrib;
            for (int i = 1; i <= st; i++) {
                cost = max(cost, sum - a[i].contrib * 2);
                sum -= a[i].contrib;
            }
            ans += cost;
        }
        if (a[n].contrib < 0) {
            int cost = 0, sum = 0;
            for (int i = n; i >= ed; i--)
                sum -= a[i].contrib;
            for (int i = n; i >= ed; i--) {
                cost = max(cost, sum + a[i].contrib * 2);
                sum += a[i].contrib;
            }
            ans += cost;
        }
        for (int i = st + 1; i < ed; i++)
            if (i < a[i].rank)
                ans += a[i].contrib;
            else if (i > a[i].rank)
                ans -= a[i].contrib;
        printf("%lld\n", ans);
    }
    return 0;
}

P9743 「KDOI-06-J」旅行

难度：普及+/提高

从这里开始进入 dp 专场。这道题是完全背包在加上一些位置上的转移。

设 f_{i,j,k,l,z} 为当前在 (i,j)，手里有 k 元钱，l 张 L 公司的票，z 张 Z 公司的票。原题面中的 k 此处记为 K。初始状态为 f_{1,1,K,0,0}=1。

每次我们来到一个站点，状态都是尚未购买该站点的票的。于是我们在出站之前应该考虑买一买票，买法就是完全背包：

\begin{cases}f_{i,j,k,l,z}=f_{i,j,k,l,z}+f_{i,j,k+a_{i,j},l-1,z}\\f_{i,j,k,l,z}=f_{i,j,k,l,z}+f_{i,j,k+b_{i,j},l,z-1}\end{cases}

我觉得是不能把两种票一起买的，因为先 L 后 Z 和先 Z 后 L 会算两次，具体会不会寄我也没试，但是分开买肯定是对的。

然后买完票就上车走人：

\begin{cases}f_{i+1,j,k,l-1,z}=f_{i+1,j,k,l-1,z}+f_{i,j,k,l,z}\\f_{i,j+1,k,l,z-1}=f_{i,j+1,k,l,z-1}+f_{i,j,k,l,z}\end{cases}

时间复杂度是 \mathcal O(n^2m^2K)。需要滚动数组优化掉第一维。

#include <cstdio>
#define int long long
#define mod 998244353
using namespace std;
int dp[2][50][95][50][50];
int a[50][50], b[50][50];
signed main() {
    int n, m, K;
    scanf("%lld%lld%lld", &n, &m, &K);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%lld", &a[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%lld", &b[i][j]);
    dp[1][1][K][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)    
            for (int k = 0; k <= K; k++)
                for (int l = 0; l < n; l++)
                    for (int z = 0; z < m; z++)
                        dp[i & 1 ^ 1][j][k][l][z] = 0;
        for (int j = 1; j <= m; j++) {
            for (int k = K - a[i][j]; k >= 0; k--)
                for (int l = 1; l < n; l++)
                    for (int z = 0; z < m; z++)
                        dp[i & 1][j][k][l][z] += dp[i & 1][j][k + a[i][j]][l - 1][z],
                        dp[i & 1][j][k][l][z] %= mod;
            for (int k = K - b[i][j]; k >= 0; k--)
                for (int l = 0; l < n; l++)
                    for (int z = 1; z < m; z++)
                        dp[i & 1][j][k][l][z] += dp[i & 1][j][k + b[i][j]][l][z - 1],
                        dp[i & 1][j][k][l][z] %= mod;
            printf("%lld ", dp[i & 1][j][0][0][0] % mod);
            if (i < n)
                for (int k = 0; k <= K; k++)
                    for (int l = 1; l < n; l++)
                        for (int z = 0; z < m; z++)
                            dp[i & 1 ^ 1][j][k][l - 1][z] += dp[i & 1][j][k][l][z],
                            dp[i & 1 ^ 1][j][k][l - 1][z] %= mod;
            if (j < m)
                for (int k = 0; k <= K; k++)
                    for (int l = 0; l < n; l++)
                        for (int z = 1; z < m; z++)
                            dp[i & 1][j + 1][k][l][z - 1] += dp[i & 1][j][k][l][z],
                            dp[i & 1][j + 1][k][l][z - 1] %= mod;
        }
        puts("");
    }
    return 0;
}

P9744 「KDOI-06-S」消除序列

难度：普及+/提高

既然是 dp 专场，那么这题肯定是 dp 嘛。

首先想暴力。设 f_i 为前 i 个数，初始全为 1，把它们调整成正确状态所需要的最小代价，那么有两种做法：甩锅给前一个，自己就改自己；一波操作 1 把前面全扬了，然后再慢慢改。写成式子就是这个样子：

f_i=\min\{f_{i-1}+[i\not\in P]b_i,a_i+\sum_{j\le i,j\in P}c_j\}

后面那个 \sum 随便前缀和搞搞，时间复杂度 \mathcal O(nq)，可以拿到 55 分的好成绩。

这个时候我们就要运用一些贪心的思想。首先我们要从 a 的定义入手，在 a 上面动一下手脚。我们定义 a'_i 为“将 v_1,v_2,\dots,v_i 的值全部设为 0 的最小代价”。它的计算很简单：

a'_i=\min\{a_i,a_{i-1}+b_i\}

就是说，要么仍然是一波操作 1，要么先改前面再改当前。然后，很容易发现操作 1 最多只会进行一次，因为前面的会被后面的完全覆盖。其实我们一开始写的 dp 式就是这个意思：要么在前面执行操作 1，要么在当前位执行操作 1，不管怎样，只会进行一次。对 a' 的处理也是这样：要么现在执行操作 1，要么在前面执行。通过对 a' 的处理，我们把分散的 1 操作可能性给集中了起来，方便我们在 P 中的数进行处理。为了方便，我们将集合 P 写成一个递增序列 p。

对于每一个 p_i，我们考虑到底应该在哪里执行 1 操作才能最优，并对这个位置（记为 pos）进行分类讨论。

综上所述，dp 式就是

f_{p_i}=\min\{a'_{p_i-1}+\sum_{j=1}^{i-1}c_{p_j},f_{p_{(i-1)}}+\sum_{j=p_{(i-1)}+1}^{p_i-1}b_j\}

两只 \sum 前缀和随便搞。时间复杂度 \mathcal O(n+\sum m)。感觉这个做法绝对不止绿，给绿是因为 \mathcal O(n\log n+\sum m) 的做法好想，但是我们还是要追求最优的。顺便说一句，在 P 中的最后一个数之后还是有数的，解决办法就是在 P 中强制加入一个 (n+1)。

#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int a[500005], b[500005], c[500005], p[500005], s[500005], g[500005], dp[500005];
signed main() {
    int n;
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &b[i]);
        s[i] = s[i - 1] + b[i];
    }
    for (int i = 1; i <= n; i++)
        scanf("%lld", &c[i]);
    a[1] = min(a[1], b[1]);
    for (int i = 1; i <= n; i++)
        a[i] = min(a[i], a[i - 1] + b[i]);
    a[n + 1] = a[n];
    int q;
    scanf("%lld", &q);
    while (q--) {
        int tot = 0;
        scanf("%lld", &tot);
        for (int i = 1; i <= tot; i++) {
            scanf("%lld", &p[i]);
            g[i] = g[i - 1] + c[p[i]];
        }
        p[++tot] = n + 1;
        g[tot] = g[tot - 1];
        for (int i = 1; i <= tot; i++)
            dp[i] = min(dp[i - 1] + s[p[i] - 1] - s[p[i - 1]], a[p[i] - 1] + g[i - 1]);
        printf("%lld\n", dp[tot]);
    }
    return 0;
}

P9745 「KDOI-06-S」树上异或

难度：提高+/省选-

既然是 dp 专场，那么这题肯定是 dp 嘛。而且是树上问题，所以是树形 dp。

但是这题的答案形式是非常的便秘，套了三层，连通块内的异或和，连通块之间乘积，方案之间加和，极其逆天。我们还是从简单的情形入手。

特殊性质 A：保证对于任意 1<i\le n，f_i=i-1。

那么这个时候“树”就变成了“链”，“连通块”也就变成了“序列上的连续区间”。设 dp_i 为以 i 作为某个区间的结尾的所有方案之和。那么很显然，有

dp_i=\sum_{j=0}^{i-1}dp_j\times\bigg(\bigoplus_{k=j+1}^ix_k\bigg)

后面那个 \bigoplus 随便前缀和搞一搞，就是一个 \mathcal O(n^2) 的算法，可以喜提 0 分。

我们发现，每次都跳到区间的开头是一个非常弱智的想法，我们只需要考虑它和它的前一个点是不是接起来的，同时再维护一个当前区间的异或和，就是这样：

\begin{cases}dp_{i,j}=dp_{i-1,j\oplus x_i}\\dp_{i,x_i}=dp_{i,x_i}+\sum_{k\ge0}dp_{i-1,k}\times k\end{cases}

第一条式子就是和前一个接上，第二条就是和前一个断开，第二维就是 i 所在区间到 i 为止的异或和。dp 式子里的值是不包含 i 所在的区间的贡献的，这个贡献要在区间结束的时候才结算。这样的时间复杂度是 \mathcal O(na_i)，可以获得 8 分的好成绩。

我们仔细观察一下第一条式子，发现第二维的操作就是异或，直接套路拆位，设 dp_{i,j,k} 为 i 所在区间到 i 为止的异或和的第 j 位为 k 的情形下，在第 j 位所能做出的贡献和。那么我们试图把上面那坨式子给改写一下。首先我们看上面那坨 \sum 很不顺眼，于是设

g_i=\sum_{k\ge0}dp_{i,k}\times k

在新概念下，它应该为

g_i=\sum dp_{i,j,k}\times k\times2^j=\sum dp_{i,j,1}\times2^j

那么原来的式子就可以写成：

\begin{cases}dp_{i,j,k}=dp_{i-1,j,k\oplus(\textrm{the }j\textrm{th bit of }x_i)}\\dp_{i,j,(\textrm{the }j\textrm{th bit of }x_i)}=dp_{i,j,(\textrm{the }j\textrm{th bit of }x_i)}+(\textrm{the }j\textrm{th bit of }g_{i-1})\end{cases}

这样就得到了一个 \mathcal O(n\log a_i) 的算法，可以拿 12 分。

于是我们试图推广至树的情况。众所周知，树就是一条条链接起来。对于一个点 u，仍设 dp_{u,i,j} 为 u 为根的子树，u 所在连通块当前异或和第 i 位为 j，且 dp 值中不含 u 所在子树的贡献，g_u 的定义一模一样。每次加入一个儿子 v 的时候，考虑接或者不接。

\begin{cases}dp_{u,i,j}=dp_{u,i,j}\times dp_{v,i,0}+dp_{u,i,j\oplus1}\times dp_{v,i,1}\\dp_{u,i,j}=dp_{u,i,j}\times g_v\end{cases}

第一条是接，dp_{u,i,j} 没和 u 联通，dp_{v,i,0} 没和 v 联通，因此它们不联通，贡献直接乘，然后 u,v 所在的连通块被接在了一起，异或值也要异或在一起。第二条是不接，g_v 的本质就是所有 v 子树内的所有状态都在 v 封顶（结算贡献），然后 dp_{u,i,j} 和 g_v 没接上，不联通，直接乘。初始化就是

dp_{i,j,(\textrm{the }j\textrm{th bit of }x_i)}=1

因为在初始状态下，异或和就是 x_i。时间复杂度为 \mathcal O(n\log a_i)。个人认为这个题的方程还是很难推的，因为拆了位后的贡献就变得比较抽象，但如果推了出来还是很容易理解这个方程的。特殊性质大部分情况下都是破题点。

#include <cstdio>
#include <vector>
#define mod 998244353
using namespace std;
int dp[500005][65][2], g[500005];
long long x[500005];
vector<int> tr[500005];
void dfs(int u, int fa) {
    for (int i = 0; i < 61; i++)
        dp[u][i][(x[u] >> i) & 1] = 1;
    for (int v: tr[u])
        if (v != fa) {
            dfs(v, u);
            for (int i = 0; i < 61; i++) {
                long long f0 = dp[u][i][0], f1 = dp[u][i][1];
                dp[u][i][0] = (f0 * dp[v][i][0] + f1 * dp[v][i][1] + f0 * g[v]) % mod;
                dp[u][i][1] = (f0 * dp[v][i][1] + f1 * dp[v][i][0] + f1 * g[v]) % mod;
            }
        }
    for (int i = 0; i < 61; i++)
        g[u] = (g[u] + (1ll << i) % mod * dp[u][i][1] % mod) % mod;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &x[i]);
    for (int i = 2; i <= n; i++) {
        int f;
        scanf("%d", &f);
        tr[i].emplace_back(f);
        tr[f].emplace_back(i);
    }
    dfs(1, 0);
    printf("%d", g[1]);
    return 0;
}

P9746 「KDOI-06-S」合并序列

难度：省选/NOI−

既然是 dp 专场，那么这题肯定是 dp 嘛。而且是区间问题，所以是区间 dp。

每次我们可以用三个数合并一个区间，但是这三个数也可以是由区间合并而来的，如果把它们展开来看，就是三个小区间合并一个大区间，而且这三个区间应该满足以下条件：

----******-----*****--************----
    A    B     C   D  E          F

那么我们可以设 dp_{i,j} 表示 a_i\sim a_j 这个区间能否被合成，能就是 1，不能就是 0。为了方便，我们记：

s_{i,j}=\bigoplus_{k=i}^ja_k

这个东西前缀异或和随便做。那么很显然有一个 \mathcal O(n^6) 的做法：

dp_{A,F}=\max\limits_{A\le B<C\le D<E\le F}\{dp_{A,B}\times dp_{C,D}\times dp_{E,F}\times[s_{A,B}\oplus s_{C,D}\oplus s_{E,F}=0]\}

如果我们两个两个合并，时间复杂度就可以压至 \mathcal O(n^4)，可以拿三四十分，但是依然过不去。

我们首先定住 EF 这一段，那么前两段的异或和就固定了。我们只需要随便选出两段，使得：

那么就可以合成 AF。为了灵活性更强，我们希望这两段在满足以上条件的前提下，右边那一段的右端点（就是 D）最靠左。我们设 h_{i,j} 为两个区间中最左端点为 i，这两个区间异或和为 j，且它们满足上述条件（也就是无重叠、可合成）的最左的最右端点。那么有

dp_{A,F}=[\exists E,A<E\le F,h_{A,s_{(E,F)}}<E,dp_{E,F}=1]

现在的问题就是如何求 h。两段有点复杂，我们先求一段，设 f_{i,j} 为左端点为 i，区间异或和为 j，且区间可合成的最小区间右端点。计算的话很显然，直接全部过一遍即可。

f_{i,s_{(i,j)}}=\min\limits_{dp_{i,j}=1}\{f_{i,s_{(i,j)}},j\}

现在要把两段区间合并起来，那么我们直接枚举另一端区间的异或和以及左端点。

h_{i,j}=\min\limits_{v\ge0}\{\min_{k>f_{i,v}}\{f_{k,j\oplus v}\}\}

里面那一层 \min 可以单独提出来处理。具体而言，就是设

g_{i,j}=\min_{k\ge i}\{f_{k,j}\}=\min\{g_{i+1,j},f_{i,j}\}

那么就可以大大加快 h 的计算速度：

h_{i,j}=\min\limits_{v\ge0}\{g_{f_{(i,v)}+1,j\oplus v}\}

那么我们就可以快速计算 dp 了。但是更新了 dp 之后，又会改变 f,h,g，因为可合成区间又多了一个。我们从后往前枚举 A，这样，若 AF 成功合成，我们只考虑往后更新 f,h,g，因为前面的一点都没有算。首先是用 F 更新 f_{A,s_{(A,F)}} 和 g_{A,s_{(A,F)}}，如果 f_{A,s_{(A,F)}} 更新了就用这 F 把 h 整个刷新一遍：

h_{i,t_{(A,F)}\oplus v}=\min\limits_{v\ge0}\{g_{F+1,v}\}

输出方案的话直接 dfs 倒序输出。时间复杂度单次为 \mathcal O(n^3+n^2a_i+na_i^2)，有点抽象，但是能过。下面这个代码没有加什么优化，在洛谷评测机上跑了 4.85s，被很多卡了常的暴力吊打。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int a[550], f[550][550], g[550][550], h[550][550], dp[550][550], s[550];
int step(int A, int F) {
    if (A == F)
        return 0;
    int B, C, D, E;
    for (int i = F; i >= A + 2; i--)
        if (dp[i][F] && h[A][s[i - 1] ^ s[F]] < i) {
            D = h[A][s[i - 1] ^ s[F]];
            E = i;
            break;
        }
    for (int i = A; i < D; i++)
        if (dp[A][i] && g[i + 1][s[E - 1] ^ s[F] ^ s[A - 1] ^ s[i]] == D) {
            B = i;
            break;
        }
    for (int i = B + 1; i <= D; i++)
        if (dp[i][D] && f[i][s[E - 1] ^ s[F] ^ s[A - 1] ^ s[B]] == D) {
            C = i;
            break;
        }
    return step(A, B) + step(C, D) + step(E, F) + 1;
}
void print(int A, int F) {
    if (A == F)
        return;
    int B, C, D, E;
    for (int i = F; i >= A + 2; i--)
        if (dp[i][F] && h[A][s[i - 1] ^ s[F]] < i) {
            D = h[A][s[i - 1] ^ s[F]];
            E = i;
            break;
        }
    for (int i = A; i < D; i++)
        if (dp[A][i] && g[i + 1][s[E - 1] ^ s[F] ^ s[A - 1] ^ s[i]] == D) {
            B = i;
            break;
        }
    for (int i = B + 1; i <= D; i++)
        if (dp[i][D] && f[i][s[E - 1] ^ s[F] ^ s[A - 1] ^ s[B]] == D) {
            C = i;
            break;
        }
    print(E, F);
    print(C, D);
    print(A, B);
    printf("%d %d %d\n", A, C - B + A, E - B + A - D + C);
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        memset(a, 0, sizeof(a));
        memset(f, 63, sizeof(f));
        memset(g, 63, sizeof(g));
        memset(h, 63, sizeof(h));
        memset(dp, 0, sizeof(dp));
        memset(s, 0, sizeof(s));
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            dp[i][i] = 1;
            s[i] = s[i - 1] ^ a[i];
        }
        for (int i = n; i >= 1; i--) {
            f[i][a[i]] = min(f[i][a[i]], i);
            for (int j = 0; j < 512; j++)
                g[i][j] = min(f[i][j], g[i + 1][j]);
            for (int j = 0; j < 512; j++)
                if (f[i][j] < n)
                    for (int k = 0; k < 512; k++)
                        h[i][j ^ k] = min(h[i][j ^ k], g[f[i][j] + 1][k]);
            for (int j = i + 2; j <= n; j++) {
                for (int k = i + 2; k <= j; k++)
                    if (dp[k][j] && h[i][s[j] ^ s[k - 1]] < k) {
                        dp[i][j] = 1;
                        break;
                    }
                if (!dp[i][j])
                    continue;
                f[i][s[j] ^ s[i - 1]] = min(f[i][s[j] ^ s[i - 1]], j);
                g[i][s[j] ^ s[i - 1]] = min(g[i][s[j] ^ s[i - 1]], j);
                if (f[i][s[j] ^ s[i - 1]] < n)
                    for (int k = 0; k < 512; k++)
                        h[i][s[j] ^ s[i - 1] ^ k] = min(h[i][s[j] ^ s[i - 1] ^ k], g[f[i][s[j] ^ s[i - 1]] + 1][k]);
            }
        }
        puts(dp[1][n] ? "Huoyu" : "Shuiniao");
        if (dp[1][n]) {
            printf("%d\n", step(1, n));
            print(1, n);
        }
    }
    return 0;
}

P9747 「KDOI-06-S」签到题

难度：省选/NOI-

咕咕咕……