挑战赛31题解

本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目标题	难度
T1	小午历险记之能量调节	入门
T2	小午历险记之宝石解密	普及-
T3	小午历险记之古籍卷轴	普及-
T4	小午历险记之星核碎片	普及-
T5	小午历险记之蜂巢信标	普及/提高-
T6	小午历险记之沙漠信标	普及/提高-

T1 小午历险记之能量调节

题目大意

在一个大小为 $M$ 的环形刻度盘上，刻度从 $0$ 到 $M-1$，当前位置为 $x$，目标位置为 $y$，每次可以顺时针或逆时针移动一格，求最少需要多少次操作才能从 $x$ 走到 $y$。

题解思路

由于刻度盘是环形的，从 $x$ 到 $y$ 只有两种走法：顺时针走或者逆时针走。顺时针的步数就是从 $x$ 增加到 $y$ 的距离，如果中途越过 $M-1$ 就从 $0$ 继续；逆时针则是从 $x$ 减少到 $y$，如果减到 $0$ 以下就从 $M-1$ 继续。这两种距离都可以直接用取模来计算，分别是 $(y-x+M)\bmod M$ 和 $(x-y+M)\bmod M$。实际最优方案一定是两者中较小的那个，直接输出最小值即可。整个过程只涉及常数次运算，时间复杂度为 $O(1)$，即使 $M$ 非常大也完全没有问题。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long M, x, y;
    cin >> M >> x >> y;

    long long d1 = (y - x) % M;
    if (d1 < 0) d1 += M;

    long long d2 = (x - y) % M;
    if (d2 < 0) d2 += M;

    cout << min(d1, d2) << endl;
    return 0;
}

T2 小午历险记之宝石解密

题目大意

有 $N$ 颗宝石，进行了 $M$ 次解密仪式，每次仪式会同时激活若干颗宝石。需要判断是否对任意两颗不同的宝石 $(u,v)$，都存在至少一次仪式使它们同时被激活。

题解思路

由于 $N$ 的范围很小，只有 $100$，可以直接用一个二维数组记录宝石之间是否“共现”过。初始化一个 $N \times N$ 的布尔矩阵，表示任意两颗宝石是否在某次仪式中一起出现。对于每一次解密仪式，把其中所有宝石两两配对，在矩阵中标记为 $true$。最后再枚举所有 $1 \le u < v \le N$，如果存在某一对没有被标记过，说明它们从未同时激活过，答案就是 No；如果所有宝石对都满足条件，则输出 Yes。这种做法直接模拟题意，复杂度在数据范围内完全可以接受。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

bool ok[N][N];
int a[N];

