Znzryb's Blog

The 2026 ICPC Latin America Championship（2026 拉丁美洲决赛）-Gym-106416——I. Inversion Game（博弈题目要找最优策略，当然，这道题目不是这种）（奇偶性问题，一定要想办法跳脱出这个具体的数量）（贡献为 0 的部分，就把它丢掉，少即是好）（最后一个手握自由改变奇偶性机会的人，就是赢家）

Posted on 2026-03-26 Edited on 2026-04-06

题目大意

题目描述
Evelyn 和 Todd 正在进行一场游戏。游戏开始时有一个包含 $N$ 个整数的多重集合 $S$ ，以及一个初始为空的数组 $v$ 。两人轮流进行操作，每回合当前玩家从 $S$ 中选择一个元素，将其添加到数组 $v$ 的末尾，并将其从 $S$ 中移除。

当 $S$ 为空时游戏结束。此时计算数组 $v$ 中的逆序对数量（即满足 $i < j$ 且 $v_i > v_j$ 的索引对的数量）。如果逆序对数量为偶数，则 Evelyn 获胜；如果为奇数，则 Todd 获胜。

两人都充分了解游戏并采用最优策略进行。对于给定的多重集合 $S$ ，有以下四种可能的结果：

无论谁先手，Evelyn 必胜（输出 E）。
无论谁先手，Todd 必胜（输出 T）。
无论先手是谁，先手玩家必胜（输出 F）。
无论先手是谁，后手玩家必胜（输出 S）。

输入格式
第一行包含一个整数 $N$ （ $1 \le N \le 10^5$ ），表示多重集合 $S$ 中的元素数量。
第二行包含 $N$ 个整数 $S_1, S_2, \ldots, S_N$ （ $1 \le S_i \le N$ ），表示多重集合 $S$ 中的元素。

输出格式
输出一个大写字母，表示在双方最优策略下的游戏结果（E、T、F 或 S）。

样例一

输入

1
2

3
1 1 1

输出

样例一解释
无论 Evelyn 和 Todd 如何从多重集合 $\{1, 1, 1\}$ 中选择元素，最终得到的数组都将是 $[1, 1, 1]$ 。由于该数组中没有逆序对（数量为 $0$ ，是偶数），因此无论谁先手，Evelyn 都将获胜。

样例二

输入

1
2

3
3 1 2

输出

思路讲解

第 49 届 ICPC区域赛沈阳站——D. Dot Product Game

不过好像其实没什么关系。

当一个数被塞入这个 v 之中的时候，其实，其对 inv 的贡献已经确定了。

呃，不过我感觉我们的思路有点问题，我们来看看 gemini 的回答：

gemini 的回答

以下是根据您的要求对该博弈论问题进行的详细分析与解答：

题目描述 (Problem Description)

给定一个包含 $N$ 个整数的多重集合 $S$ 。Evelyn 和 Todd 轮流从中取出一个数字并追加到初始为空的数组 $v$ 的末尾。当集合 $S$ 为空时游戏结束。
如果最终数组 $v$ 中的逆序对数量为偶数，则 Evelyn 获胜；如果逆序对数量为奇数，则 Todd 获胜。假设两人均采取最优策略，请判断在给定的 $S$ 下游戏的最终结果：

E: Evelyn 必胜（不论谁先手）。
T: Todd 必胜（不论谁先手）。
F: 先手必胜（不论是 Evelyn 还是 Todd）。
S: 后手必胜（不论是 Evelyn 还是 Todd）。

解题思路 (Chosen Approach)

本题的核心在于分析“谁能在游戏末尾掌握逆序对奇偶性的选择权”。
设 $N$ 为集合的总元素数， $O$ 为集合中出现频率为奇数的数字的种类数。
当游戏进行到最后只剩下 $2$ 个元素时，如果这两个元素不相同，那么当前行动的玩家可以通过选择先放哪一个、后放哪一个，直接改变最终数组的逆序对奇偶性（相邻交换不同元素必然使逆序对数量加一或减一）。因此，谁能在剩下 $2$ 个不同元素时行动，谁就掌握了必胜的控制权。
基于此，我们可以分情况讨论：

当 $O \le 1$ 时：
集合中几乎所有元素都可以两两配对。Evelyn 的目标是使得逆序对为偶数。无论谁先行动，Evelyn 都可以采取“配对模仿策略”（即对手出什么，她只要有相同的就跟着出）。这样最终构成的数组会是由一对对相同的数字组成，而形如 $x, x, y, y$ 的数组，其逆序对总数必然是偶数。Todd 无法打破这种配对来强制创造奇数个逆序对。因此，Evelyn 必胜（输出 E****）。
当 $O \ge 2$ 时：
集合中存在足够多无法配对的元素，这意味着“控制者”总能通过合理的策略，确保在最后剩下 $2$ 个元素时它们互不相同，从而行使奇偶性选择权并赢下游戏。

如果 $N$ 为偶数：当剩下 $2$ 个元素时，恰好轮到先手行动（因为先手在剩余偶数个元素时操作）。因此先手可以控制最终的奇偶性，先手必胜（输出 F****）。
如果 $N$ 为奇数：当剩下 $2$ 个元素时，恰好轮到后手行动。因此后手可以控制最终的奇偶性，后手必胜（输出 S****）。

代码实现 (Code Implementation)

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n;
    if (!(cin >> n)) return;

    // 题目给出 S_i <= N，可以直接使用大小为 N + 1 的数组统计频率
    vector<int> freq(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        freq[x]++;
    }

    // 统计出现次数为奇数的元素种类数 O
    int odd_count = 0;
    for (int i = 1; i <= n; ++i) {
        if (freq[i] % 2 != 0) {
            odd_count++;
        }
    }

    // 根据 O 和 N 的奇偶性判断胜负
    if (odd_count <= 1) {
        cout << "E\n";
    } else if (n % 2 == 0) {
        cout << "F\n";
    } else {
        cout << "S\n";
    }
}

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

    solve();

    return 0;
}

复杂度与细节分析 (Explanation)

时间复杂度： $\mathcal{O}(N)$ 。我们只需要遍历一次长度为 $N$ 的输入数据来统计每个元素的出现次数，然后再遍历一次大小为 $N$ 的频次数组来统计奇数频次元素的种类数 $O$ 。总体时间为线性。
空间复杂度： $\mathcal{O}(N)$ 。开辟了一个大小为 $N + 1$ 的数组 freq 来存放每种数字的出现次数，内存开销极小。
边界情况处理：
- 全同元素（例如样例一的 $\{1, 1, 1\}$ ）：此时 $O = 1$ ，属于 $O \le 1$ 的情况，程序会正确输出 E。因为全同元素的逆序对只能是 $0$ （偶数）。
- 全异元素（例如样例二的 $\{3, 1, 2\}$ ）：此时 $O = 3 \ge 2$ 且 $N = 3$ （奇数），程序会正确走到最后的分支并输出 S，完美符合组合博弈推论。代码逻辑涵盖了所有离散状态，无遗漏的边界漏洞。

