小白月赛89

A 伊甸之花

白色王子所在的世界里总共有 m 种节拍，编号分别是 1 到 m，一首乐曲可以想象成一个有 n 个元素的数组 a，其中的一个元素 ai 表示该曲中第 i 个音符的音高。
对于两首乐曲（即两个数组）a、b，我们认为这两首乐曲是相似的当且仅当对于任意一个 2≤i≤n，都有 ai−ai−1=bi−bi−1。
对于两首乐曲 a、b，我们认为这两首乐曲是完全相同的当且仅当对于任意一个 1≤i≤n，都有 ai=bi。
现在给出一首乐曲 a，询问是否存在一首与其不完全相同的乐曲 b 与其相似。

实际上，只要数组同时存在 1 和 m 就一定不能。

void solve() {
    int n, m;cin >> n >> m;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    if (count(a.begin(), a.end(), m) && count(a.begin(), a.end(), 1)) {
        cout << "No\n";
    } else {
        cout << "Yes\n";
    }
}

B 显生之宙

白色的王子给了你一个由 $n$ 个数组成的数列，并告诉你，你需要执行 $n - 1$ 次如下操作：选定一个数列中的数 x，再选择数列中的至少一个其他数，然后让这些数都加上 $x$ ，再将 $x$ 移除出这个数列。经过 $n - 1$ 次操作过后，数列中最后只会剩下一个数。白色的王子希望你告诉他，最后剩下的那个数最小是多少。题目保证最后输出的答案的绝对值 $\leq 4 \times 10^{18}$ 。

这题写了半天没写出来！

#define int long long
void solve() {
    int n;cin >> n;vector<int>a(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    sort(a.begin() + 1, a.begin() + 1 + n);
    int sum = 0, ans = 0;
    for (int i = 1;i <= n - 1;i++) {
        a[i] += sum;
        if (a[i] >= 0) {
            ans += a[i];
        } else {
            sum += a[i];
        }
    }
    cout << a[n] + ans + sum << '\n';
}

C 太阳之华

白色的王子摆放了一个 $n \times m$ 的棋盘，游戏开始时棋盘上的每一个格子要么是红色 # 的，要么是蓝色 . 的。
游戏规则是这样的：红方先手，双方交替进行游戏。每一方在自己的回合都可以选择一个由自己的颜色的格子组成的四连通区域，然后对于这个四连通区域的每一个格子：如果这个格子的上下左右有和该格子颜色不同的格子的话，就将这些格子染成该格子的颜色。当场上均为蓝色格子时，蓝方胜利；当场上均为红色格子时，红方胜利。

注：四连通区域指的是从区域内每一格出发，可通过四个方向，即上、下、左、右这四个方向的移动的组合，在不越出区域的前提下，到达区域内的任意格子。

现在给出初始棋盘，询问如果双方都足够聪明，有没有一方一定能够获得游戏胜利，或者是游戏永远结束不了而将以平局告终。

Solution

搜索

只要棋盘中有一个红色，那么红色一定不会输，要么红赢，要么平局。全为蓝色，蓝色才能赢。

代码中将 g[i][j]='0' 的操作实际上相当于起到开 vis 数组的作用，做到不重复访问。

如果红色一轮中能访问到的蓝色个数刚好等于蓝色总个数，则红方赢，否则平局。

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void solve() {
    int n, m;cin >> n >> m;
    vector<string> g(n + 1);
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        string s;cin >> s;s = ' ' + s;
        g[i] = s;
        cnt += count(s.begin(), s.end(), '.');
    }
    if (cnt == n * m) {
        cout << "Blue\n";return;
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (g[i][j] == '#') {
                set<pair<int, int>> res;
                queue<pair<int, int>> q;
                q.push({i,j});
                g[i][j] = '0';
                while (q.size()) {
                    auto [x, y] = q.front();q.pop();
                    for (int k = 0;k < 4;k++) {
                        int cx = x + dx[k], cy = y + dy[k];
                        if (cx<1 || cx>n || cy<1 || cy>m)continue;
                        if (g[cx][cy] == '#') {
                            g[cx][cy] = '0';q.push({cx,cy});
                        } else if (g[cx][cy] == '.') {
                            res.insert({cx,cy});
                        }
                    }
                }
                if (res.size() == cnt) {
                    cout << "Red\n";return;
                }
            }
        }
    }
    cout << "Draw\n";
}

D 冥古之潮

白色王子给你一个由 $n$ 个点和 $m$ 条无向边构成的连通图，每条边长度为 1，同时给你一个点 $x$ 。

白色王子告诉你图上有 $k$ 个锚点。记第 $i$ 个锚点所在的点编号为 $a_{i}$ ，点 $a_{i}$ 到点 $x$ 的最短距离为 $d i s_{i}$ 。他告诉你这 $k$ 个锚点的位置满足 $d i s_{1}$ < $d i s_{2}$ < ... < $d i s_{k}$ ，且对于任意一个锚点 $i$ ，都有 $d i s_{i} \neq 0$ 。保证 $D i s_{i} \leq 5000$ 。现在白色王子想知道这 $k$ 个锚点的位置有多少种可能。具体地，我们记这 $k$ 个锚点的位置组成了一个集合 $S = {a 1, a 2, . . ., a k}$ ，对于两个集合，如果他们有任意一个元素不一样，我们就认为这两个集合是不一样的。也就是说，你只需要输出合法的不同集合数即可。一共有 $q$ 组询问，每组询问给出一个 $k$ ，你需要求出锚点数量为 $k$ 时的可能位置方案数。由于答案可能过大，你只需要输出它对 $10^{9} + 7$ 取模的结果。

Solution

BFS+DP

先算出各个点到 $x$ 的距离。然后 DP (不懂待更 $\dots$ )

$d p [i] [j]$ 代表选到 $i$ 为止，选择了 $j$ 个点的方案数。若不选 $i$ ，直接转移( $d p [i] [j] = d p [i - 1] [j]$ )，若选 $i$ ，则乘上 $t o n g [i]$ .( $d p [i] [j] = d p [i] [j] + d p [i - 1] [j - 1] \times t o n g [i]$ )

#define int long long
const int mod = 1e9 + 7;
void solve() {
    int n, m, q, x;cin >> n >> m >> q >> x;
    vector<int> g[n + 1];
    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;
    vector<int> dis(n + 1), vis(n + 1), tong(5000);
    que.push(x);vis[x] = 1;
    while (que.size()) {
        int now = que.front();que.pop();
        for (auto i : g[now]) {
            if (vis[i])continue;
            vis[i] = 1;
            dis[i] = dis[now] + 1;
            tong[dis[i]]++;
            que.push(i);
        }
    }
    vector<vector<int>> dp(5001, vector<int>(5001));
    dp[0][0] = 1;
    for (int i = 1;i <= 5000;i++) {
        for (int j = 0;j <= 5000;j++) {
            dp[i][j] = dp[i - 1][j];
            if (j)dp[i][j] = dp[i][j] + dp[i - 1][j - 1] * tong[i];
            dp[i][j] %= mod;
        }
    }
    /*这和上面的等价
    for (int i = 1;i <= 5000;i++) {
        dp[i][0] = 1;
        for (int j = 1;j <= 5000;j++) {
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * tong[i];
            dp[i][j] %= mod;
        }
    }
    */
    while (q--) {
        int p;cin >> p;
        cout << dp[5000][p] << '\n';
    }
}