int main() {
    int n, m;
    cin >> n >> m;

    while(m--) {
        int k;
        cin >> k;
        for (int i = 1; i <= k; i++) cin >> a[i];

        for (int i = 1; i <= k; i++) {
            for (int j = i + 1; j <= k; j++) {
                int u = a[i];
                int v = a[j];
                ok[u][v] = true;
                ok[v][u] = true;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (!ok[i][j]) {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;
    return 0;
}

T3 小午历险记之古籍卷轴

题目大意

小午一开始有 $N$ 本卷轴，编号任意。在开始研读前，可以反复进行“卖两本换一本”的操作。之后他要从第 $1$ 卷开始，按顺序连续研读，问最多能连续研读到第几卷。

题解思路

可以把问题理解成：我们关心的是哪些编号的卷轴最终能被凑出来，而不是它们具体是怎么来的。只要某个编号最终能有一本，就可以用来研读。

先用一个布尔数组记录当前手中是否已经拥有某个编号的卷轴。读入初始卷轴时，如果编号已经出现过，或者编号大于当前可能用到的范围，这些卷轴都不可能直接用于研读，就当作“多余卷轴”，计入一个变量 sold，表示可以拿来卖掉的数量。

接下来用两个指针维护当前状态：
L 表示当前最小缺失的编号，也就是下一本想要研读的卷号；
R 表示当前最大的、已经拥有的编号，用来在必要时拆掉换资源。

循环中有两种操作方式：

• 如果手里有至少 $2$ 本多余卷轴，就可以直接“卖两本换一本”，把缺失的 $L$ 号卷轴补出来；
• 否则，只能从当前已有的最大编号 $R$ 中拆掉一本，把它变成一份多余卷轴，再继续尝试。

当既无法合成新卷轴，又无法继续拆已有卷轴时，说明已经无法补出下一个连续编号，研读过程结束。此时 $L-1$ 就是最多能连续研读到的卷号。

整个过程每本卷轴最多只会被处理常数次，时间复杂度是 $O(N)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 300010;

bool vol[N];
int a[N];

int main() {
    int n;
    cin >> n;
    // vol[i] 表示是否已经拥有编号为 i 的卷轴
    for (int i = 0; i <= n + 1; i++) {
        vol[i] = false;
    }

    int sold = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] > n + 1) sold++;
        else if (vol[a[i]]) sold++;
        else vol[a[i]] = true;
    }

    int l = 1;
    int r = n + 1;

    while (true) {
        while (vol[l]) l++;
        while (r != 0 && !vol[r]) r--;

        if (sold >= 2) {
            sold -= 2;
            vol[l] = true;
        } 
        else {
            if (l >= r) break;
            vol[r] = false;
            sold++;
        }
    }

    cout << l - 1 << endl;
    return 0;
}

T4 小午历险记之星核碎片

题目大意

给定一个非负整数 $N$，把它看成一个二进制集合，要求输出所有非负整数 $x$，使得 $x$ 的二进制中为 $1$ 的位置全部包含在 $N$ 的二进制为 $1$ 的位置中，并按升序输出这些 $x$。

题解思路

把 $N$ 的二进制中所有为 $1$ 的位看成若干个可选的“位置”，题目要求的所有 $x$，本质上就是从这些位置中任选一些（也可以一个都不选）组成的所有子集。因为 $N$ 中为 $1$ 的比特位数量最多只有 $15$ 个，所以一共最多只有 $2^{15}$ 种情况，可以直接枚举。

具体做法是先把 $N$ 中所有为 $1$ 的位的位置取出来，存到一个数组里。设这些位置一共有 $k$ 个，那么用一个从 $0$ 到 $(1<<k)-1$ 的掩码来枚举所有子集。对于每一个掩码，如果第 $j$ 位为 $1$，就把对应的位置加到当前数中，最终得到一个合法的 $x$。把所有生成的 $x$ 存下来，排序后依次输出即可。由于总数很小，这样做时间和空间都完全没问题。

参考代码

#include <bits/stdc++.h>
using namespace std;

long long p[20];
long long v[1 << 15];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;

    int k = 0;
    for (int i = 0; i < 60; i++) {
        if ((n >> i) & 1) {
            p[k++] = i;
        }
    }
    
    int tot = 1 << k;
    for (int m = 0; m < tot; m++) {
        long long x = 0;
        for (int i = 0; i < k; i++) {
            if ((m >> i) & 1) {
                x |= (1LL << p[i]);
            }
        }
        v[m] = x;
    }

    sort(v, v + tot);
    for (int i = 0; i < tot; i++) {
        cout << v[i] << endl;
    }

    return 0;
}

T5 小午历险记之蜂巢信标

题目大意

在一个无限的六边形网格中，有 $N$ 个被激活的单元，每个单元有一个整数坐标。如果两个激活单元能通过若干次“走到相邻的激活单元”互相到达，则它们属于同一个信标网络。要求统计这些激活单元一共能形成多少个互不连通的信标网络。

题解思路

这道题本质上就是在一个特殊邻接关系的网格图中统计连通块数量。每一个被激活的蜂巢单元都可以看成一个点，若两个点的坐标满足题目给出的六种相邻关系之一，就在它们之间连一条边。最终问题就变成：给定一个无向图，求连通块个数。