gpt 5.4 的回答（最终采用的）

题意
给定一个多重集合 S，两个人轮流从中取一个数，按取出的顺序拼成数组 v。
当 S 为空时，统计 v 的逆序对个数。

逆序对个数是偶数，Evelyn 赢。
逆序对个数是奇数，Todd 赢。
两个人都最优，要求判断最终属于哪一种情况：
E：Evelyn 不管先后手都赢。
T：Todd 不管先后手都赢。
F：先手赢。
S：后手赢。
核心做法
设 odd 表示“出现次数为奇数的不同数字有多少个”。
结论非常简单：
如果 odd <= 1，输出 E
如果 odd >= 2 且 odd 是偶数，输出 F
如果 odd >= 3 且 odd 是奇数，输出 S
T 这种情况不会出现。
为什么只看奇数次出现的数
如果某个值还有至少两份，那么一方取了它一份以后，另一方立刻取同样的值一份。
这两步对逆序对奇偶性的贡献是一样的，因为第二次取这个值时，比它小的剩余元素个数没有变化，所以两次贡献异或后为 0，等于完全抵消。
所以，所有“成对出现”的副本都可以看成无效，只剩下每个出现奇数次的值各保留一份。于是原问题等价于：
有 odd 个互不相同的数，每个数只出现一次，轮流取数，最后看逆序对奇偶性。
为什么答案只和 odd 的奇偶性有关
当剩下 m 个互不相同的数时，如果当前取的是第 k 小的数，那么它会和之后所有比它小的数形成逆序对，所以这一手对最终奇偶性的贡献就是 k mod 2。
于是：
m = 1 时，只能取唯一的数，贡献一定是 0，最终奇偶性固定为偶数。
m = 2 时，当前玩家可以取较小的数或较大的数，分别对应贡献 0 和 1，因此当前玩家可以直接决定最终奇偶性。
对于 m >= 3，当前玩家总能选到贡献为 0 的位置，也总能选到贡献为 1 的位置，所以“谁能决定最终奇偶性”会随着 m 每减一交替一次。
从 m = 2 开始可知：
m 为偶数时，当前玩家能决定最终奇偶性。
m 为奇数且 m >= 3 时，当前玩家不能决定，决定权在对手手里。
再映射回题目：
odd = 0 或 1：最终一定是偶数，所以输出 E
odd 为偶数且至少 2：先手能决定奇偶性，所以输出 F
odd 为奇数且至少 3：后手能决定奇偶性，所以输出 S
代码实现（C++20）

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

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

    int N;
    cin >> N;

    vector<int> parity(N + 1, 0);

    for (int i = 0; i < N; ++i) {
        int x;
        cin >> x;
        parity[x] ^= 1;  // 只关心出现次数的奇偶性
    }

    int odd = 0;
    for (int x = 1; x <= N; ++x) {
        odd += parity[x];
    }

    char ans;
    if (odd <= 1) {
        ans = 'E';
    } else if (odd % 2 == 0) {
        ans = 'F';
    } else {
        ans = 'S';
    }

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

复杂度

时间复杂度：O(N)
空间复杂度：O(N)
样例对应
样例一：

输入
3
1 1 1

输出
E

解释：只有数字 1，它出现了 3 次，所以 odd = 1，答案是 E。
样例二：

输入
3
3 1 2

输出
S

解释：三个数都只出现一次，所以 odd = 3，属于奇数且不少于 3，答案是 S。

我们发现，所有两两配对的部分，其贡献都为 0。

贡献为 0 的部分，就把它丢掉，少即是好。我们删除的部分，不仅这个贡献为 0，对于博弈论来说，他们两者的操作还是这个互为镜像的。

然后，转换成这样了，变成 0/1 的这个奇偶性游戏了，我们会发现，最后一个手握自由改变奇偶性机会的人，就是赢家。

这个是因为，无论前面怎么变化，奇偶性要么是 0，要么是 1，我如果手握这个选择，我就可以选对自己有利的，想保持就保持，想改变就改变。

我们发现，选择 S 中第一个大的数字（采用 0-based，其实也就是第二大的数字），一定可以改变奇偶，因此，我们会发现，倒数第二个操作的人，就是赢得这个游戏的人，因为其是最后一个手握自由改变奇偶性机会的人。

那么答案就非常明显了。

if (odd_freq_cnt <= 1) {
    cout << "E\n";
    return;
}
if (odd_freq_cnt % 2 == 0) {
    cout << "F\n";
}else {
    cout << "S\n";
}

AC代码

AC
https://codeforces.com/gym/106416/submission/368226851

源代码

/**
 * Problem: I. Inversion Game
 * Contest: The 2026 ICPC Latin America Championship
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106416/problem/I
 * Created: 2026-03-26 14:07:23
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> S(N + 2);
    vector<ll> freq(N + 2);
    // set<ll> st;
    for (int i = 1; i <= N; ++i) {
        cin >> S[i];
        freq[S[i]]++;
        // st.insert(S[i]);
    }
    ll odd_freq_cnt = 0;
    for (int i = 1; i <= N; ++i) {
        if (freq[i] & 1) {
            odd_freq_cnt++;
        }
    }
    // if (SZ(st) == 1) {
    //     cout << "E\n";
    //     return;
    // }
    if (odd_freq_cnt <= 1) {
        cout << "E\n";
        return;
    }
    if (odd_freq_cnt % 2 == 0) {
        cout<<"F\n";
    }else {
        cout<<"S\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase = 1; testcase <= lT; ++testcase)
    Solve();
    return 0;
}

/*

*/

心路历程（WA，TLE，MLE……）

The 2026 ICPC Latin America Championship（2026 拉丁美洲决赛）-Gym-106416——D. Dropshipping（正过来看，ddl 是 ddl，也就是截止时间，但是反过来看，ddl 是激活时间）

Posted on 2026-03-26 Edited on 2026-04-06

题目大意

一开始对题面的理解有问题，我以为他可以保留折扣机会，但是实际上不行，不能保留。

题目描述

给定 $N$ 个顾客的商品购买需求，第 $i$ 个需求对应的商品价格为偶数 $A_i$ 。

