SYNU 四月周赛 Round II 暨2026蓝桥杯模拟赛题解

A. 消灭逆序对

考虑每次交换a，b：

• a=b：不改变逆序对
• a<b: 逆序对+1
• a>b：逆序对-1

对于任何一个非严格升序的序列，可以知道逆序对总是存在的

因此每次操作最多减少一个逆序对，最多减少k个，如果k还没用完序列已经有序，则答案为0.

因此答案为：$max(逆序对数量-k, 0)$

求逆序对可以用归并排序或者树状数组。

代码由ai生成

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 归并排序求逆序对
long long mergeSort(vector<int>& a, int l, int r, vector<int>& tmp) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    long long ans = mergeSort(a, l, mid, tmp) + mergeSort(a, mid + 1, r, tmp);
    
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            // a[i] > a[j]，说明 a[i] 到 a[mid] 都与 a[j] 构成逆序对
            ans += (mid - i + 1);
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    
    // 将临时数组中的元素拷贝回原数组
    for (int i = l; i <= r; ++i) {
        a[i] = tmp[i];
    }
    return ans;
}

int main() {
    // 优化输入输出速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long k;
    if (!(cin >> n >> k)) return 0;

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

    vector<int> tmp(n);
    // 计算初始序列的逆序对数量 I
    long long inversions = mergeSort(a, 0, n - 1, tmp);

    // 计算最小逆序对数量
    long long ans = max(0LL, inversions - k);
    cout << ans << "\n";

    return 0;
}

B. 推箱子

题目要求最大化“最小值”，这是经典的最大最小化问题。

题目要求最大化：$\min\limits_{1 \le i \le n} \max(p_{f(i)} - w_i, 0)$，其中 $f(i)$ 是分配给箱子 $i$ 的弹簧编号。

最大化 $\max(p_j - w_i, 0)$ 的最小值，等价于先最大化 $p_j - w_i$ 的最小值，接下来分两步考虑如何最大化 $\min (p_{f(i)} - w_i)$：

我们有 $m$ 个弹簧，但只有 $n$ 个箱子，因此需要舍弃 $m - n$ 个弹簧。为了让每个箱子弹得尽量远，显然应该舍弃弹力最小的 $m - n$ 个弹簧，选择弹力最大的前 $n$ 个弹簧。

第二步：箱子和弹簧的匹配（排序不等式）

现在我们有了 $n$ 个箱子（重量 $w$）和 $n$ 个最强的弹簧（弹力 $p$），如何匹配才能使 $\min(p_i - w_i)$ 最大？

结论：将箱子重量降序排列，弹簧弹力降序排列，然后一一对应匹配（即最重的箱子配最强的弹簧，第二重的配第二强的，以此类推）。

因此只需要将前n大的弹簧匹配前n大的箱子即可。

把 $w$ 和 $p$ 序列都从大到小排序，然后取前 $n$ 个 $p_i-w_i$ 的最小值即可。

代码由 ai 生成

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 优化输入输出流，提升 cin/cout 速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<int> w(n);
    vector<int> p(m);

    for (int i = 0; i < n; ++i) cin >> w[i];
    for (int i = 0; i < m; ++i) cin >> p[i];

    // 1. 将箱子重量降序排列
    sort(w.begin(), w.end(), greater<int>());

    // 2. 将弹簧弹力降序排列
    sort(p.begin(), p.end(), greater<int>());

    // 3. 贪心匹配：用最强的 n 个弹簧与 n 个箱子一一对应，计算最小差值
    // 注意：最坏情况下 p[i] - w[i] 可能为负数，最小可达 1 - 10^9，
    // 超出了 int 的下界，因此 min_diff 需要使用 long long
    long long min_diff = 2e9; 
    for (int i = 0; i < n; ++i) {
        long long diff = (long long)p[i] - w[i]; // 强转防溢出
        if (diff < min_diff) {
            min_diff = diff;
        }
    }

    // 4. 距离不可为负，与 0 取最大值
    long long ans = max(0LL, min_diff);
    cout << ans << "\n";

    return 0;
}

