目录

1. A. 乐乐的魔法项链
2. B. 买饮料最省钱
3. C. 帝国老鼠病毒
4. D. 字母移位
5. E. 逛画展
6. F. 字符串

---

A. 乐乐的魔法项链

题意

给定长度为 $n$ 的数组，魔法数定义为：各位数字之和能整除该数本身。求最长连续子数组，使得魔法数个数不超过 $k$。

$n \le 10^6$，数字值 $< 10^9$。

思路

滑动窗口（双指针）。右指针不断扩展窗口，当窗口内魔法数超过 $k$ 时左指针收缩。

1. 预处理魔法数：计算 $x$ 的各位之和，判断 $x \bmod \text{sum} = 0$
2. 维护 $[l, r]$ 窗口，记录魔法数计数 cnt
3. $r$ 右移：若 $a[r]$ 是魔法数则 cnt++
4. 当 cnt > k：左移 $l$ 直到满足条件
5. 每步更新答案

时间复杂度 $O(n \log V)$，空间 $O(1)$。

代码

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

// 判断各位数字之和能否整除自身
bool check(int x) {
    int sum = 0, t = x;
    while (t) {
        sum += t % 10;
        t /= 10;
    }
    return x % sum == 0;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int ans = 0, cnt = 0;          // cnt: 窗口内魔法数个数
    int l = 0;
    for (int r = 0; r < n; r++) {
        if (check(a[r])) cnt++;    // 右端点加入
        while (cnt > k) {          // 超过限制，收缩左边界
            if (check(a[l])) cnt--;
            l++;
        }
        ans = max(ans, r - l + 1); // 更新最长长度
    }
    cout << ans << endl;
    return 0;
}

---

B. 买饮料最省钱

题意

$N$ 家商店，第 $i$ 家单价 $a_i$，最多买 $b_i$ 瓶。需恰好买 $M$ 瓶，求最小总花费。保证 $\sum b_i \ge M$。

$N \le 2 \times 10^5$，$M, b_i \le 10^{12}$。

思路

贪心：按单价升序排序，优先从最便宜的商店买，直到凑满 $M$ 瓶。

注意 $M$ 和 $b_i$ 可达 $10^{12}$，用 long long。

时间复杂度 $O(N \log N)$。

代码

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

struct Shop {
    ll price, num;               // price: 单价, num: 库存
} a[200005];

bool cmp(Shop x, Shop y) {
    return x.price < y.price;    // 按单价升序（贪心关键）
}

int main() {
    int n;
    ll m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i].price >> a[i].num;

    sort(a + 1, a + n + 1, cmp); // 排序

    ll ans = 0, need = m;        // need: 还需购买的数量
    for (int i = 1; i <= n; i++) {
        if (need == 0) break;
        ll buy = min(need, a[i].num); // 从当前商店购买
        ans += buy * a[i].price;      // 累加花费
        need -= buy;
    }
    cout << ans << endl;
    return 0;
}

---

C. 帝国老鼠病毒

题意

初始 1 对成年鼠。每对成年鼠每月繁殖 1 对，新生鼠需 $m$ 个月后成年。老鼠不死亡，求 $n$ 个月后总对数，对 $123456789$ 取模。

$m \le 100$，$n \le 10^7$。

思路

带成熟延迟的递推。

设 $f[i]$ 为第 $i$ 个月后的总对数。

• 前 $m$ 个月：只有最初那对能繁殖，每月 +1，即 $f[i] = f[i-1] + 1$
• $m$ 个月后：之前出生的鼠开始成年，新增数量 = 第 $i-m$ 个月时的总数（即 $m$ 个月前存在的鼠都已成年）
• 递推：$f[i] = f[i-1] + f[i-m-1]$

每一步取模。时间复杂度 $O(n)$。

当 $n$ 极大时可用矩阵快速幂优化到 $O(m^3 \log n)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MOD = 123456789;

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

    vector<long long> f(n + 1);
    f[0] = 1;                        // 初始：第0个月1对

    // 前m个月：只有最初那对成年鼠在繁殖，每月固定+1
    for (int i = 1; i <= m; i++) {
        f[i] = (f[i - 1] + 1) % MOD;
    }

    // m个月后：第i-m个月的鼠已经成年，开始参与繁殖
    for (int i = m + 1; i <= n; i++) {
        f[i] = (f[i - 1] + f[i - m - 1]) % MOD;
    }

    cout << f[n] << endl;
    return 0;
}

---

D. 字母移位

题意

给定长度为 $n$ 的小写字符串 $s$ 和数组 $a$。依次执行 $n$ 步：第 $k$ 步将前 $k$ 个字符移位 $a_k$ 位（奇数步向左、偶数步向右）。字母表循环。求最终字符串。

$n \le 10^5$，$a_i \le 10^9$。

思路

暴力模拟每次对前缀移位是 $O(n^2)$，不可行。

关键观察：位置 $i$ 参与了第 $i, i+1, \dots, n$ 步，其净位移 = 这些步骤位移量的代数和（奇数步向左为负，偶数步向右为正）。

即位置 $i$ 的净位移 = $\sum_{k=i}^{n} (-1)^k \cdot a_k$（$k$ 为步骤编号）。

用后缀和 $O(n)$ 计算：从后往前累加带符号的 $a_k$，每步更新对应字符。

对 26 取模时注意处理负数：((shift % 26) + 26) % 26。