商店有一项优惠活动：每完成 $X$ 次全价购买后，下一次购买单件商品可以获得 50% 的折扣。此次打折购买不计入下一次获取折扣所需的 $X$ 次全价购买中。

你可以自由决定这 $N$ 件商品的购买顺序。但为了满足发货时间限制，第 $i$ 个需求对应的商品，必须在你的前 $i+K$ 次购买中完成。

由于顾客已经提前支付了全额费用，你通过折扣节省下来的金额即为你个人的利润。请计算并输出你能获得的最大总利润（即所有打折购买商品原价的一半的总和）。

输入格式

第一行包含三个整数 $N$ 、 $X$ 和 $K$ （ $1 \le N, X \le 2 \times 10^5$ ， $0 \le K \le 2 \times 10^5$ ），分别表示需求数量、获得折扣所需的全价购买次数，以及延迟发货的限制参数。
第二行包含 $N$ 个偶数 $A_1, A_2, \dots, A_N$ （ $2 \le A_i \le 10^9$ ），依次表示每个需求商品的价格。

输出格式

输出一个整数，表示你能获得的最大总利润。

样例 1

输入：

1 2	3 1 0 6 4 14

输出：

样例 1 解释

由于 $K=0$ ，第 $i$ 个需求必须在第 $i$ 次购买时完成。因此购买顺序被严格固定为 [6, 4, 14]。只有第二次购买（价格为 $4$ ）可以享受半价折扣，能获得的最大利润为 $4 / 2 = 2$ 。

样例 2

输入：

1 2	3 1 1 6 4 14

输出：

样例 2 解释

由于 $K=1$ ，第 $i$ 个需求必须在前 $i+1$ 次购买内完成。合法的购买顺序包括 [6, 4, 14]、[6, 14, 4]、[4, 6, 14] 以及 [14, 6, 4]。
其中，顺序 [6, 14, 4] 是最优的：在花费全价购买价格为 $6$ 的商品后，可以对价格为 $14$ 的商品使用折扣，从而获得最大利润 $14 / 2 = 7$ 。

思路讲解

gemini 的正难则反

问题描述 (Problem Description)

给定 $N$ 个顾客的商品购买需求，第 $i$ 个需求对应的商品价格为偶数 $A_i$ 。商店有折扣规则：每完成 $X$ 次全价购买后，下一次单件购买将享受半价折扣。你可以自由决定购买顺序，但为了保证发货时间，第 $i$ 个需求必须在你的前 $i+K$ 次购买内完成。通过折扣省下来的钱即为你的利润，要求计算并输出能够获得的最大总利润。

解题思路 (Chosen Approach)

这是一个带有截止时间（Deadline）限制的最优调度问题。
对于原始数组中的第 $i$ 个商品，它最迟必须在第 $i+K$ 次购买时被处理。因此，对于每个商品 $i$ ，它的有效放置区间为 $[1, \min(N, i+K)]$ 。令截止位置 $d_i = \min(N, i+K)$ 。
我们可以从后往前（从第 $N$ 次购买到第 $1$ 次购买）逆序来确定每次购买的商品：

候选池特性：当我们在决策第 $j$ 个位置放哪个商品时，所有截止位置 $d_i \ge j$ 的商品都可以放在这里。我们将这些商品加入候选池。
无差异的灵活性：对于此时存在于候选池中的任意商品，因为它们的 $d_i \ge j$ ，它们显然也满足 $d_i > j-1$ 。这意味着，候选池中的任何商品对于更早的位置（ $1$ 到 $j-1$ ）都是绝对合法的。因此，在当前位置做选择时，我们不需要担心某个商品是否必须留给前面的特定位置，它们的灵活性是完全等价的。
贪心选择：

如果当前位置 $j$ 是折扣位（即 $j \pmod{X+1} == 0$ ），为了让利润最大化，我们应该从候选池中挑出价格最大的商品用于打折。
如果当前位置 $j$ 是全价位，我们无法从该位置获得利润，为了把更高价格的商品保留给前面的折扣位，我们应该从候选池中挑出价格最小的商品消耗掉。

代码实现 (Code Implementation)

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

using namespace std;

int main() {
    // 优化标准输入输出流以提高执行速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, X, K;
    if (!(cin >> N >> X >> K)) return 0;

    // A 存储每个商品的价格
    vector<long long> A(N + 1);
    // add_at[j] 存储截止位置恰好为 j 的所有商品价格
    vector<vector<long long>> add_at(N + 1);

    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        int d_i = min(N, i + K);
        add_at[d_i].push_back(A[i]);
    }

    // pool 作为候选池，动态维护当前所有合法的可用商品价格
    multiset<long long> pool;
    long long max_profit = 0;

    // 从最后一次购买逆序推演到第一次购买
    for (int j = N; j >= 1; --j) {
        // 当时间倒退到 j 时，截止位置恰好为 j 的商品进入可用候选池
        for (long long price : add_at[j]) {
            pool.insert(price);
        }

        // 判断当前位置 j 是否为折扣位
        // 规则是 X 个全价后跟 1 个半价，所以折扣位恰好是 X+1 的倍数
        if (j % (X + 1) == 0) {
            // 折扣位：贪心选择候选池中价格最大的商品
            auto it = prev(pool.end());
            max_profit += (*it) / 2;
            pool.erase(it);
        } else {
            // 全价位：贪心选择候选池中价格最小的商品，将大数字留给前面的折扣位
            auto it = pool.begin();
            pool.erase(it);
        }
    }

    cout << max_profit << "\\n";

    return 0;
}

代码解释与复杂度分析 (Explanation of the code and its complexity analysis)

代码逻辑分析：

数据预处理：我们首先遍历所有 $N$ 个输入商品，算出每个商品的最后期限 d_i = min(N, i + K)。随后我们将这些价格通过 add_at 数组归类（类似于桶排序），以便逆序处理时能够以 $O(1)$ 的时间查找到在特定位置新解锁的商品。
贪心维护：使用 std::multiset<long long> 来作为可用商品的动态候选池。外层循环从 $N$ 倒序遍历至 $1$ 。每次到达一个新的位置 $j$ ，我们将 add_at[j] 中的元素全部加入池中。
利润计算：根据取模逻辑判断当前轮次，折扣直接加到 max_profit 中。multiset 会自动维护元素有序，使得获取最大值 (prev(pool.end())) 和最小值 (pool.begin()) 都极为高效。需要注意的是，一定要用迭代器删除（erase(it)），以防止误删同价格的其他商品。
复杂度分析：

