【题解】2023年华泰竞赛初赛题解

A 查找客户

题意：求区间$[l,r][l,r]$中有多少正整数包含了子串$xx$。

知识点：模拟

签到题。按题意遍历然后check一下即可。（注：这道题本来是出成1e18的数据范围的，但难题数量足够了，于是出成签到题）。

大家可以思考一下，$l,rl,r$范围1e18时怎么做。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int l, r, x;
    cin >> l >> r >> x;
    int ans = 0;
    for (int i = l; i <= r; ++i) {
        if (string::npos!= to_string(i).find(to_string(x))) {
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}

B 小红和小紫玩游戏

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

知识点：博弈/数学

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

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

因此，先手则有以下必胜策略：若$kk$为奇数，直接进行减10操作，那么此时$kk$变成了偶数，对方就只能进行减10操作。这样最终使得$kk$变成0的一定是自己；若$kk$是偶数，自己就只能进行减10操作使得$kk$变成奇数，那么此时获胜权就来到了对方的手里——直接进行减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,mn,m$的范围只有40，因此这道题可以先预处理出任意两点的最短路，之后即可O(1)获取。

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

D 小红的五子棋

题意：在$n\ast mn*m$的棋盘上摆放尽可能少的白子，使得剩余格子填满黑子后也不会产生黑子的五子连珠。

知识点：构造

首先我们需要特判$min(n,m)min(n,m)$不大于4的情况。显然这种情况我们只需要考虑一种方向，直接贪心去堵就行了（每隔4个空格放一个棋子）。

对于剩下的情况，我们采用“日字”堵法：即保证每行、每列、每对角线仍然每4个放一个棋子。可以通过dfs或者手玩找到规律。

所谓"日字"堵法，即每个两个白子构成一个“日字”，即对于每个$(x,y)(x,y)$放了白子，$(x+2k,y+k)(x+2k,y+k)$、$(x-k,y+2k)(x-k,y+2k)$也需要放白子。

我们需要控制第一行的起始格子位置来确保棋子数量是最少的。这些可以通过dfs或者找规律得到最优的方案。

关于这种摆法是最优的，证明如下：

对于$n,mn,m$都不大于9的情况，直接dfs打表可证。

当$n\mathrm{或}mn或m$大于9时，我们把棋盘切割成一个$(n\mathrm{\%}5+5,m\mathrm{\%}5+5)(n\backslash \%5+5,m\backslash \%5+5)$的小棋盘，以及剩余若干个$5\ast 55*5$的棋盘。显然，最终的白子数量一定不大于每个小棋盘的白子数量之和。而每个$5\ast 55*5$的小棋盘至少需要放置5颗白子，而“日字”摆法最终的花费白子数量为$cnt(n\mathrm{\%}5+5,m\mathrm{\%}5+5)+5\ast xcnt(n\backslash \%5+5,m\backslash \%5+5)+5*x$，其中$xx$为$5\ast 55*5$小棋盘的数量。综上可知“日字摆法”在$n\mathrm{或}mn或m$大于9时也是最优的。

ps1：非常抱歉题目的checker在$n=5n=5$或者$m=5m=5$时出了点小bug，已修复并重测，影响了少部分前20的选手排名。

ps2：本题灵感来源于ecfinal的L题：构造一个01矩阵满足横向和纵向不存在四个连续的1，并要求所有的1连通，且1的数量尽可能多。

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<string>> ve;
int main() {
    ve.push_back({
        ".o...",
        "...o.",
        "o....",
        "..o..",
        "....o",
    });
    ve.push_back({
        "..o..",
        "o....",
        "...o.",
        ".o...",
        "....o",
    });
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        if (n <= 4 && m <= 4) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= m; ++j) {
                    cout << '.';
                }
                cout << endl;
            }
            continue;
        }
        if (n <= 4) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= m; ++j) {
                    if (j % 5 == 0) {
                        cout << 'o';
                    } else {
                        cout << '.';
                    }
                }
                cout << endl;
            }
            continue;
        }
        if (m <= 4) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= m; ++j) {
                    if (i % 5 == 0) {
                        cout << 'o';
                    } else {
                        cout << '.';
                    }
                }
                cout << endl;
            }
            continue;
        }
        int ti = 0, tj = 0, tp = 0, tcnt = 0;
        auto calc = [&](int x, int y, int p) {
            int cnt = 0;
            const auto &s = ve[p];
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    cnt += s[(x + i) % 5][(y + j) % 5] % 2 == 0;
                }
            }
            if (tcnt < cnt) {
                tcnt = cnt;
                tp = p;
                ti = x;
                tj = y;
            }
        };
        for (int i = 0; i <= 4; ++i) {
            for (int j = 0; j <= 4; ++j) {
                for (int p = 0; p <= 1; ++p) {
                    calc(i, j, p);
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cout << ve[tp][(ti + i) % 5][(tj + j) % 5];
            }
            cout << endl;
        }
    }
    return 0;
}