C. 幸运数

考虑到n非常大，因此肯定无法一个个枚举+check。

由于k非常小，不妨考虑构造答案。

用dfs每次往后面加数即可，记录当前数位和和当前构造出来的数，每次循环枚举0到9。如果构造出来的数大于n则return，或者数位和超过k则return。

注意：一些写法可能会爆longlong，可以看看下面代码的注释

代码由ai生成

#include <iostream>
using namespace std;

long long N;
int K;
long long ans;

// 纯构造 DFS
void dfs(long long current_num, int current_sum) {
    // 尝试在当前数字末尾追加 0 到 9
    for (int d = 0; d <= 9; d++) {
        // 剪枝1：数位和超过K。因为是升序枚举，后面的更大，直接 break
        if (current_sum + d > K) break;
        
        // 剪枝2：超过N。变形为 current_num > (N - d) / 10 防止乘10溢出 long long！
        if (current_num > (N - d) / 10) break;
        
        // 通过所有检查，这是一个合法数字
        long long next_num = current_num * 10 + d;
        ans++;
        dfs(next_num, current_sum + d);
    }
}

int main() {
    // 优化输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    if (!(cin >> T)) return 0;
    
    while (T--) {
        cin >> N >> K;
        
        ans = 0;
        // 从 1 开始构造
        for (int d = 1; d <= 9; d++) {
            if (d > K || d > N) break; // 特判首位
            ans++;
            dfs(d, d);
        }
        cout << ans << "\n";
    }
    
    return 0;
}

D. 两极分化

其实就是求极差不超过k的最长子区间是哪些。

不妨考虑维护一个滑动窗口 $[l, r]$，用两个单调队列分别追踪窗口内的最大值和最小值：

• 单调递减队列 maxq：队首始终是当前窗口的最大值
• 单调递增队列 minq：队首始终是当前窗口的最小值 当 $\max - \min > k$ 时，收缩左边界 $l$，直到极差重新满足条件。

当左端点 $l$ 固定时，满足条件的最右端点 $r_{\max}(l)$ 关于 $l$ 单调递增。

证明：设 $l_1 < l_2$，若 $r_{\max}(l_1) = R$，即 $[l_1, R]$ 的极差 $\le k$ 但 $[l_1, R+1]$ 的极差 $> k$。那么对于 $l_2$，区间 $[l_2, R]$ 是 $[l_1, R]$ 的子区间，极差只会更小，必然也 $\le k$。因此 $r_{\max}(l_2) \ge R$。$\square$

这个单调性保证了 $l$ 和 $r$ 都只会单调右移，总移动次数不超过 $2n$，复杂度为 $O(n)$。

当然，考虑用RMQ+二分也可以轻松通过本题。

代码由ai生成

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, k;
int a[MAXN];
int maxq[MAXN], minq[MAXN]; // 单调队列（存索引），用数组模拟比deque更快
int maxh, maxt, minh, mint;  // 队首/队尾指针
int main() {
    // ====== 快速I/O ======
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int best_len = 0;
    vector<int> best_lefts; // 记录所有最优方案的左端点(1-indexed)
    maxh = minh = 1;
    maxt = mint = 0;
    int l = 1; // 窗口左边界
    for (int r = 1; r <= n; r++) {
        // ---- 维护单调递减队列(最大值在队首) ----
        while (maxh <= maxt && a[maxq[maxt]] <= a[r])
            maxt--;
        maxq[++maxt] = r;
        // ---- 维护单调递增队列(最小值在队首) ----
        while (minh <= mint && a[minq[mint]] >= a[r])
            mint--;
        minq[++mint] = r;
        // ---- 收缩左边界直到极差 ≤ k ----
        while (a[maxq[maxh]] - a[minq[minh]] > k) {
            l++;
            // 弹出过期元素
            if (maxq[maxh] < l) maxh++;
            if (minq[minh] < l) minh++;
        }
        // ---- 更新最优答案 ----
        int len = r - l + 1;
        if (len > best_len) {
            best_len = len;
            best_lefts.clear();
            best_lefts.push_back(l);
        } else if (len == best_len) {
            best_lefts.push_back(l);
        }
    }
    // ====== 输出 ======
    cout << best_len << " " << best_lefts.size() << "\n";
    for (int left : best_lefts) {
        cout << left << " " << left + best_len - 1 << "\n";
    }
    return 0;
}