时间复杂度 (Time Complexity): $O(N \log N)$ 。预处理划分数组只需 $O(N)$ 的时间；逆序遍历的循环一共执行 $N$ 次，在整个过程中，每个价格必定被插入到 multiset 一次，并且被删除一次。红黑树（multiset）的插入与删除操作单次耗时 $O(\log N)$ 。故总时间复杂度为 $O(N \log N)$ ，这在 $N \le 2 \times 10^5$ 且时限为 1 秒的要求下能够极速运行并通过。
空间复杂度 (Space Complexity): $O(N)$ 。使用了若干个长度为 $N+1$ 的 vector 来存储数据，同时 multiset 中最多同时存储 $N$ 个元素。总共占用的内存远低于 1024 MB 的内存限制。

呃，这个问他问的太早了。其实知道了，不能够保留这个折扣机会，那么其实倒过来看就非常 easy 的一件事情了。

为什么反向处理呢？我们不难发现，一个数，更早被处理完全没有任何问题，但是不能更晚被处理。

或者，可以这么说，正过来看，ddl 是 ddl，也就是截止时间，但是反过来看，ddl 是激活时间。

ll gen_ans(const map<ll, vector<ll> > &ddl_price, ll N, ll X) {
    ll ans = 0;
    // gen_sorted_st(ddl_price, st1);
    multiset<ll> st_small;
    multiset<ll,greater<>> st_big;
    // gen_sorted_st(ddl_price, st2);
    for (int i = N; i >= 1; --i) {
        auto it = ddl_price.find(i);
        // 有没有 ddl 是 i 的商品？我们对其进行激活
        if (it != ddl_price.end()) {
            for (auto price: it->second) {
                st_big.insert(price);
                st_small.insert(price);
            }
        }
        if (i % (X + 1) == 0) {
		        // 折扣的时候选择大的数字
            ll add=*st_big.begin();
            ans+=add/2;
            st_erase(st_small,st_big,add);
        } else {
		        // 平时抛弃小的数字
            ll add=*st_small.begin();
            st_erase(st_small,st_big,add);
        }
    }
    return ans;
}

AC代码

AC
https://codeforces.com/gym/106416/submission/368218310

源代码

/**
 * Problem: D. Dropshipping
 * Contest: The 2026 ICPC Latin America Championship
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106416/problem/D
 * Created: 2026-03-24 14:31:27
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */
map<ll, vector<ll> > gen_goods_ddl(const vector<ll> &A, ll N, ll K) {
    map<ll, vector<ll> > res;
    for (int i = 1; i <= N; ++i) {
        ll ddl = min(i + K, N);
        res[ddl].push_back(A[i]);
    }
    return res;
}

// struct Ddl_price {
//     ll ddl;
//     ll price;
// };
//
// struct Cmp1 {
//     bool operator()(const Ddl_price &a, const Ddl_price &b) const {
//         if (a.ddl != b.ddl) return a.ddl > b.ddl;
//         return a.price > b.price;
//     }
// };
//
// struct Cmp2 {
//     bool operator()(const Ddl_price &a, const Ddl_price &b) const {
//         if (a.ddl != b.ddl) return a.ddl > b.ddl;
//         return a.price < b.price;
//     }
// };
//
// void gen_sorted_st(const map<ll, vector<ll> > &ddl_price, auto &st) {
//     for (auto it = ddl_price.rbegin(); it != ddl_price.rend(); ++it) {
//         ll ddl = it->first;
//         for (auto price: it->second) {
//             st.insert({ddl, price});
//         }
//     }
// }
void st_erase(auto &st_small, auto &st_big, ll x) {
    auto its = st_small.find(x);
    st_small.erase(its);
    auto itb = st_big.find(x);
    st_big.erase(itb);
}

ll gen_ans(const map<ll, vector<ll> > &ddl_price, ll N, ll X) {
    ll ans = 0;
    // gen_sorted_st(ddl_price, st1);
    multiset<ll> st_small;
    multiset<ll,greater<>> st_big;
    // gen_sorted_st(ddl_price, st2);
    for (int i = N; i >= 1; --i) {
        auto it = ddl_price.find(i);
        if (it != ddl_price.end()) {
            for (auto price: it->second) {
                st_big.insert(price);
                st_small.insert(price);
            }
        }
        if (i % (X + 1) == 0) {
            ll add=*st_big.begin();
            ans+=add/2;
            st_erase(st_small,st_big,add);
        } else {
            ll add=*st_small.begin();
            st_erase(st_small,st_big,add);
        }
    }
    return ans;
}

void Solve() {
    ll N, X, K;
    cin >> N >> X >> K;
    vector<ll> A(N + 2);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }
    auto ddl_price = gen_goods_ddl(A, N, K);
    cout << gen_ans(ddl_price, N, X) << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase = 1; testcase <= lT; ++testcase)
    Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106416/submission/368218310

*/

心路历程（WA，TLE，MLE……）

The 2026 ICPC Latin America Championship（2026 拉丁美洲决赛）-Gym-106416——G. GATA-CAT（ATAT骨架插入式构造方法）

Posted on 2026-03-25 Edited on 2026-04-06

题目大意

题目描述
构造一个长度不超过 $500$ 且仅由大写字母 C、G、A、T 组成的非空字符串，使其满足以下两个条件：

字符串中包含恰好 $G$ 个子序列 GATA（即字符 G、A、T、A 按顺序出现，中间可以包含其他字符）。
字符串中包含恰好 $C$ 个子序列 CAT（即字符 C、A、T 按顺序出现，中间可以包含其他字符）。

输入格式
第一行包含一个整数 $Q$ （ $1 \le Q \le 1000$ ），表示询问的组数。
接下来的 $Q$ 行，每行包含两个整数 $G$ 和 $C$ （ $0 \le G, C \le 10^6$ ），分别表示所需的 GATA 子序列的数量和 CAT 子序列的数量。

输出格式
对于每组询问，输出一行满足条件的字符串（长度不超过 $500$ 且仅包含 C、G、A、T）。如果存在多个解，输出任意一个即可。题目保证在给定限制下一定有解。

样例输入与输出

样例 1：

Input:
4
1 1
2 3
18 1
2 1

Output:
GATCAT
GGCATAT
GATGGATATCAT
GGATCAT

样例 2：

Input:
5
1 0
0 1
1 1
0 0
0 0

Output:
GATAT
CAT
GATCAT
GG
GG

样例解释

对于样例 1 的第一组询问（ $G=1, C=1$ ），输出为 GATCAT：

GATA 子序列的数量为 $1$ （由第 1 个字符 G、第 2 个字符 A、第 3 个字符 T、第 5 个字符 A 组成）。
CAT 子序列的数量为 $1$ （由第 4 个字符 C、第 5 个字符 A、第 6 个字符 T 组成）。

