小白月赛89题解

前言

整体评价

内测的时候，做题做一半忍不住仔细看了遍标题，确实是小白月赛啊，这个难度跟平时的小白月赛比起来要高很多，属实是上强度了。

A.伊甸之花

贪心

根据题意，要找到一个相似的，最优的就是将原先的曲子往下平移一格，或者往上平移一格。而如果数组里有一个数顶着上界，即 那么无法上移，如果有 ，则无法下移。用两个变量记录一下，如果既无法上移又无法下移，那么就输出 "No"

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 998244353;
int arr[maxn];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    int flag1 = 1, flag2 = 1;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        if (arr[i] == 1)
            flag1 = 0;
        if (arr[i] == m)
            flag2 = 0;
    }
    cout << ((flag1 | flag2) ? "Yes" : "No") << endl;
    // system("pause");
    return 0;
}

B.显生之宙

贪心

根据题意，设想一下要让结果最小，应该如何操作。很显然对于负数，把其他所有数都加上这个数，对于正数，只选择一个数增加。

然后为了让负数最大化利用，将数组从小到大排序，让最小的数放前面，就可以尽可能让更多的数加上这个负数。然后就是模拟前面说的这个操作的过程。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 10;
int arr[maxn];
void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    sort(arr + 1, arr + 1 + n);
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        arr[i] += sum;
        if (arr[i] < 0)
            sum += arr[i];
        else if (i != n)
            arr[n] += arr[i];
    }
    cout << arr[n] << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C.太阳之华

猜结论题，首先感谢样例里面把三种情况全都涉及到了

观察样例，直接猜以下结论：开始全都是蓝，则直接后手赢，如果红能一步赢，则先手赢，否则肯定会僵持住，就是平局。（证明不来）

所以这题主要代码考察如何判断红色一步直接赢，我的想法是这样：

用并查集把所有红色的连通块都缩在一起，统计选择每个连通块，能够增加的蓝色方块个数，若某个连通块该值等于场上所有蓝色方块个数，则可以一步先手赢。

再具体一点，就是遍历所有蓝色方块，四个方向枚举相邻的红色连通块，加入对应连通块编号的 set 中（比如围成圈的红色连通块，内部的一个蓝色，可能导致该连通块个数加了四次，所以用set去重，记录对应的蓝色块编号）。最好遍历所有set，找是否有

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
char ch[maxn][maxn];
int bel[maxn][maxn];
int pianx[4] = {1, 0, -1, 0}, piany[4] = {0, 1, 0, -1};
int n, m;
set<int> s[1000000];
void dfs(int x, int y, int id) {
    ch[x][y] = '@';
    bel[x][y] = id;
    for (int i = 0; i < 4; i++) {
        int xx = x + pianx[i], yy = y + piany[i];
        if (xx < 1 || xx > n || yy < 1 || yy > m || ch[xx][yy] != '#')
            continue;
        dfs(xx, yy, id);
    }
}
void solve() {
    cin >> n >> m;
    int cntb = 0, cnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> ch[i][j];
            cntb += ch[i][j] == '.';
        }
    if (cntb == n * m) {
        cout << "Blue" << endl;
        return;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (ch[i][j] == '#')
                dfs(i, j, ++cnt);
        }
    for (int i = 1; i <= cnt; i++)
        s[i].clear();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (ch[i][j] == '.') {
                for (int k = 0; k < 4; k++) {
                    int ii = i + pianx[k], jj = j + piany[k];
                    if (ii < 1 || ii > n || jj < 1 || jj > m ||
                        ch[ii][jj] != '@')
                        continue;
                    s[bel[ii][jj]].insert((i - 1) * m + j);
                }
            }
    for (int i = 1; i <= cnt; i++)
        if (s[i].size() == cntb) {
            cout << "Red" << endl;
            return;
        }
    cout << "Draw" << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

D.冥古之潮

bfs+dp，这个dp是比较典的，但是之前没见过可能忘了，所以卡题了

