“码王杯”黑龙江工程学院第十届校赛题解

黑工程的神秘人

2024-04-01 15:18:20

发布于：黑龙江

57阅读

0回复

0点赞

大钻石

题目没有输入要求，要求程序输出特定的字符串。在这个问题中，输出字符串为“大钻石，XXX”，其中“XXX”是一个需要参赛者猜测的隐藏信息。这是哈尔滨市地铁上魔性的**语，大钻石，选莱驰。

恋爱脑的小高

这个问题是一个策略游戏问题，其中涉及到数学逻辑和策略性决策。

解题思路

本题的关键在于理解“第二小因数”对游戏的影响。对于非质数 $n$ ，其第二小因数将大于1，这意味着小高第一次能数的数字范围有限制，而男朋友可以从小高停止的数字后继续开始数到第二小因数即可。那么男朋友一定可以获胜，也就是无论 $n$ 为多少，都输出1即可。

完蛋！！！我被质数包围了？

解题思路

根据哥德巴赫的强猜想，每个大于5的整数都可以表示为三个质数的和。如果我们可以将数组中前n-3个数变成2，然后最后3个数字和如果大于5，则可以表示为最多三个质数的和，那么通过相应的增减操作，理论上我们可以使数组中的每个元素都变为质数。

结论

依据哥德巴赫的强猜想，我们可以认为，只要数组中的和都大于2n- 1，就总有办法通过加减操作使每个数成为质数。因此，解题的关键是检查数组中是否数组中的和都大于2n- 1。如果是，根据猜想，输出"Yes"；否则，输出"No"。这种方法在数学上是合理的，但实际上，哥德巴赫的猜想尚未得到证明，因此这种方法有一定的理论基础，但在数学上还不是完全确定的。

CharyChung和HashBuke的数字游戏

解题思路

这个问题本质上是一个博弈问题，其中涉及到Nim游戏的变种。在这个游戏中，每个序列元素 $*_i$ 对应的Nim值由特定的算法计算得出，该算法依赖于 $m$ 和 $*$ 的值。

通过将每个 $*_i$ 除以 $g$ ，其中 $g$ 是 $*$ 和 $m$ 的最大公约数（GCD），我们简化了问题。接下来，使用Sprague-Grundy定理，计算每个元素的Nim值，以决定游戏的胜负。

核心思路是：

通过给定的规则计算每个元素的Nim值。
Nim值的异或和为零时，后手赢；否则，先手（CharyChung）赢。
对于每个 $*_i$ ，计算可以选择的 $x$ 的数量，这些 $x$ 会导致CharyChung赢得游戏。

AC代码


#include <algorithm>
#include <cstdio>
using namespace std;

int main() {
    static const long long mod = 998244353;
    static const int maxn = 300010;
    int n, m, *;
    scanf("%d %d %d", &n, &m, &*);
    auto gcd = [](int x, int y) {
        while (x %= y) swap(x, y);
        return y;
    };
    int g = gcd(*, m);
    m /= g, * /= g;
    auto SG = [m, *](long long x) -> long long {
        if (!*)
            return x;
        if (x < m + *)
            return (x / *) & 1;
        x -= * << 1;
        long long q = x / m, r = x % m;
        if ((* << 1) <= m)
            return (r % (* << 1) >= *) ? 1 : (r >= m - *) << 1;
        return r < m - * ? 0 : min(q + 1, (m - r - 1) / (m - a)) + 1;
    };
    long long nim = 0;
    static long long A[maxn];
    for (int i = 1; i <= n; i++) scanf("%lld", A + i), A[i] /= g, nim ^= SG(A[i]);
    if (!nim) {
        printf("0\n");
        return 0;
    }
    if (!a) {
        int ans = 0;
        for (int i = 1; i <= n; i++) ans += (nim ^ A[i]) < A[i];
        printf("%d\n", ans);
        return 0;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        auto get = [m, a, SG](const long long x, const long long v) {
            long long l = 0, r = (x - a) / m;
            while (l <= r) {
                long long mid = (l + r) >> 1;
                if (SG((x - a) % m + mid * m) <= v)
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            return l;
        };
        long long v = nim ^ SG(A[i]);
        ans += (get(A[i], v) - get(A[i], v - 1)) % mod;
    }
    printf("%lld\n", ans % mod);
    return 0;
}

结论

这道题目是一个典型的Nim游戏扩展，需要理解Nim游戏的基本原理和Sprague-Grundy定理。通过计算每个序列元素的Nim值，并分析首次操作后的游戏状态，我们可以确定CharyChung能赢得游戏的策略数量。

RiverBoy的原神挑战

这个问题涉及计算一个数字序列逐位递减直到零所需的时间。由于每个位的变化都需要一秒钟，我们需要考虑每位数字递减至零所需的总时间。为了优化计算过程，我们不需要逐步模拟计时器的倒计时过程。相反，可以直接计算达到目标所需的总时间。这种方法的关键在于理解如何高效地累加每位数字对总倒计时时间的贡献。

优化策略

优化的核心在于直接计算每位数字对总倒计时时间的贡献，而不是模拟整个倒计时过程。这样，计算量大大减少，尤其是对于大数字。

每位数字对总时间的贡献等于它本身的数值。因为计时器的每个位置递减到零所需的时间就是该位置上的数字值。遍历数字的每一位，将每位的值累加起来，得到总时间。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e6 + 10;


void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    vector<int> a(n);
    int k = 0;
    for (int i = n - 1; i >= 0; i--) {
      k += (int)(s[i] - '0');
      a[i] = k;
    }
    int carry = 0;
    for (int i = 0; i < n; i++) {
      a[i] += carry;
      carry = a[i] / 10;
      a[i] %= 10;
    }
    while (carry > 0) {
      a.push_back(carry % 10);
      carry /= 10;
    }
    while (a.size() > 1 && a.back() == 0) {
      a.pop_back();
    }
    for (int i = (int)(a.size() - 1); i >= 0; i--) {
      cout << a[i];
    }
    cout << '\n';
}