对于样例 2 的第一组询问（ $G=1, C=0$ ），输出为 GATAT：

GATA 子序列的数量为 $1$ （由第 1 个字符 G、第 2 个字符 A、第 3 个字符 T、第 5 个字符 A 组成）。
由于字符串中完全不包含字符 C，因此 CAT 子序列的数量为 $0$ 。

思路讲解

gemini 的固定骨架式插入构造方法

题目描述

需要构造一个长度不超过 $500$ 且仅由大写字母 C、G、A、T 组成的非空字符串，要求该字符串中包含恰好 $G$ 个 GATA 子序列和恰好 $C$ 个 CAT 子序列。
输入包含多组询问（ $Q \le 1000$ ），每组询问给出 $G$ 和 $C$ （ $0 \le G, C \le 10^6$ ）。

解题思路

我们可以采用“固定骨架 + 贪心插入字符”的策略。
首先，我们构造一个由 A 和 T 交替组成的骨架字符串： $(AT)^K = \text{ATAT}\dots\text{AT}$ （共 $K$ 对）。
因为目标子序列 CAT 和 GATA 分别以唯一的字符 C 和 G 开头，且在我们的构造中，C 和 G 只会作为这两个子序列的起始字符，所以它们的贡献是完全独立且互不干扰的。
当我们在这个骨架中插入一个 C 时，它能形成的 CAT 数量仅取决于它右侧的 A 和 T。
如果我们把 C 插入到倒数第 $i$ 个 A 的前面（即其右侧恰好有 $i$ 对 AT），那么它右侧的骨架字符串本质上是 $(AT)^i$ 。
经过数学推导，在 $(AT)^i$ 中：

AT 子序列的数量为： $\text{AT}_i = \frac{i \times (i+1)}{2}$
ATA 子序列的数量为： $\text{ATA}_i = \frac{(i-1) \times i \times (i+1)}{6}$
因此，在倒数第 $i$ 个 A 前面插入一个 C，就会增加 $\text{AT}_i$ 个 CAT；同理，插入一个 G，就会增加 $\text{ATA}_i$ 个 GATA。
为了用最少的字符凑出恰好 $C$ 个 CAT 和 $G$ 个 GATA，我们可以将其转化为完全背包问题（找零钱问题）。由于 $\text{AT}_i$ 是三角形数， $\text{ATA}_i$ 是四面体数，它们的增长速度非常快，使用贪心算法（每次优先分配面值最大的数）可以极快地完成任务，且所需的“硬币”数量极少。
经过计算，当选定 $K = 130$ 时：
骨架长度为 $260$ 。
最大可用面值 $\text{AT}*{130} = 8515$ ， $\text{ATA}*{130} = 366145$ 。
凑出最大的 $10^6$ 时，最多只需要约 $120$ 个 C 和约 $10$ 个 G。
总长度最大约为 $260 + 120 + 10 = 390$ ，严格满足题目中要求的不超过 $500$ 字符的限制。

代码实现

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 用于存储骨架后缀带来的增量面值
long long AT[135];
long long ATA[135];

// 预处理所有 AT_i 和 ATA_i 的面值
void precompute() {
    for (int i = 1; i <= 130; i++) {
        AT[i] = (long long)i * (i + 1) / 2;
        ATA[i] = (long long)(i - 1) * i * (i + 1) / 6;
    }
}

void solve() {
    long long G, C;
    cin >> G >> C;

    vector<int> cnt_C(135, 0);
    vector<int> cnt_G(135, 0);

    // 贪心划分 C
    long long rem_C = C;
    for (int i = 130; i >= 1; i--) {
        if (AT[i] > 0) {
            cnt_C[i] = rem_C / AT[i];
            rem_C %= AT[i];
        }
    }

    // 贪心划分 G
    long long rem_G = G;
    for (int i = 130; i >= 1; i--) {
        if (ATA[i] > 0) {
            cnt_G[i] = rem_G / ATA[i];
            rem_G %= ATA[i];
        }
    }

    // 从左到右构造最终字符串
    // 外层循环代表剩余后缀从大到小，倒数第 i 个 A 前方插入字符
    string res = "";
    for (int i = 130; i >= 1; i--) {
        res.append(cnt_C[i], 'C'); // 插入所需数量的 C
        res.append(cnt_G[i], 'G'); // 插入所需数量的 G
        res += "AT";               // 补上骨架的一环
    }

    cout << res << "\\n";
}

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

    precompute();

    int Q;
    if (cin >> Q) {
        while (Q--) {
            solve();
        }
    }
    return 0;
}

复杂度分析与代码解释

时间复杂度：
预处理的时间复杂度为 $O(K)$ 。对于每组询问，贪心求解两个面值数组并拼装字符串的操作最多只需要遍历 $K$ 次，循环内的除法与取模均为常数时间操作，因此单次查询的时间复杂度为 $O(K)$ 。
总时间复杂度为 $O(K + Q \times K)$ ，其中 $K = 130, Q \le 1000$ ，总体运算量不到 $2 \times 10^5$ 次，能够在一瞬间通过 $1000$ 组询问。
空间复杂度：
我们只用了一维数组存储 $130$ 个计算好的面额，和输出使用的字符串等局部变量，空间复杂度为 $O(K)$ 。极低的内存占用，安全可靠。
特殊边界考虑：
当 $G = 0, C = 0$ 时，所有的余数分配都会置零。最终程序只会打印单纯由 $(AT)^{130}$ 构成的骨架，此时没有 C 也没有 G 混入其中，答案为合法字符串，长 $260$ ，完美符合题意。最大要求情况下，贪心的结果余数迅速收敛下降，确保最终总长度不会越过 $500$ 限制。

我确实也是想到了插入式的这个构造方法，但是确实没他想的这个么全。

不难发现如下规律：

我采用了过程式编程，模块化的思想，把不同的功能模块拆成了不同的函数，避免了Spaghetti Code，也就是面条代码。

我了解了一下，这个不算函数式编程，函数式编程的要求非常严格。

函数式编程的定义，以及我的代码为什么不是函数式编程（函数式编程中甚至不能使用 while 和 for 循环，用递归函数代替，有点变态了）（函数式编程最核心的思想是，就是声明的所有变量，全部都是 const 类型，即不可变）

1. 什么是函数式编程（Functional Programming, FP）？

函数式编程是一种编程范式（也就是一种编写代码的思想和风格），它将计算机运算视为数学上的函数计算，并且避免使用程序状态以及易变对象。
它的几个核心特点包括：