题干还是有点阅读理解的，这里简述一下题意：

个点， 条边的无向图，有一个特殊结点 ，接下来多次询问，每次询问给定数量 ，回答 选择 个到 的距离不同的结点 的方案数。

先单独考虑，对于确定的 ，应该要怎么做。

一个显然的步骤是，以 为起点，bfs一遍图，处理出来数组 表示距离 为 的结点的数量。

然后得到 数组后，没什么想法，以为会是组合数什么的乱搞，就卡住了。补题才知道，这里有个很典的DP模型。

设二维DP数组 表示考虑到距离 为止，选择了 个点的方案数，那么转移方程就分为距离 选或者不选两种可能。不选，直接转移。选了的话，距离 的点共有 个，所以乘 ， 即

注意取模问题。

会发现，按这种方式DP的话，选择点的数量是由小到大转移，所以直接预处理选点个数到最大为止，之后每次询问都直接 回答 即可。

代码：

#define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define db double
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 5e3;
const int mod = 1e9 + 7;
vector<int> G[maxn];
int dep[maxn], d[maxn], vis[maxn];
int dp[maxm][maxm];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, q, x;
    cin >> n >> m >> q >> x;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    queue<int> que;
    que.push(x);
    vis[x] = 1;
    int mxdep = 0;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto v : G[u]) {
            if (vis[v])
                continue;
            vis[v] = 1;
            dep[v] = dep[u] + 1;
            d[dep[v]]++;
            mxdep = max(mxdep, dep[v]);
            que.push(v);
        }
    }
    dp[0][0] = 1;
    for (int i = 1; i <= mxdep; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= mxdep; j++) {
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * d[i]) % mod;
        }
    }
    while (q--) {
        int k;
        cin >> k;
        cout << dp[mxdep][k] << endl;
    }
    // system("pause");
    return 0;
}

E.神性之陨

通过看样例的图片，会发现，为了满足题目中 只存在一条路径 ，选择的竖条都是错落开的。定义一列中，选择的连续方格为一个竖条,则合法的路径选择的竖条，要么前面的上端点和后面的下端点相连，要么前面的下端点和后面的上端点相连，相连的地方就是唯一路径在这两列中的走法。

所以自然会想到，开一个三维 数组，表示在第 行， 第 列的方格，能否作为上/下端点。又因为能作为端点的地方，都可以作为唯一路径上的点，故去统计最后一列里，能作为端点的格子数量即为答案。

转移方程也很好写，直接 的枚举每个格子，左边能作为端点的地方，判断这一列的竖条能否不超界的对应放置。

还有注意一下下标访问会不会越界，也就是竖条放置会不会超出界限的问题，很容易就把程序写好，然后发现样例过不去

看到第二个样例里面，最后统计的时候少统计了，思考原因，发现是因为最后一列中的 不需要在前一列的端点处才能放。因为长度为1的竖条只要相邻，都能使路径在这一列上唯一，所以长度为 的竖条能放置的地方是前一列所有 能放置方块 的地方，不要求必须是端点处。

这个需求跟差分的特性很相近，所以会考虑使用差分数组来维护，如果某个格子 能当上端点，那么这一列里，能放置方块的行数范围就包括了 ，然后每一列去维护这个差分数组，碰到竖条长度为1的，就使用差分数组更新 DP 数组，而非，前一列的DP数组更新。

下面讲一下我出现的错误，可选择性跳过

核心思路就是这样，但我代码写挂了，喜提出题人嘲笑

我写挂的原因是，我处理差分数组是直接对差分数组进行前缀和，所以遇到连续的1时，就对差分数组错误处理，所以错了。思路很对，但是wa了的人可以试一下下面这组样例

1
50 50
1 24 20 18 20 9 16 8 12 4 13 20 1 22 15 22 11 16 9 20 8 9 4 18 11 11 13 17 17 13 25 24 21 4 23 21 16 2 13 9 7 20 6 28 14 19 14 2 1 1

