问题 A：青蛙的跳跃轨迹

题意简述：一只青蛙初始位于坐标 0。它按照特定规律跳跃：第奇数次向右跳跃 $a$ 个单位，第偶数次向左跳跃 $b$ 个单位。求经过 $k$ 次跳跃后，青蛙的最终坐标。

算法分析：这是一个基础的数学模拟题。由于跳跃规律是固定的"右-左"循环，我们可以将每两次跳跃视为一个完整的周期。一个周期的净位移为 $a - b$。通过计算完整周期的数量以及是否剩余一次奇数跳跃，即可在 $O(1)$ 时间复杂度内得出结果。

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int tests;
    cin >> tests;
    while (tests--) {
        long long right_step, left_step, total_jumps;
        cin >> right_step >> left_step >> total_jumps;
        
        long long full_cycles = total_jumps / 2;
        long long position = full_cycles * (right_step - left_step);
        
        if (total_jumps % 2 != 0) {
            position += right_step;
        }
        
        cout << position << "\n";
    }
    return 0;
}

问题 B：消除特定子串

题意简述：给定一个长度为 $n$ 的 01 数组。你可以将任意位置的 1 修改为 0。目标是消除数组中所有的 101 连续子串，求最少的修改次数。

算法分析：采用贪心策略。从左到右遍历数组，当检测到 101 模式时，为了最大化消除效果并避免影响前面的已处理部分，最优选择是将该模式右侧的 1 修改为 0。这样不仅能破坏当前的 101，还能防止它与后续的 01 组合成新的 101。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<int> bits(n);
    for (int i = 0; i < n; ++i) {
        cin >> bits[i];
    }
    
    int operations = 0;
    for (int i = 1; i < n - 1; ++i) {
        if (bits[i] == 0 && bits[i - 1] == 1 && bits[i + 1] == 1) {
            operations++;
            bits[i + 1] = 0; 
        }
    }
    
    cout << operations << "\n";
    return 0;
}

问题 C：数组元素剔除与等和判定

题意简述：给定一个包含 $n$ 个整数的数组，要求找出所有满足以下条件的位置：删除该位置的元素后，剩余元素中存在一个数，其值恰好等于剩余其他所有元素之和。

算法分析：常规思路可能会使用线段树来维护区间和与最大值，但这会导致较高的常数和时间复杂度。实际上，可以通过 $O(n)$ 的数学方法优化。我们只需预先计算出数组的总和，并记录数组中的最大值和次大值。当尝试删除第 $i$ 个元素时，剩余元素的总和为 total_sum - arr[i]。如果 arr[i] 是原数组的最大值，则剩余元素的最大值为次大值；否则，剩余元素的最大值仍为原最大值。最后只需判断 剩余总和 - 剩余最大值 == 剩余最大值 是否成立即可。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<long long> arr(n);
    long long total_sum = 0;
    long long max1 = -1, max2 = -1;
    int max1_idx = -1;
    
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        total_sum += arr[i];
        if (arr[i] > max1) {
            max2 = max1;
            max1 = arr[i];
            max1_idx = i;
        } else if (arr[i] > max2) {
            max2 = arr[i];
        }
    }
    
    vector<int> valid_indices;
    for (int i = 0; i < n; ++i) {
        long long current_sum = total_sum - arr[i];
        long long current_max = (i == max1_idx) ? max2 : max1;
        if (current_sum - current_max == current_max) {
            valid_indices.push_back(i + 1);
        }
    }
    
    cout << valid_indices.size() << "\n";
    for (int idx : valid_indices) {
        cout << idx << " ";
    }
    cout << "\n";
    return 0;
}

问题 D：构造最高频序列

题意简述：给定一个长度为 $n$ 的数组，要求从中挑选 $k$ 个元素构成一个序列（元素无需连续），使得该序列在原数组中作为子序列出现的次数最多。输出这个最优序列。