纯函数（Pure Functions）：给定相同的输入，永远返回相同的输出，并且没有任何“副作用”（Side Effects）。副作用是指修改了函数外部的状态，比如修改全局变量、读写文件、控制台输出等。
不可变性（Immutability）：变量一旦被创建，就不能再被修改。如果你需要改变数据，你不能修改原数据，而是要创建一个包含新数据的新副本。
避免共享状态（Avoid Shared State）：函数之间不通过共享的全局变量来传递状态，所有需要的数据都通过参数传递。
声明式编程（Declarative）：关注“做什么”（What to do），而不是“怎么做”（How to do it）。通常会大量使用 map, reduce, filter 等高阶函数，而不是使用 for 或 while 循环一步步改变状态。

2. 你的代码算函数式编程吗？

不算。 你的代码属于典型的指令式编程（Imperative Programming）和过程式编程（Procedural Programming），这也是 C++ 在算法竞赛（CP）中最常见的标准写法。
你的代码中有几个明显违背函数式编程原则的地方：

违背“无副作用”和“避免共享状态”

在你的代码中，存在全局变量：

1 2	vector<ll> at_ls, ata_ls; ll lT, testcase;

并且你的 init() 函数直接修改了这些外部的全局变量：

void init() {
    at_ls.resize(siz_AT_repeat);
    ata_ls.resize(siz_AT_repeat);
    // ...
}

在严格的函数式编程中，函数不应该修改外部环境。init 应该返回初始化好的数组，而不是修改全局变量。

违背“不可变性（Immutability）”

在 opls_insert 函数中，你使用了引用传递 &ans 来就地修改数据：

void opls_insert(vector<Ch_Num_CG> &ans, vector<ll> opls, ll offset, char cg) {
    // ...
    ans[i - offset].num_g++; // 直接修改了传入的对象
}

在函数式编程中，输入参数是不允许被修改的。标准的做法应该是把 ans 传进去，然后在函数内部生成一个新的 vector<Ch_Num_CG> 并返回。

大量使用指令式的循环状态修改

你的代码大量使用了 for 和 while 循环来一步步改变局部变量的状态。例如在 greedy_cal 中：

while (x != 0) {
    // ...
    x -= *it; // x 的状态在不断被改变
}

在函数式编程中，这种逻辑通常会用递归（Recursion）或者折叠函数（如 `std::accumulate` / `reduce`）来实现，以避免变量状态的不断变更。

总结

你的代码中确实用到了 std::partial_sum, std::upper_bound, std::sort 这些来自 <algorithm> 库的函数，它们带有一点“声明式”的味道，但整体架构上你的代码依然是基于状态突变（State Mutation）的过程式编程。
对于算法竞赛而言，你现在的写法（过程式/指令式）是绝对正确且最高效的。真正的函数式编程（如 Haskell 代码，或者在 C++ 中全程不使用非 const 变量）会带来极大的内存开销和常数级别的性能损耗，这在打 Codeforces 这种对时空常数要求极高的比赛中通常是不讨好的。

那么我这个代码更算是什么呢？

逐步求精（Stepwise Refinement）

这是由计算机科学家尼克劳斯·维尔特（Niklaus Wirth，PASCAL 语言的发明者）在 1971 年提出的。指的是将一个复杂的任务，不断分解成更小、更简单的子任务，直到这些子任务简单到可以用几行代码直接实现为止****。

我相信这个代码还是很清楚的。

vector<ll> at_ls, ata_ls;
ll siz_AT_repeat = 140;

void init() {
    at_ls.resize(siz_AT_repeat);
    ata_ls.resize(siz_AT_repeat);
    for (int i = 1; i < siz_AT_repeat; ++i) {
        at_ls[i] = i;
        ata_ls[i] = i;
    }
    // 上面是差分数组
    // 下面进行一次这个前缀和或者两次前缀和
    partial_sum(all(at_ls), at_ls.begin());
    partial_sum(all(ata_ls), ata_ls.begin());
    partial_sum(all(ata_ls), ata_ls.begin());
#ifdef LOCAL
    debug1d(ata_ls);
    debug1d(at_ls);
#endif
}

// 贪心地计算需要在哪里插入 G/C
vector<ll> greedy_cal(const vector<ll> &A, ll x) {
    vector<ll> res;
    while (x != 0) {
        auto it = upper_bound(all(A), x);
        if (it == A.begin()) {
            // #ifdef LOCAL
            //             debug(x);
            // #endif
            assert(0);
        } else {
            --it;
	          // 应该在倒数第几个 A 前插入？
            res.push_back(it - A.begin());
            x -= *it;
        }
    }
#ifdef LOCAL
    debug1d(res);
#endif
    return res;
}


struct Ch_Num_CG {
    char ch;
    ll num_g;
    ll num_c;
};

void opls_insert(vector<Ch_Num_CG> &ans, vector<ll> opls, ll offset, char cg) {
    // assert(is_sorted(all(opls),greater<>()));
    sort(all(opls), greater());
    ll cnta = 0;
    for (int i = SZ(ans) - 1; i > offset; --i) {
        if (ans[i].ch == 'A') {
            cnta++;
        }
        while (!opls.empty() && opls.back() == cnta) {
            if (cg == 'G') {
                ans[i - offset].num_g++;
            } else {
                ans[i - offset].num_c++;
            }
            opls.pop_back();
        }
    }
}

string gen_ans(const vector<Ch_Num_CG> &ans) {
    string res;
    for (auto [ch,num_g,num_c]: ans) {
        res += string(num_g, 'G');
        res += string(num_c, 'C');
        res += ch;
    }
    return res;
}

void Solve() {
    ll G, C;
    cin >> G >> C;
    vector<ll> g_opls = greedy_cal(ata_ls, G);
    vector<ll> c_opls = greedy_cal(at_ls, C);
    string s;
    vector<Ch_Num_CG> Ans;
    for (int i = 0; i < siz_AT_repeat + 5; ++i) {
        Ans.push_back({'A', 0, 0});
        Ans.push_back({'T', 0, 0});
    }
    opls_insert(Ans,g_opls,2,'G');
    opls_insert(Ans,c_opls,0,'C');
    cout << gen_ans(Ans) << "\n";
}

AC代码

AC
https://codeforces.com/gym/106416/submission/368168341

源代码

/**
 * Problem: G. GATA-CAT
 * Contest: The 2026 ICPC Latin America Championship
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106416/problem/G
 * Created: 2026-03-25 22:28:00
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */
vector<ll> at_ls, ata_ls;
ll siz_AT_repeat = 140;