E. 追求小众

本题要求出字符串中不包含任何模式串的最长子串。

可以考虑先用KMP算法/字符串哈希先求出所有模式串在原字符串上的所有位置区间。

那么问题转化成了：在线段上存在若干禁止区间，我要选出一个区间使得该区间不包含任何完整的禁止区间（可以包含部分）。

我们把禁止区间分成左右端点l和r来考虑，对于同一个l，我们只考虑最小的r（因为包含大的肯定已经包含了小点）。

$$v[l] = \min\{r : [l, r] \text{ 是禁止区间}\}$$

不妨考虑倒序枚举：

定义：

$$R(i) = \min\{r : \text{存在禁止区间 } [l, r] \text{ 且 } l \ge i\}$$

即从位置 $i$ 及之后开始的所有禁止区间中，右端点最小的一个。

从右向左扫描时，$R(i) = \min(v[i],\ R(i+1))$。

从位置 $i$ 开始的最长合法子串右端点为：

$$f(i) = \begin{cases} R(i) - 1 & \text{if } R(i) \le |P| \\ |P| & \text{otherwise} \end{cases}$$

$R(i)$ 是从位置 $i$ 向右看，"第一个不能越过"的禁止右端点。子串必须在 $R(i)$ 之前结束才不会吞入完整的模式串。

因此一边枚举一边统计答案即可。

总复杂度: $O(n|S|)$

代码由ai生成

#include <bits/stdc++.h>
using namespace std;
// ================================================================
// KMP 匹配：在 text 中找 pattern 的所有出现位置
// 返回 1-indexed 闭区间 [l, r]，表示 text[l..r] = pattern
// ================================================================
vector<pair<int, int>> kmp_find(const string& text, const string& pattern) {
    int m = pattern.size();
    if (m == 0 || m > (int)text.size()) return {};
    // 构建失配函数 fail[i] = pattern[0..i] 的最长公共前后缀长度
    vector<int> fail(m, 0);
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && pattern[j] != pattern[i])
            j = fail[j - 1];
        if (pattern[j] == pattern[i])
            j++;
        fail[i] = j;
    }
    // 在 text 中匹配
    vector<pair<int, int>> res;
    for (int i = 0, j = 0; i < (int)text.size(); i++) {
        while (j > 0 && pattern[j] != text[i])
            j = fail[j - 1];
        if (pattern[j] == text[i])
            j++;
        if (j == m) {
            // 匹配成功：text[i-m+1 .. i] = pattern
            res.push_back({i - m + 2, i + 1}); // 转为 1-indexed 闭区间
            j = fail[j - 1];                    // 继续匹配下一个出现
        }
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string P;
    cin >> P;
    int n;
    cin >> n;
    int N = P.size();
    const int INF = N + 1; // 哨兵值，表示无禁止区间
    // v[l] = 以 l 为左端点的所有禁止区间中，最小的右端点
    vector<int> v(N + 2, INF);
    for (int i = 0; i < n; i++) {
        string S;
        cin >> S;
        for (auto [l, r] : kmp_find(P, S)) {
            v[l] = min(v[l], r); // 同一左端点取最严格的限制
        }
    }
    // 从右向左扫描
    // R = min{r : 存在禁止区间 [l, r] 且 l >= 当前位置 i}
    // 即从位置 i 向右看，最近的"不可越过"的禁止右端点
    int R = INF;
    int ans = 0;
    for (int i = N; i >= 1; i--) {
        R = min(R, v[i]);      // 加入以 i 为左端点的禁止区间
        int rightmost = (R <= N) ? R - 1 : N; // 从 i 开始最远能到达的位置
        ans = max(ans, rightmost - i + 1);
    }
    cout << ans << "\n";
    return 0;
}