答案是42

代码环节

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define pii pair<int, int>
using namespace std;
const int maxn = 5e3 + 10;
int dp[maxn][maxn][2];  // 第i行第j列能否成为 上/下 端点
int arr[maxn];
void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j][0] = dp[i][j][1] = 0;
    for (int i = 1; i <= m; i++)
        cin >> arr[i];
    vector<int> sub(n + 2);
    sub[1] = 1;
    sub[n + 1] = -1;
    for (int j = 1; j <= m; j++) {
        if (arr[j] == 1) {
            vector<int> tem(n + 2);
            for (int i = 1; i <= n; i++) {
                sub[i] += sub[i - 1];
                if (sub[i] > 0) {
                    dp[i][j][0] = dp[i][j][1] = 1;
                    tem[i]++;
                    tem[i + 1]--;
                }
            }
            swap(sub, tem);
            continue;
        }
        for (int i = 0; i <= n + 1; i++)
            sub[i] = 0;
        for (int i = 1; i <= n; i++) {
            if (dp[i][j - 1][0]) {  // 前一列能当上端点
                if (i - arr[j] + 1 >= 1) {
                    dp[i][j][1] = dp[i - arr[j] + 1][j][0] = 1;
                    sub[i - arr[j] + 1]++;
                    sub[i + 1]--;
                }
            }
            if (dp[i][j - 1][1]) {
                if (i + arr[j] - 1 <= n) {
                    dp[i][j][0] = dp[i + arr[j] - 1][j][1] = 1;
                    sub[i]++;
                    sub[i + arr[j]]--;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans += dp[i][m][0] | dp[i][m][1];
    cout << ans << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

F.无垢之土

怎么说呢，这道题我现在依旧不太懂为什么树形dp后会自动考虑到越过顶点的情况，只是照着题解的思路，写一份仅供参考的代码放这里吧。

题解思路是：对于答案的两个顶点 和 ，在树上会有lca ，则他们相遇的时间两倍是

然后通过二分消除出生条件的限制，即二分答案时间，只去维护出生时间二倍小等于当前二分的时间的人。

我一开始想维护每个节点，它的子树中的人到达该节点的最短时间，然后取前2短的相加。不过这种思路就是答案思路去掉二分的情况，一个hack的样例就比如，2个节点，1为根，0s时，一号节点有人出生，2s时二号节点有人出生。然后不二分的话，在1号节点统计这两个人到达时间分别是0s和3s。但是正确答案显然是1号节点到2号节点等他出生，2s时二人相遇。

代码

#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define db double
using namespace std;
const int maxn = 1e5 + 10;
vector<int> G[maxn];
vector<int> t[maxn];
vector<int> mn[maxn];
int ans = inf;
int n, m;
void dfs(int u, int f, int mid) {
    vector<int> tem;
    mn[u].clear();
    for (auto it : t[u]) {
        if (it * 2 <= mid)
            tem.push_back(it);
    }
    for (auto v : G[u]) {
        if (v == f)
            continue;
        dfs(v, u, mid);
        for (auto it : mn[v])
            tem.push_back(it + 1);
    }
    sort(tem.begin(), tem.end());
    for (int i = 0; i < min(2, (int)tem.size()); i++)
        mn[u].push_back(tem[i]);
    if (tem.size() >= 2)
        ans = min(ans, tem[0] + tem[1]);
}
bool check(int mid) {
    ans = inf;
    dfs(1, 1, mid);
    if (ans <= mid)
        return 1;
    return 0;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= m; i++) {
        int a, tt;
        cin >> a >> tt;
        t[a].push_back(tt);
    }
    int l = 0, r = 1e9, ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid))
            ans = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    cout << ans << endl;
    // system("pause");
    return 0;
}

说在最后

第一次参加牛牛的内测，激动之余，模仿珂朵莉的风格放一些漂亮的图片来写题解。