void init() {
    at_ls.resize(siz_AT_repeat);
    ata_ls.resize(siz_AT_repeat);
    for (int i = 1; i < siz_AT_repeat; ++i) {
        at_ls[i] = i;
        ata_ls[i] = i;
    }
    partial_sum(all(at_ls), at_ls.begin());
    partial_sum(all(ata_ls), ata_ls.begin());
    partial_sum(all(ata_ls), ata_ls.begin());
#ifdef LOCAL
    debug1d(ata_ls);
    debug1d(at_ls);
#endif
}

vector<ll> greedy_cal(const vector<ll> &A, ll x) {
    vector<ll> res;
    while (x != 0) {
        auto it = upper_bound(all(A), x);
        if (it == A.begin()) {
            // #ifdef LOCAL
            //             debug(x);
            // #endif
            assert(0);
        } else {
            --it;
            res.push_back(it - A.begin());
            x -= *it;
        }
    }
#ifdef LOCAL
    debug1d(res);
#endif
    return res;
}


struct Ch_Num_CG {
    char ch;
    ll num_g;
    ll num_c;
};

void opls_insert(vector<Ch_Num_CG> &ans, vector<ll> opls, ll offset, char cg) {
    // assert(is_sorted(all(opls),greater<>()));
    sort(all(opls), greater());
    ll cnta = 0;
    for (int i = SZ(ans) - 1; i > offset; --i) {
        if (ans[i].ch == 'A') {
            cnta++;
        }
        while (!opls.empty() && opls.back() == cnta) {
            if (cg == 'G') {
                ans[i - offset].num_g++;
            } else {
                ans[i - offset].num_c++;
            }
            opls.pop_back();
        }
    }
}

string gen_ans(const vector<Ch_Num_CG> &ans) {
    string res;
    for (auto [ch,num_g,num_c]: ans) {
        res += string(num_g, 'G');
        res += string(num_c, 'C');
        res += ch;
    }
    return res;
}

