【题解】第二届“612杯”周赛 —— 完整解析与思路分享

Aerhuo 发布于 2025-12-07 92 次阅读

前言

第二届“612杯”圆满结束！感谢大家的参与。为了这场比赛，我投入了很大的精力，筛选出的题目都是我认为相当优质的题目。

例如比赛题号 F “612的取舍之道” 这道题目，很多人容易往动态规划（DP）去想，这题我参考了之前看到过的力扣的一篇讨论，参加第二届“612杯”内测的力扣1600分选手在写这题时也陷入了思维陷阱，想使用 DP 去完成这题，而实际上这题的标准解是 逆向思维，使用 滑动窗口/前缀和 简化思路。实际上，你使用动态规划，最终也只是这个方法的变形。

原本平凡的算法题，点缀上一些二次元氛围，变得更加浪漫了呢！总的来说，无论你是 AK 了的大佬，还是被卡在某道题的萌新，希望这篇题解能带给你新的收获。

注意：为方便书写，题解代码均使用 C++ 贴出。

A. 612的早八惊魂

难度：入门
核心知识点：数组遍历、最大值查找

思路解析

题目要求找出起床最晚的人的编号，直接将问题化简为找最大值及其下标。我们只需要维护一个当前最大值 mx 和对应的编号 idx，遍历输入数据，当发现比当前 mx 更大的值时，更新它们即可。

AC 代码

#include <bits/stdc++.h>

using namespace std;

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

    int idx, mx = 0;
    int num;
    for (int i = 1; i <= n; ++i)
    {
        cin >> num;

        // 更新最大值和对应的下标
        if (num > mx)
        {
            idx = i;
            mx = num;
        }
    }

    cout << idx;
}

B. 612的AA制之谜

难度：入门
核心知识点：求和、取模、浮点数输出

思路解析

简化思路，我们只需要统计总金额，然后检查总金额是否是 612 的倍数（采用取余 % 完成）。
* 如果是倍数，将金额归零。
* 如果不是，最后输出 总金额 / 人数 即可。

注意，我们需要在计算 AA 金额的时候使用浮点数，以防小数部分被截断，以及使用 printf("%.2f", ...) 或 fixed << setprecision(2) 输出金额以做到保留两位小数。

AC 代码

#include <bits/stdc++.h>

using namespace std;

int main()
{
    double n; // 使用 double 方便后续计算
    cin >> n;

    int sum = 0;
    int num;
    for (int i = 1; i <= n; ++i)
    {
        cin >> num;
        sum += num;
    }

    // 幸运数字判断
    if (sum % 612 == 0)
    {
        sum = 0;
    }

    printf("%.2f", sum / n);
}

C. 612的内卷排名

难度：入门
核心知识点：排序、结构体/映射

思路解析

可能有同学在看到这题后感到了紧张，判断李伟峰是否是最后一名看上去很难。实际上我们只需要知道李伟峰的分数 是否是最低的 即可，因为并列倒一也是倒一。

因此本题就退化为了一道简单的 从大到小排序 的题目。如果排序后，李伟峰的分数等于数组最后一个元素（最小值），则输出指定标语。

（值得注意的一点是，题目输入的 $K$ 是以 1 为起点的，因此千万不要直接用 $K$ 为下标去访问元素，需要先处理下标对齐）

AC 代码

#include <bits/stdc++.h>

using namespace std;

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

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

    int cur = a[k - 1]; // 记录李伟峰的分数

    // 从大到小排序
    sort(a.begin(), a.end(), greater<int>());

    for (int num : a)
    {
        cout << num << ' ';
    }

    cout << '\n';

    // 如果他的分数等于排序后最后一个元素（最小值）
    if (cur == a.back())
    {
        cout << "Break the involution!";
    }
}

D. 三角洲高手的超能力 (Easy Version)

难度：普及-
核心知识点：哈希表 (Map) / 计数

思路解析

从本题开始“612杯”才算是正式开始了。题目要求：
1. 找出数据中出现次数最多的数字（众数）。
2. 统计小于众数的数字数量和大于众数的数字数量。

