【ZCX-010-DIV3】智程星周赛 010 入门组题解

A. 酒

思路

分别计算三位李白喝酒的总量：

• 1 号：$a \times x + b \times y$
• 2 号：$c \times y$
• 3 号：$d \times y + e$

然后按编号从小到大更新最大值。这样如果出现并列，先出现的编号会被保留下来，也就是编号最小者。

答案要求保留两位小数，使用 fixed << setprecision(2) 输出即可。

复杂度

时间复杂度 $O(1)$，空间复杂度 $O(1)$。

参考代码

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

int main() {
    double a, b, c, d, e, x, y;
    cin >> a >> b >> c >> d >> e >> x >> y;

    // 分别计算三个人喝掉的酒量。
    double v1 = a * x + b * y;
    double v2 = c * y;
    double v3 = d * y + e;

    int id = 1;
    double ans = v1;
    // 只在严格更大时更新，这样并列时会保留较小编号。
    if (v2 > ans) {
        ans = v2;
        id = 2;
    }
    if (v3 > ans) {
        ans = v3;
        id = 3;
    }

    cout << id << ' ' << fixed << setprecision(2) << ans << '\n';
    return 0;
}

B. 传染病

思路

第 $1$ 天新增感染人数为 $a$，第 $2$ 天为 $a \times q$，第 $3$ 天为 $a \times q^2$，以此类推。

题目要求 $k$ 天内每天新增感染人数的乘积。可以一边维护当天新增人数 cur，一边把它乘进答案：

1. 初始 cur = a。
2. 循环 $k$ 天，每天令 ans = ans * cur % MOD。
3. 下一天新增人数变成 cur = cur * q % MOD。

因为 $k \le 10^6$，直接循环完全足够。注意所有乘法都要取模，并使用 long long。

复杂度

时间复杂度 $O(k)$，空间复杂度 $O(1)$。

参考代码

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

const long long MOD = 722733748;

int main() {
    long long k, a, q;
    cin >> k >> a >> q;

    long long ans = 1;
    long long cur = a % MOD; // cur 表示当天新增感染人数。
    q %= MOD;

    for (long long day = 1; day <= k; day++) {
        ans = ans * cur % MOD; // 把当天人数乘进传染系数。
        cur = cur * q % MOD;   // 推到下一天的新增人数。
    }

    cout << ans << '\n';
    return 0;
}

C. 三位数

思路

题目要求输出所有满足条件的三位数，且 $k \le 20$，所以直接枚举 $100 \sim 999$ 即可。

对于一个三位数 $i$：

• 百位 $a = i / 100$
• 十位 $b = i / 10 \% 10$
• 个位 $c = i \% 10$

需要同时满足：

• $a \times 10 + b$ 是 $k$ 的倍数；
• $b \times 10 + c$ 是 $k$ 的倍数；
• $i$ 本身是 $k$ 的倍数。

由于枚举顺序本来就是从小到大，所以直接输出即可。若没有输出过任何数，最后输出 None!。

复杂度

时间复杂度 $O(900)$，空间复杂度 $O(1)$。

参考代码

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

int main() {
    int k;
    cin >> k;

    bool found = false;
    for (int i = 100; i <= 999; i++) {
        // 拆出百位、十位、个位。
        int a = i / 100;
        int b = i / 10 % 10;
        int c = i % 10;

        // 三个条件需要同时满足。
        if ((a * 10 + b) % k == 0 &&
            (b * 10 + c) % k == 0 &&
            i % k == 0) {
            cout << i << '\n';
            found = true;
        }
    }

    if (!found) {
        cout << "None!" << '\n';
    }
    return 0;
}

D. 数字串

思路

第 $g + 1$ 个序列相邻两个 1 之间有 $g$ 个 0，也就是说 1 每隔 $g + 1$ 个位置出现一次。

设周期为 $p = g + 1$。因为 $0 \le g \le n$，所以可选周期满足：

$$1 \le p \le n + 1$$

判断字符串 $s$ 是否可能来自某个周期序列的连续截取。

分情况讨论：

1. 如果 $s$ 中没有 1，那么它必须是一段连续的 0。最长连续 0 长度可以达到 $n$，所以只要 $m \le n$ 就输出 Yes，否则输出 No。
2. 如果 $s$ 中只有一个 1，设它的位置为 pos。需要选择一个周期 $p$，使得这个 1 左边和右边都不会再出现别的 1。也就是：
   • $p \ge pos$
   • $p > m - pos$
   • $p \le n + 1$
3. 如果 $s$ 中有至少两个 1，那么相邻两个 1 的距离必须完全相等，这个距离就是周期 $p$。同时：
   • $p \le n + 1$
   • 第一个 1 前面不能还有本周期的 1，即 first <= p
   • 最后一个 1 后面不能还有本周期的 1，即 m - last < p

只要满足对应条件，就可以输出 Yes。

复杂度

每组数据扫描一遍字符串，时间复杂度 $O(m)$，空间复杂度 $O(1)$。

参考代码

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

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

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        string s;
        cin >> n >> m >> s;

        int cnt = 0;
        int first = -1, last = -1;
        int p = -1;
        bool same = true;

        for (int i = 0; i < m; i++) {
            if (s[i] == '1') {
                int cur = i + 1; // 使用 1 下标，方便和长度比较。
                if (cnt == 0) {
                    first = cur;
                } else if (cnt == 1) {
                    p = cur - last;
                } else if (cur - last != p) {
                    same = false;
                }
                last = cur;
                cnt++;
            }
        }

        bool ok = false;

        if (cnt == 0) {
            // 全是 0，要求能被某个序列中相邻 1 之间的空隙覆盖。
            ok = (m <= n);
        } else if (cnt == 1) {
            // 只有一个 1，周期要足够大，保证左右两边不会再出现 1。
            int pNeed = max(first, m - first + 1);
            ok = (pNeed <= n + 1);
        } else {
            // 至少两个 1，相邻 1 的距离必须全部相等，这个距离就是周期。
            ok = same && (p <= n + 1);

            if (first > p) {
                ok = false;
            }
            if (m - last >= p) {
                ok = false;
            }
        }

        cout << (ok ? "Yes" : "No") << '\n';
    }

    return 0;
}