由于 $N$ 只有 $1000$，可以先把所有激活单元的坐标存下来，再用一个哈希表把坐标映射到编号，方便快速判断“某个相邻坐标是否也是激活状态”。之后用 DFS 或 BFS 遍历图：维护一个访问数组，从每个尚未访问的点出发，搜索所有能到达的点，并标记为已访问，每启动一次搜索，就对应发现了一个新的信标网络。遍历结束后，搜索的次数就是答案。整体复杂度是 $O(N)$ 级别，完全可以通过。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int x[N], y[N];
bool vis[N];

int dx[6] = {-1, -1, 0, 0, 1, 1};
int dy[6] = {-1, 0, -1, 1, 0, 1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    unordered_map<long long, int> mp;
    for (int i = 1; i <= n; i++) {
        long long k = (x[i] + 1000000000LL) << 32 | (y[i] + 1000000000LL);
        mp[k] = i;
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        ans++;
        queue<int> q;
        q.push(i);
        vis[i] = true;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int d = 0; d < 6; d++) {
                int nx = x[u] + dx[d];
                int ny = y[u] + dy[d];
                long long k = (nx + 1000000000LL) << 32 | (ny + 1000000000LL);
                if (mp.count(k)) {
                    int v = mp[k];
                    if (!vis[v]) {
                        vis[v] = true;
                        q.push(v);
                    }
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}

T6 小午历险记之沙漠信标

题目大意

给定一张 $n \times m$ 的网格地图，从起点 S 出发走到终点 T，可以上下左右移动。. 可以正常通过，# 不能通过，G 是检查点，整条路径中最多只能进入 一次 G，求最少步数，若无法到达输出 -1。

题解思路

这是一个带状态限制的最短路问题。普通的 BFS 只能记录位置，但这里还需要关心“是否已经用过一次进入 G 的机会”。因此把状态扩展为三维：当前位置 $(x,y)$，以及是否已经经过过 G。
用 d[x][y][k] 表示到达 $(x,y)$，且已经经过 $k$ 次 G（$k=0$ 或 $1$）时的最短步数。用 BFS 从起点开始扩展，每次尝试向四个方向走，如果遇到 # 就跳过；如果遇到 G，只有在当前还没用过（$k=0$）时才能走，并把状态转为 $k=1$；普通格子则直接走，状态不变。
最终答案是到达 T 的两种状态中较小的步数，只要有一种能到达即可。整个 BFS 过程中每个格子最多进队两次，时间复杂度是 $O(nm)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 5;
const int INF = 1e9;

int n, m;
char g[N];
int d[N][2];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main() {
    cin >> n >> m;
    int sx = -1, sy = -1, tx = -1, ty = -1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i * m + j];
            if (g[i * m + j] == 'S') {
                sx = i;
                sy = j;
            }
            if (g[i * m + j] == 'T') {
                tx = i;
                ty = j;
            }
        }
    }

    for (int i = 0; i < n * m; i++) {
        d[i][0] = d[i][1] = INF;
    }

    queue<int> q;
    int s = sx * m + sy;
    d[s][0] = 0;
    q.push(s * 2);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        int id = v / 2;
        int k = v % 2;
        int x = id / m;
        int y = id % m;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            int ni = nx * m + ny;
            char c = g[ni];

            if (c == '#') continue;

            int nk = k;
            if (c == 'G') {
                if (k == 1) continue;
                nk = 1;
            }

            if (d[ni][nk] > d[id][k] + 1) {
                d[ni][nk] = d[id][k] + 1;
                q.push(ni * 2 + nk);
            }
        }
    }

    int t = tx * m + ty;
    int ans = min(d[t][0], d[t][1]);
    if (ans == INF) ans = -1;

    cout << ans << endl;
    return 0;
}