我们可以将本题划分为两步：
1. 找众数：使用数组或哈希表记录每个数字的出现次数，遍历找出最大频次对应的数字。将数字作为数组/Map的下标，这个问题就化为了 A 题。
2. 统计大小：遍历一次输入数据，维护两个变量 greater 和 less。当数字大于众数时 greater++，当数字小于众数时 less++。

AC 代码

#include <bits/stdc++.h>

using namespace std;

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

    vector<int> a(n);
    unordered_map<int, int> record;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        record[a[i]]++; // 统计频率
    }

    int cur = 0;
    int mx = 0;

    // 寻找众数
    for (auto& pair : record)
    {
        if (pair.second > mx)
        {
            cur = pair.first;
            mx = pair.second;
        }
    }

    int less = 0, greater = 0;
    for (int num : a)
    {
        if (num < cur)
        {
            less++;
        }
        else if (num > cur)
        {
            greater++;
        }
    }

    cout << greater << ' ' << less;
}

E. 三角洲高手的超能力 (Hard Version)

难度：普及-
核心知识点：前缀和、预处理 / 二分查找
题目参考：https://blog.csdn.net/GF0919/article/details/130723385
（由于原题链接是私密的，因此贴出 CSDN 上的转发题）

思路解析

这题是算法选手与普通同学的分水岭，因为它开始真正涉及到 时间复杂度。
如果采用类似 D 题的暴力遍历解法，总复杂度为 $O(NK)$，大量的测试点会显示 TLE（超时）。

我们需要优化到每次查询 $O(1)$。
这里采用 前缀和+预处理 的解法。我们需要维护两个数组：
* less[i]：代表小于 $i$ 的数字数量。
* greater[i]：代表大于 $i$ 的数字数量。

通过递推关系：
* less[i] = less[i - 1] + cnt[i - 1] （cnt 为数字计数数组）
* greater[i] = greater[i + 1] + cnt[i + 1]

我们只需要使用两个 for 循环预处理即可，这样查询时直接输出 greater[d] 和 less[d]。

AC 代码

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    vector<int> cnt(1e5 + 2); // 计数数组

    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        cnt[a[i]]++;
    }

    vector<int> less(1e5 + 2);
    vector<int> greater(1e5 + 2);

    // 预处理 less 数组
    for (int i = 1; i <= 1e5; ++i)
    {
        less[i] = less[i - 1] + cnt[i - 1];
    }

    // 预处理 greater 数组（注意倒序）
    for (int i = 1e5; i >= 1; --i)
    {
        greater[i] = greater[i + 1] + cnt[i + 1];
    }

    while (k--)
    {
        int d;
        cin >> d;

        cout << greater[d] << ' ' << less[d] << '\n';
    }
}

F. 612的取舍之道

难度：普及-
核心知识点：前缀和、滑动窗口（逆向思维）

思路解析

这也是一道容易陷入 DP 陷阱的思维题。
采取 逆向思维：经历 $k$ 次操作后，我们得到了什么？
答：长度为 $n - k$ 的原数组 $a$ 的子数组。

因此，题目转化为：
1. 计算所有长度为 $n - k$ 的连续子数组的和 sub_sum。
2. 答案即为 max(sub_sum, total_sum - sub_sum)。

实现上只需要维护一个前缀和数组，或者使用滑动窗口即可。
注意：$a_i$ 的最大值可达 $10^9$，求和时务必使用 long long 以避免溢出。

AC 代码

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void solve()
{
    int n, k;
    cin >> n >> k;

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

    ll ans = 0;
    // 枚举所有长度为 n-k 的子数组
    for (int i = n - k; i <= n; ++i)
    {
        ll sum = pref_sum[i] - pref_sum[i - n + k];
        ans = max(ans, max(sum, pref_sum.back() - sum));
    }

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}

G. 我想睡觉

难度：普及/提高-
核心知识点：数学公式变形、哈希表

思路解析