F. 平方数划分

我们要找到一种2划分，使得划分出的两个子集中不存在任意两数之和为一个平方数。

也就是说，我们不妨假设平方数全集为 $P$，则对于 $x \in S_1$ 必须满足 $\forall_{p \in P} p - x \not \in S_1$。

所以我们不妨先求出那些数不能在一个集合里（互斥）。

由于元素的最大值为 $2e5$，考虑生成平方数，即 $x \rightarrow x^2$，若 $x^2 \le 2e5$，则 $x \le \sqrt{2e5} = 400左右$，这意味着平方数最多只有400个左右。

因此可以考虑对每一个平方数 $p_i$，都枚举一边原始序列 $a_j$,看看 $p_i - a_j$是否在序列中，如果在则说明其互斥。

当我们记录下所有的互斥对 $(u, v)$ 之后，由于 u 和 v 必须满足二分性，可以考虑是 u v 之间存在一条边，所有的数之间的关系就转化到了一张图 $G$ 上。当所有的互斥对同时满足时，等价于 $G$ 是一张二分图。

因此用染色法判断这张图是否是二分图即可，答案就是染色情况。

复杂度：$O(n \sqrt n)$

代码由ai生成

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int MAXA = 200005;   // a_i 上界
const int MAXN = 100005;   // n 上界

// ===== 完全平方数表 =====
int sq[700], sqCnt;

void initSquares() {
    for (long long i = 1; i * i <= 400000LL; i++)
        sq[sqCnt++] = (int)(i * i);
}

// ===== 全局状态 =====
bool inSet[MAXA];          // 元素是否在当前集合中
int  col[MAXA];            // 染色: -1=未染, 0/1=颜色
int  a[MAXN];              // 输入序列

// ===== 输出一个子集（空集输出空行） =====
void printVec(const vector<int>& v) {
    for (int i = 0; i < (int)v.size(); i++) {
        if (i) putchar(' ');
        printf("%d", v[i]);
    }
    putchar('\n');
}

int main() {
    initSquares();

    int T;
    scanf("%d", &T);

    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            inSet[a[i]] = true;
            col[a[i]]   = -1;
        }

        // ===== BFS 染色判定二分图 =====
        bool bipartite = true;
        for (int i = 0; i < n && bipartite; i++) {
            if (col[a[i]] != -1) continue;   // 已被其他连通分量染色

            col[a[i]] = 0;
            queue<int> q;
            q.push(a[i]);

            while (!q.empty() && bipartite) {
                int u = q.front(); q.pop();

                // 枚举所有完全平方数，在线计算邻居
                for (int j = 0; j < sqCnt; j++) {
                    int v = sq[j] - u;
                    if (v <= 0 || v > 200000) continue;  // 越界
                    if (v == u)               continue;  // 不考虑自环
                    if (!inSet[v])            continue;  // 不在集合中

                    if (col[v] == -1) {
                        col[v] = 1 - col[u];
                        q.push(v);
                    } else if (col[v] == col[u]) {
                        // 同色相邻 → 存在奇环 → 非二分图
                        bipartite = false;
                        break;
                    }
                }
            }
        }

        // ===== 输出 =====
        if (!bipartite) {
            puts("No");
        } else {
            vector<int> s0, s1;
            for (int i = 0; i < n; i++) {
                if (col[a[i]] == 0) s0.push_back(a[i]);
                else                s1.push_back(a[i]);
            }
            puts("Yes");
            printf("%d %d\n", (int)s0.size(), (int)s1.size());
            printVec(s0);
            printVec(s1);
        }

        // ===== 清理（只清当前用到的位置，避免 memset 全量清零） =====
        for (int i = 0; i < n; i++) {
            inSet[a[i]] = false;
            col[a[i]]   = -1;
        }
    }

    return 0;
}