算法分析：序列出现的次数受限于其中出现频率最低的元素的频次。因此，问题转化为：寻找一个频次 $x$，使得数组中频次大于等于 $x$ 的元素个数（按 $\lfloor \frac{freq}{x} \rfloor$ 计算）总和至少为 $k$。我们可以先统计所有元素的出现频率，然后使用二分查找来确定最大的合法频次 $x$。

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, k;
    cin >> n >> k;
    map<int, int> freq;
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        freq[val]++;
    }
    
    int left = 1, right = n, best_freq = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int count = 0;
        for (auto const& [num, f] : freq) {
            count += f / mid;
        }
        if (count >= k) {
            best_freq = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    int printed = 0;
    for (auto const& [num, f] : freq) {
        int times = f / best_freq;
        for (int i = 0; i < times && printed < k; ++i) {
            cout << num << " ";
            printed++;
        }
    }
    cout << "\n";
    return 0;
}

问题 E：比赛题目分配策略

题意简述：有 $n$ 道题目，部分题目难度相同。需要将这些题目分配到若干场比赛中，满足：1. 每场比赛内的题目必须完全相同；2. 不同比赛的题目不能相同；3. 后一场比赛的题目数量必须是前一场的两倍。求能够使用的最大题目总数。

算法分析：首先统计每种题目的可用数量，并将这些数量排序。由于数据范围限制，我们可以直接枚举第一场比赛所需的题目数量 start。对于每个 start，利用贪心思想，在排序后的频次数组中依次寻找满足当前所需数量的题目，并将所需数量翻倍，累加使用的题目总数，最终取所有枚举情况下的最大值。

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        counts[val]++;
    }
    
    vector<int> freqs;
    for (auto const& [num, f] : counts) {
        freqs.push_back(f);
    }
    sort(freqs.begin(), freqs.end());
    
    long long max_problems = 0;
    int max_possible_start = freqs.back();
    
    for (int start = 1; start <= max_possible_start; ++start) {
        long long current_sum = 0;
        int required = start;
        for (int f : freqs) {
            if (f >= required) {
                current_sum += required;
                required *= 2;
            }
        }
        max_problems = max(max_problems, current_sum);
    }
    
    cout << max_problems << "\n";
    return 0;
}

问题 F：带距离限制的子序列最大和

题意简述：给定一个长度为 $n$ 的数组，要求选择恰好 $x$ 个元素，使得它们的和最大。限制条件是：任意两个被选中的元素在原数组中的下标距离不能大于 $k$（即下标差 $\le k$），且首尾元素也需满足相应的边界距离限制。

算法分析：这是一个典型的动态规划问题。定义状态 $dp[i][j]$ 表示从前 $i$ 个元素中选择 $j$ 个元素，且第 $j$ 个元素为 $a[i]$ 时的最大和。状态转移方程为 $dp[i][j] = \max_{i-k \le t < i} \{dp[t][j-1]\} + a[i]$。
对于基础版本（F1），数据规模较小，可以直接使用三层循环暴力求解。但对于进阶版本（F2），$n$ 和 $x$ 的规模增大，暴力 DP 会超时。此时需要引入单调队列优化。通过为每个选择数量 $j$ 维护一个单调递减的双端队列（Deque），可以在 $O(1)$ 均摊时间内获取滑动窗口 $[i-k, i-1]$ 内的最大 $dp$ 值，从而将整体时间复杂度优化至 $O(n \cdot x)$。

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

const long long NEG_INF = -1e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, k, x;
    cin >> n >> k >> x;
    
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    
    vector<deque<pair<long long, int>>> dq(x + 1);
    vector<long long> dp(x + 1, NEG_INF);
    
    dp[0] = 0;
    dq[0].push_back({0, 0});
    
    long long max_sum = -1;
    
    for (int i = 1; i <= n; ++i) {
        vector<long long> current_dp(x + 1, NEG_INF);
        
        for (int j = 1; j <= min(i, x); ++j) {
            while (!dq[j - 1].empty() && dq[j - 1].front().second < i - k) {
                dq[j - 1].pop_front();
            }
            
            if (!dq[j - 1].empty()) {
                long long best_prev = dq[j - 1].front().first;
                current_dp[j] = best_prev + a[i];
                
                if (n - i < k && j == x) { 
                    max_sum = max(max_sum, current_dp[j]);
                }
            }
        }
        
        for (int j = 1; j <= min(i, x); ++j) {
            if (current_dp[j] != NEG_INF) {
                while (!dq[j].empty() && dq[j].back().first <= current_dp[j]) {
                    dq[j].pop_back();
                }
                dq[j].push_back({current_dp[j], i});
            }
        }
    }
    
    cout << max_sum << "\n";
    return 0;
}