此次“612杯”的主题是数学。题目要求找出满足 $|a_i - a_j - k| = i - j$ （其中 $1 \le j < i \le n$）的下标对数。
通用的解法是拆开绝对值符号分情况讨论：

  1. 当 $a_i - a_j - k \ge 0$ 时：
    • $a_i - a_j - k = i - j \implies a_i - i = a_j - j + k$
  2. 当 $a_i - a_j - k < 0$ 时：
    • $-(a_i - a_j - k) = i - j \implies a_i + i = a_j + j + k$

很容易得出两个情况是互不相交的。因此我们只需要维护两个哈希表（或数组），分别统计 $a_x - x$ 和 $a_x + x$ 的数量，遍历 $i$ 时查询对应的 $j$ 即可。

AC 代码

#include <bits/stdc++.h>

using namespace std;

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

    long long ans = 0, num;
    unordered_map<int, int> cnt_1;
    unordered_map<int, int> cnt_2;

    for (int i = 1; i <= n; ++i)
    {
        cin >> num;
        ans += cnt_1[num - i];
        ans += cnt_2[num + i];

        // 存入当前数据供后续匹配，注意公式右边是 +k
        cnt_1[num - i + k]++;
        cnt_2[num + i + k]++;
    }

    cout << ans;
}

H. 记忆的残响与约定的彼方

难度：普及/提高-
核心知识点：数论、欧拉筛、质因数分解
题目参考：https://codeforces.com/contest/2154/problem/C1

思路解析

题目要求判断是否存在一对 $gcd(a_i, a_j) > 1$（$i \ne j$）。

如果我们通过暴力的方法，对于每两个数都进行一次 gcd，那么时间复杂度为 $O(N^2)$，必然超时，因此我们不得不采用其它方法。

实际上判断是否存在一对 $gcd(a_i, a_j) > 1$ 根本没必要把每两个数都 gcd 一遍，我们可以直接将题目转换成另一个条件——存在两个数有相等的质因子。
充分性证明：存在两个数的有相等的质因子就已经保证了存在两数的最大公因数至少不为 1。

Solve 1：试除法

解法：试除法分解质因数
时间复杂度：$O(N \sqrt{M})$

我们只需要不断除去能整除这个数的质数，就可以得出它的全部质因子了。这个方法在极端数据下有可能超时，但逻辑简单，曾在第一届“612杯”的最后一题出现过。

Solve 1 代码

#include <bits/stdc++.h>

using namespace std;

void fen(int num, unordered_map<int, int>& cnt)
{
    for (int i = 2; i * i <= num; ++i)
    {
        if (num % i == 0)
        {
            cnt[i]++;
        }

        while (num % i == 0)
        {
            num /= i;
        }
    }

    if (num > 1)
    {
        cnt[num]++;
    }
}

void solve()
{
    int n;
    cin >> n;

    int num;
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; ++i)
    {
        cin >> num;
        fen(num, cnt);
    }

    for (auto& pair : cnt)
    {
        if (pair.second > 1)
        {
            cout << "YES" << '\n';
            return;
        }
    }

    cout << "NO" << '\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}

Solve 2：欧拉筛 + 预处理 (优化解)

解法：欧拉筛预处理最小质因数 (SPF)
时间复杂度：$O(M + N)$ ($M$ 为数据最大值)

这是一种优化方案。我们只需要预处理每个数字的 最小质因数 (min_prime)，然后通过查表的方式快速获取 $a_i$ 的质因子。我们发现只要有两个数存在相等的最小质因子就能保证 $gcd(a_i, a_j) > 1$，我们根本没必要处理每个质因子。

Solve 2 代码

#include <bits/stdc++.h>

using namespace std;

const int maxN = 1e6;

vector<int> primes;
vector<int> min_prime(maxN + 1);

// 欧拉筛预处理
void seive()
{
    for (int i = 2; i <= maxN; ++i)
    {
        if (min_prime[i] == 0)
        {
            min_prime[i] = i;
            primes.push_back(i);
        }

        for (int p : primes)
        {
            if (p > min_prime[i] || (long long)i * p > maxN)
            {
                break;
            }

            min_prime[i * p] = p;
        }
    }
}

