华泰证券初赛

只做出来了一个题。。。。。。

https://www.nowcoder.com/discuss/505731702297219072 题解。

先存了，怕找不到了。C题应该是能做，嫌麻烦了。

B：

题意：两个人轮流对 $x$ 操作，减10/除以6（必须是12的倍数），谁先把 $x$ 变成6谁赢，问先手必胜还是必败。

知识点：博弈/数学

首先12的倍数除以6仍然是以6结尾的（证明如下，12的倍数除以6依然是偶数，由于6结尾的数除以6的尾数要么是6要么是1，因此结尾就只能是6了）。

因此本题的 $x$ 将永远是6结尾，我们只需要关注十位数以上的数（包含十位数）什么时候变成0就可以了。对于 $x = 10 k + 6$ ，我们如果要保证 $x$ 是12的倍数，那么 $k$ 必须是奇数。因为 $x = 2 * (5 k + 3)$ ，只有 $k$ 是奇数才能保证 $5 k + 3$ 是偶数。

因此，先手则有以下必胜策略：若 $k$ 为奇数，直接进行减10操作，那么此时 $k$ 变成了偶数，对方就只能进行减10操作。这样最终使得 $k$ 变成0的一定是自己；若 $k$ 是偶数，自己就只能进行减10操作使得 $k$ 变成奇数，那么此时获胜权就来到了对方的手里——直接进行减10操作即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    if (n / 10 % 2) {
        cout << "kou" << endl;
    } else {
        cout << "yukari" << endl;
    }
    return 0;
}

C 小红的rpg游戏

题意：给定一个矩阵，和一些上下左右操作。现在需要简化操作，每次选定一个终点走唯一的最短路，使得路线和原操作相同。

知识点：最短路

我们观察到 $n, m$ 的范围只有40，因此这道题可以先预处理出任意两点的最短路，之后即可O(1)获取。

当我们判断能否通过一次设定目的地时，我们的逻辑如下：假设 $[l, r]$ 区间的操作指令满足最短路长度恰好等于指令数量（且最短路唯一），而[l,r+1]则不符合，此时我们即可通过一次设定 $r$ 来执行 $[l, r]$ 的所有指令。

#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int n, m;
char s[42][42];
string ord;
int d[42][42][42][42];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i] + 1;
    }
    cin >> ord;
    int x = 0, y = 0;
    memset(d, 0x3f, sizeof(d));
    auto bfs = [&](int sx, int sy) {
        queue<PII> q;
        q.push({sx, sy});
        auto dd = d[sx][sy];
        dd[sx][sy] = 0;
        while (q.size()) {
            auto [x, y] = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i) {
                int tx = dx[i] + x, ty = dy[i] + y;
                if (dd[tx][ty] > dd[x][y] + 1 && s[tx][ty] != '*' && s[tx][ty]) {
                    q.push({tx, ty});
                    dd[tx][ty] = dd[x][y] + 1;
                }
            }
        }
    };
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i][j] == 'R') {
                x = i;
                y = j;
            }
            if (s[i][j] != '*') {
                bfs(i, j);
            }
        }
    }
    auto get = [&](char c) -> PII {
        if (c == 'W') {
            return {-1, 0};
        }
        if (c == 'S') {
            return {1, 0};
        }
        if (c == 'A') {
            return {0, -1};
        }
        return {0, 1};
    };
    int ans = 0;
    vector<PII> path;
    path.push_back({x, y});
    for (int i = 0; i < ord.size(); ++i) {
        auto [dx, dy] = get(ord[i]);
        x += dx;
        y += dy;
        path.push_back({x, y});
    }
    auto check = [&](int u, int v, int w) {
        auto [sx, sy] = path[u];
        auto [ex, ey] = path[w];
        auto dd = d[sx][sy];
        if (dd[ex][ey] != w - u) {
            return false;
        }
        for (int i = 0; i < 4; ++i) {
            int tx = ex + dx[i], ty = ey + dy[i];
            if (!s[tx][ty] || s[tx][ty] == '*') {
                continue;
            }
            if (path[v] == (PII){tx, ty}) {
                continue;
            }
            if (dd[ex][ey] == dd[tx][ty] + 1) {
                return false;
            }
        }
        return true;
    };
    for (int i = 0; i + 1 < path.size();) {
        ++ans;
        int j = i;
        while (j + 1 < path.size() && check(i, j, j + 1)) {
            ++j;
        }
        i = j;
    }
    cout << ans << endl;
    return 0;
}

C 小红的rpg游戏

搜索

标签

存档