代码

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

int main() {
    int n;
    string s;
    cin >> n >> s;

    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 第k步的符号：奇数步向左(负)，偶数步向右(正)
    // 即符号 = -1（k奇数）或 +1（k偶数）
    ll suf = 0;                      // 后缀和：当前位置经历的净位移
    for (int i = n; i >= 1; i--) {
        if (i % 2 == 1) suf -= a[i]; // 奇数步：向左（负方向）
        else suf += a[i];            // 偶数步：向右（正方向）

        ll shift = ((suf % 26) + 26) % 26; // 处理负数取模
        s[i - 1] = 'a' + (s[i - 1] - 'a' + shift) % 26;
    }

    cout << s << endl;
    return 0;
}

---

E. 逛画展

题意

长为 $N$ 的数组，元素是 $[1, M]$ 的画家编号。求最短连续子数组包含全部 $M$ 位画家。多解时输出起点最小的。

$N \le 10^6$，$M \le 2000$。

思路

滑动窗口（尺取法）——最小覆盖子串模板。

1. 维护窗口 $[l, r]$ 和计数数组 cnt[M+1]，记录窗口内各画家出现次数
2. types 记录窗口内不同画家数量
3. $r$ 右移，加入新元素：
   • 若 cnt[x]==0（首次出现），types++
   • cnt[x]++
4. 当 types == M（覆盖全部），尝试收缩左边界：
   • 记录更优解
   • 移除 $a[l]$，若 cnt[a[l]] 归零则 types--
5. 重复直到 $r$ 到末尾

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

代码

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

const int N = 1000005;
int a[N], cnt[2005];               // cnt[x]: 画家x在窗口内的作品数

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int types = 0;                  // 窗口内不同画家数量
    int bestL = 1, bestR = n;      // 最优区间

    int l = 1;
    for (int r = 1; r <= n; r++) {
        if (cnt[a[r]] == 0) types++; // 新画家出现
        cnt[a[r]]++;

        // 已覆盖全部画家，尝试收缩左边界
        while (types == m) {
            if (r - l < bestR - bestL) { // 更短的区间
                bestL = l;
                bestR = r;
            }
            cnt[a[l]]--;
            if (cnt[a[l]] == 0) types--; // 该画家消失
            l++;
        }
    }

    cout << bestL << " " << bestR << endl;
    return 0;
}

---

F. 字符串

题意

给定由 .、o、? 组成的字符串 $S$（长度 $N$）。将 ? 替换为 . 或 o，要求恰好 $K$ 个 o 且 o 不能相邻。保证有解。

输出 $T$：若某位置在所有合法方案中都是 .，$T_i=$ .；都是 o，$T_i=$ o；否则 $T_i=$ ?。

$N \le 2 \times 10^5$。

思路

三步判定法：

1. 预处理冲突：若某个 ? 的前一个或后一个字符已经是 o，则这个 ? 只能填 .（否则会相邻冲突）。将这些 ? 改为 .。

2. 统计：

   • cnt1：当前已确定 o 的数量
   • cnt2：剩余 ? 的数量

3. 必然性判定（对所有剩余 ? 位置）：

   • 若 cnt1 == K：o 已经足够，所有 ? 必然填 .
   • 若 cnt1 + cnt2 == K：所有的 ? 必须填 o 才能凑满 $K$ 个
   • 其他情况：该位置 . 和 o 都有可能 → 输出 ?

正确性保证：题目保证有合法方案，因此当 cnt1+cnt2==K 时，剩余 ? 全部设为 o 不会产生相邻冲突（否则无解，矛盾）。

时间复杂度 $O(N)$。

代码

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

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;

    int len = s.size();
    s = "#" + s;                     // 1-indexed，方便边界处理

    // 第一步：将与 'o' 相邻的 '?' 强制改为 '.'
    for (int i = 1; i <= len; i++) {
        if (s[i] == '?' && (s[i - 1] == 'o' || s[i + 1] == 'o')) {
            s[i] = '.';              // 不能填 'o'，否则与已有 'o' 相邻
        }
    }

    // 第二步：统计已有 'o' 和剩余 '?' 的数量
    int cnt1 = 0;                    // 已有的 'o' 个数
    int cnt2 = 0;                    // 剩余的 '?' 个数
    for (int i = 1; i <= len; i++) {
        if (s[i] == 'o') cnt1++;
        if (s[i] == '?') cnt2++;
    }

    // 第三步：输出，对 '?' 进行必然性判定
    for (int i = 1; i <= len; i++) {
        if (s[i] == '?') {
            if (cnt1 == k)           // 已经足够 k 个 'o'
                cout << ".";
            else if (k == cnt1 + cnt2) // 需要全部 '?' 填 'o' 才够
                cout << "o";
            else                      // 两种可能都存在
                cout << "?";
        } else {
            cout << s[i];
        }
    }
    cout << endl;
    return 0;
}

---

总结

题目	算法	关键技巧
A. 乐乐的魔法项链	滑动窗口	双指针维护计数
B. 买饮料最省钱	贪心 + 排序	按单价排序，long long
C. 帝国老鼠病毒	递推	延迟成熟的斐波那契变种
D. 字母移位	后缀和	净位移 = 后缀和，取模防负
E. 逛画展	滑动窗口（尺取法）	最小覆盖子串模板
F. 字符串	必然性判定	三步法：消冲突→统计→判定