void solve()
{
    int n;
    cin >> n;

    vector<bool> record(maxN + 1);
    bool ans = false;

    int num;
    for (int i = 0; i < n; ++i)
    {
        cin >> num;

        if (ans || min_prime[num] == 0)
        {
            continue;
        }

        if (record[min_prime[num]])
        {
            ans = true;
        }

        record[min_prime[num]] = true;
    }

    cout << (ans ? "YES" : "NO") << '\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    seive();

    while (t--)
    {
        solve();
    }
}

I. 染红的苍蓝

难度：普及/提高+
核心知识点：前缀和、数学推导、线性扫描
题目参考：https://codeforces.com/contest/2169/problem/C

本题的原题来自 CodeForces 平台的一道 1400 分的题目，考究数学推导并且可以不采用高级数据结构，十分契合本次 数组+数学 的主题，在开始正式讲解前，我们先讲讲它的原题吧。

原题解析

原题：给定一系列数字，我们可以选择一个区间 $[L, R]$，并让区间内的每个数变为 $(L + R)$，或不采取任何操作，求这一系列数字可能的最大和。

我们记 $P_i$ 为原数组中直到 $i$ 为止的和，因此我们对区间 $[L, R]$ 进行操作后得到的收益为：
$(R + L) \times (R - L + 1) - (P_R - P_{L - 1})$

化简后可得：
$R^2 + R - P_R - (L^2 - L - P_{L - 1})$

我们只需要统计每个区间的操作收益的最大值，并判断是否大于 0，如果是则最终的答案就是 原数组和 + 最大收益。

那么如何统计最大收益呢？其实这就是一个经典的 最大差值问题。
想要最大化 $R^2 + R - P_R - (L^2 - L - P_{L - 1})$，只需要在遍历 $R$（也就是 $i$）的过程中，记录最小的 $L^2 - L - P_{L - 1}$ 为 mn，并维护最大的 $R^2 + R - P_R - mn$ 即可。

原题代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

void solve()
{
    int n;
    cin >> n;

    vector<int> pref_sum(n + 1);
    int num;

    int minD = INT_MAX / 2;

    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> num;

        pref_sum[i] = pref_sum[i - 1] + num;
        minD = min(minD, i * i - i - pref_sum[i - 1]);

        ans = max(ans, i * i + i - pref_sum[i] - minD);
    }

    cout << ans + pref_sum.back() << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}

思路解析（本场比赛题目）

看完原题解析后，是否思路清晰了许多？

本题的限制 $k$ 其实根本无关痛痒，我们只需要把区间 $[L, R]$ (需满足 $L - k \ge 1$ 之前的逻辑，这里根据题目实际上是要求有效区间起始点至少为 $L+k$) 的贡献公式进行修正。

根据题目中必须发动一次圣剑的设定，我们将公式化为：
收益 $= (R - L) \times (R - L + 1) - P_R - P_{L - k - 1}$
(注：此处为便于代码实现的简化视角，具体 $L$ 的定义与题目描述中重构区间的关系相对应)

由于必须要进行操作，所以我们只需要统计最大的贡献，答案就是 原数组和 + 最大贡献，因此我们只需要仿照原题抄一遍代码基本就可以 AC 本题了。
核心在于维护：
mn = min(mn, i*i - i - pref_sum[i - k - 1])
ans = max(ans, i*i + i - pref_sum[i] - mn)

AC 代码

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void solve()
{
    int n, k;
    cin >> n >> k;

    int num;

    ll mn = LLONG_MAX / 2;
    vector<ll> pref_sum(n + 1);

    ll ans = LLONG_MIN / 2;
    for (int i = 1; i <= n; ++i)
    {
        cin >> num;
        pref_sum[i] = pref_sum[i - 1] + num;

        // 保证 L 至少为 1，即 i (作为R) 至少要在 L+k 的位置
        // 也就是 i >= k + 1
        if (i >= k + 1)
        {
            // 维护与 L 相关的最小项
            mn = min(mn, (ll)i * i - i - pref_sum[i - k - 1]);

            // 更新当前 i 作为右端点的最大收益
            ans = max(ans, (ll)i * i + i - pref_sum[i] - mn);
        }
    }

    cout << ans + pref_sum.back() << '\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}