signed main()
{
    int t = 1;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> t;
    while ( t -- )solve();
    return 0;
}

序列X

这个问题可以通过拓扑排序的概念来解决。我们需要判断给定的 $k$ 个序列是否可以由一个共同的序列 $x$ 通过将任意元素移动到序列头部得到。实质上，这是一个关于序列相对顺序一致性的问题。

题目解读

有 $n$ 个不同的数构成一个序列 $x$ ，这个序列的数的范围是从 1 到 $n$ 。
可以将序列 $x$ 中的任意一个数移动到序列头部来形成新的序列。
给定 $k$ 个这样的操作后的序列，要判断是否存在一个原始序列 $x$ 。

解题思路

构建有向图：考虑这些序列中每个数的相对位置，如果在某个序列中数字 $a$ 出现在数字 $b$ 之前，那么我们可以在 $a$ 和 $b$ 之间建立一个有向边。
拓扑排序：使用拓扑排序来判断这个有向图是否存在环。如果存在环，说明没有一个满足条件的原始序列 $x$ ；如果不存在环，说明存在这样的序列。
实现算法：
- 初始化入度数组和邻接表。
- 遍历每个序列，根据序列中数字的顺序在邻接表中添加边，并更新入度数组。
- 使用队列进行拓扑排序，统计排序过程中访问的节点数。
- 如果访问的节点数等于 $n$ ，说明所有节点都被访问过，图中无环，输出“YES”；否则输出“NO”。

追击123

这个问题是典型的滑动窗口问题，目标是找出包含字符'1'、'2'和'3'的最小子字符串长度。我们需要遍历字符串，同时更新一个滑动窗口，以找到包含所有三个字符的最短区间。

解题思路

初始化：使用一个哈希表来存储当前窗口中每个字符的出现次数。
扩展右端点：移动右端点（r），直到窗口包含所有三个字符。
收缩左端点：一旦找到包含所有三个字符的窗口，尝试通过移动左端点（l）来缩小窗口大小，同时保持窗口中包含所有三个字符。
更新结果：记录满足条件的最小窗口长度。

变换数字

这个问题是关于找出对给定序列中的一个子区间进行变换（将所有0变为1，所有1变为0），以使得整个序列中1的数量最大化的问题。

解题思路

前缀和计算：先计算原始序列的前缀和，用于快速获取任意区间内1的数量。
遍历所有可能的区间：对于每一个可能的区间[i,j]，通过双层循环遍历所有区间，时间复杂度为O(n^2)，计算如果将这个区间内的0和1互换后，整个序列中1的总数量。
计算变换后1的数量：
- 在区间外的1的数量为序列两端的前缀和。
- 区间内的1的数量为区间长度减去区间内原有的1的数量（即变换后的1的数量）。
更新最大值：记录在所有可能的区间变换后1的最大数量。