void Solve() {
    ll G, C;
    cin >> G >> C;
    vector<ll> g_opls = greedy_cal(ata_ls, G);
    vector<ll> c_opls = greedy_cal(at_ls, C);
    string s;
    vector<Ch_Num_CG> Ans;
    for (int i = 0; i < siz_AT_repeat + 5; ++i) {
        Ans.push_back({'A', 0, 0});
        Ans.push_back({'T', 0, 0});
    }
    opls_insert(Ans,g_opls,2,'G');
    opls_insert(Ans,c_opls,0,'C');
    cout << gen_ans(Ans) << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
    init();
    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106416/submission/368168341

*/

心路历程（WA，TLE，MLE……）

The 2026 ICPC Latin America Championship（2026 拉丁美洲决赛）-Gym-106416——F. Fun with Balls（读题面，一定要把每句话都读到，你就看大写字母就完了）（其实，你会发现，虽然 n 的大小为 150，但是需要你决策的地方其实不多）

Posted on 2026-03-24 Edited on 2026-04-06

题目大意

一开始没注意到这句话，绷不住了。注意，读题面，一定要把每句话都读到，你就看大写字母就完了。

也不能怪我，这个 if 在 cf 题面上的这个位置太阴了。

题意总结

给定 $N$ 个球，以及它们被依次使用时的颜色序列 $K_1,K_2,\dots,K_N$ 。

Antonella 按如下规则逐个放球，且每一步之后都必须保持整个球堆稳定：

第一个球一定放在地面上。
之后每次加入一个新球时，这个球要么放在地面上，要么恰好放在两个球的正上方。
所有在地面上的球必须紧密排列，中间不能有空隙。
如果当前有多个合法放置位置，Antonella 一定选择最高的位置。
如果最高的位置不止一个，则她可以任选其中一个。

若若干个同色球两两之间可以通过“接触”的球一路连通，则它们构成一个同色连通块，称为一个 cluster。cluster 的大小就是其中球的个数。

题目要求你在所有可能构造出的稳定球堆中，求出：

所有颜色的所有 cluster 里，最大 cluster 的大小 的最大可能值。

也就是说，要输出 Antonella 在满足规则的前提下，最终有可能得到的最大同色连通块大小。

输入格式

第一行是整数 $N$ 。

第二行是 $N$ 个整数 $K_1,K_2,\dots,K_N$ ，表示每个球按加入顺序的颜色。

输出格式

输出一个整数，表示答案。

样例 1

Input
3
1 2 1

Output
2

解释：

先放第一个颜色为 1 的球。第二个颜色为 2 的球也只能放在地面上，可以放在第一个球左边或右边。第三个颜色为 1 的球此时会放到前两个球上方。这样最终颜色为 1 的两个球会连成一个大小为 2 的 cluster，所以答案是 2。

样例 2

Input
3
1 1 1

Output
3

解释：

三个球颜色都相同，不管具体怎么放，最终都能连成一个大小为 3 的同色 cluster，所以答案是 3。

样例 3

Input
4
1 5 5 1

Output
2

解释：

按规则逐步加入后，最大的同色连通块大小最多只能达到 2，因此答案是 2。

样例 4

Input
6
1 2 2 1 2 3

Output
3

解释：

在某种合法构造下，颜色为 2 的球可以形成一个大小为 3 的 cluster，因此答案是 3。

思路讲解

这道题目不是很想补，毕竟暴力嘛，算了。

AC代码

源代码

心路历程（WA，TLE，MLE……）

The 2026 ICPC Latin America Championship（2026 拉丁美洲决赛）-Gym-106416——A. Ants on a Ring（这种题目就是推性质）（这个环，一定要想办法化曲为直！一定要在一个地方，把环变成一条直线）

Posted on 2026-03-24 Edited on 2026-04-06

题目大意

题目描述
在一个圆上有 $N$ 只蚂蚁。圆被顺时针划分为 $L$ 个位置，编号为 $1$ 到 $L$ ，其中位置 $L$ 与位置 $1$ 相邻。
每只蚂蚁初始站在不同的位置上，并且都需要到达各自不同的目标位置。
在每一秒内，每只蚂蚁可以选择：

停留在原地。
顺时针或逆时针移动到相邻的位置。

在任何时刻（包括在两个位置之间移动的过程中），任意两只蚂蚁都不能处于同一个位置。例如，如果某只蚂蚁在某一秒内顺时针从位置 $1$ 移动到位置 $2$ ，那么在同一秒内，其他蚂蚁不能进行以下操作：

停留在位置 $2$ （这会导致两只蚂蚁在位置 $2$ 相遇）。
逆时针从位置 $3$ 移动到位置 $2$ （这会导致两只蚂蚁在位置 $2$ 相遇）。
逆时针从位置 $2$ 移动到位置 $1$ （这会导致两只蚂蚁在位置 $1$ 和位置 $2$ 之间相遇）。

你需要判断是否有可能让所有蚂蚁都到达各自的目标位置。如果可以，求出所需的最短时间（秒数）。

输入格式
第一行包含两个整数 $N$ （ $1 \le N \le 1000$ ）和 $L$ （ $1 \le L \le 10^9$ ），分别表示蚂蚁的数量和位置的总数。
第二行包含 $N$ 个互不相同的整数 $A_1, A_2, \dots, A_N$ （ $1 \le A_i \le L$ ），表示每只蚂蚁的初始位置。
第三行包含 $N$ 个互不相同的整数 $B_1, B_2, \dots, B_N$ （ $1 \le B_i \le L$ ），表示每只蚂蚁的目标位置。

输出格式
输出一行，包含一个整数，表示所有蚂蚁到达目标位置所需的最短时间。如果无论如何都无法全部到达目标位置，则输出星号 *。

样例展示与解释

样例 1
输入：

1
2
3

2 2
2 1
2 1

输出：

样例 1 解释：两只蚂蚁初始就已经在各自的目标位置上，因此需要 $0$ 秒。

样例 2
输入：

1
2
3

2 2
1 2
2 1

输出：

样例 2 解释：两只蚂蚁可以同时顺时针（或同时逆时针）移动，仅需 $1$ 秒即可到达目标位置。

样例 3
输入：

1
2
3

1 10
1
7

输出：

样例 4
输入：

1
2
3

3 5
1 3 2
5 2 4

输出：

样例 5
输入：

1
2
3

3 5
1 3 2
4 2 5

输出：

样例 5 解释：三只蚂蚁都可以选择逆时针移动，其中第二只蚂蚁需要在中途停留一秒。

思路讲解

这道题目，实际上可以 $O(n)$ 解决（忽略了快排的时间复杂度），至少我们的做法是这个时间复杂度的。

sort(all(lr_global));
for (int i = 0; i < SZ(lr_global); ++i) {
    if (lr_global[0].r > lr_global[i].r) {
        lr_global[i].r += L;
    }
}
auto check = [&]() -> bool {
    for (int i = 1; i < N; ++i) {
        if (lr_global[i].l == lr_global[i - 1].l) {
            return false;
        }
    }
    for (int i = 1; i < N; ++i) {
        if (lr_global[i].r <= lr_global[i - 1].r) {
            return false;
        }
    }
    return true;
};
if (!check()) {
    cout << "*\n";
    return;
}

核心代码就这一段，只能说化曲为直 yyds。

for (ll shift: {-1, 0, 1}) {
    ll ans = 0;
    for (auto [l,r]: lr_global) {
        ans = max(abs(l + L * shift - r), ans);
    }
    ans_global = min(ans_global, ans);
}

为什么这个代码对呢？其实在化曲为直下，一切都非常简单。

说白了，我们只要 l 的相对位置不变，r 的相对位置不变，那么就一定有解，是不是？

那么，我们知道，一个点，他切换方向，其实就是 l 在化曲为直的线段上，平移了 Len 位。如果其他点不也平移的 L 位的话，这个一定会导致错误的发生（即 l 的相对位置发生变化）！

那么我们就知道了，要切换方向，要么一起切换，要么一起不切换。

当然，你会说，这很奇怪啊，明明这个有些例子是有些点逆时针，有些点顺时针啊？其实，这个是因为为了符合我们的第一个条件，就是起始点和结束点必须都保持升序的条件，在保持这个条件的情况下，其实方向的变化是一起的。

AC代码

AC
http://codeforces.com/gym/106416/submission/368041079

源代码

/**
 * Problem: A. Ants on a Ring
 * Contest: The 2026 ICPC Latin America Championship
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106416/problem/A
 * Created: 2026-03-24 19:13:11
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */
struct L_R {
    ll l, r;

    bool operator<(const L_R &o) const {
        return l < o.l;
    }
};

void Solve() {
    ll N, L;
    cin >> N >> L;
    vector<L_R> lr_global(N);
    for (int i = 0; i < N; ++i) cin >> lr_global[i].l;
    for (int i = 0; i < N; ++i) cin >> lr_global[i].r;
    // auto lr_backup = lr_global;
    sort(all(lr_global));
    for (int i = 0; i < SZ(lr_global); ++i) {
        if (lr_global[0].r > lr_global[i].r) {
            lr_global[i].r += L;
        }
    }
    auto check = [&]() -> bool {
        for (int i = 1; i < N; ++i) {
            if (lr_global[i].l == lr_global[i - 1].l) {
                return false;
            }
        }
        for (int i = 1; i < N; ++i) {
            if (lr_global[i].r <= lr_global[i - 1].r) {
                return false;
            }
        }
        return true;
    };
    if (!check()) {
        cout << "*\n";
        return;
    }
    ll ans_global = INF;
    for (ll shift: {-1, 0, 1}) {
        ll ans = 0;
        for (auto [l,r]: lr_global) {
            ans = max(abs(l + L * shift - r), ans);
        }
        ans_global = min(ans_global, ans);
    }
    cout << ans_global << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase = 1; testcase <= lT; ++testcase)
    Solve();
    return 0;
}

/*
AC
http://codeforces.com/gym/106416/submission/368041079

*/

题目大意

思路讲解

题目描述 (Problem Description)

解题思路 (Chosen Approach)

代码实现 (Code Implementation)

复杂度与细节分析 (Explanation)

AC代码

心路历程（WA，TLE，MLE……）

题目大意

思路讲解

问题描述 (Problem Description)

解题思路 (Chosen Approach)

代码实现 (Code Implementation)

代码解释与复杂度分析 (Explanation of the code and its complexity analysis)

AC代码

心路历程（WA，TLE，MLE……）

题目大意

思路讲解

题目描述

解题思路

代码实现

复杂度分析与代码解释

1. 什么是函数式编程（Functional Programming, FP）？

2. 你的代码算函数式编程吗？

违背“无副作用”和“避免共享状态”

违背“不可变性（Immutability）”

大量使用指令式的循环状态修改

在函数式编程中，这种逻辑通常会用**递归（Recursion）**或者折叠函数（如 std::accumulate / reduce）来实现，以避免变量状态的不断变更。

总结

AC代码

心路历程（WA，TLE，MLE……）

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

在函数式编程中，这种逻辑通常会用递归（Recursion）或者折叠函数（如 `std::accumulate` / `reduce`）来实现，以避免变量状态的不断变更。