A.能源调配

题目理解

有$n$个能量槽和$n$个能量晶体，每个晶体有一个基础能量值$a_i$。 当把晶体放入能量槽时：

• 如果放入奇数编号的能量槽$（1,3,5,...）$，能量贡献为$+a_i^2$
• 如果放入偶数编号的能量槽$（2,4,6,...）$，能量贡献为$-a_i^2$

我们可以自由安排晶体放入顺序，以最大化总能量

解题思路

为使总能量最大，我们可以：

• 让较大的数放在奇数位(贡献为正)
• 让较小的数放在偶数位(贡献为负)

这样我们可以先把数组从小到大排序，前$\frac {n}{2}$个数放在偶数位，也就是贡献值为负数；剩下的数放在奇数位，也就是贡献值为正数

标准程序代码如下(c++)

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
typedef vector<vector<int>> mat;
using pii = pair<int, int>;
using pdd = pair<double,double>;
constexpr int N = 2e5 + 10;

void solve()
{
    int n;
    cin>>n;
    vector<int> a(n+10);
    for(int i=1;i<=n;i++) cin>>a[i];
    
    sort(a.begin()+1,a.begin()+1+n);  // 从小到大排序
    
    int sum1=0,sum2=0;
    // 计算前一半（较小数）的平方和
    for(int i=1;i<=n/2;i++) sum1+=a[i]*a[i];
    // 计算后一半（较大数）的平方和
    for(int i=n/2+1;i<=n;i++) sum2+=a[i]*a[i];
    
    // 输出最大总能量：大数平方和 - 小数平方和
    cout<<sum2-sum1<<'\n';
}

signed main()
{
    IOS;
    int _= 1;
    //cin >> _;
    while(_--)
    {
        solve();
    }
    return 0;
}

B.领袖

题目理解

当$A$的频率是$B$的倍数时，$A$可以与$B$高效协作。 现在现在，我们要找“潜在领袖”。一个队员是“潜在领袖”的条件是：他的频率 $x$，必须是队伍中至少 $n-1$ 名队员（包括他自己）频率的倍数.。 换句话说，对于一个潜在领袖x，队伍里最多只能有一个队员频率不是x的倍数。而我们的任务就是满足这个条件的所有队员的编号。

解题思路

这道题的关键在于一个简单的数学事实：一个数 $x$ 如果是另一个数 $a$ 的倍数，那么 $x$ 一定大于或等于 $a$。 很显然，所以在一组数中，只有最大值和次大值才有可能成为答案，所以只要求出这一组数中的最大值和次大值这两个数，并且一次验证是否可以成为领袖即可。

标准程序代码(c++)

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

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

    // 步骤1：寻找最大值mx, 次大值submx, 和最大值的出现次数cnt
    int mx = -1, submx = -1e9, cnt = 0; // submx 初始化为一个很小的数
    for(int i = 1; i <= n; i ++)
    {
        if(a[i] > mx)
        {
            // 发现了新的最大值，旧的mx成为submx
            submx = mx;
            mx = a[i];
            cnt = 1; // 重置计数器
        }
        else if(a[i] == mx)
        {
            cnt ++; // 发现了相同的最大值，计数器加1
        }
        else 
        {
            // 当前数比mx小，但可能比submx大
            submx = max(submx, a[i]);
        }
    }

    // 步骤2：分情况讨论
    if(cnt > 1)
    {
        // 情况一：最大值不止一个，只验证mx
        int st = 0; // st 是 "statistic" 的缩写，用于统计是mx倍数的个数
        for(int i = 1; i <= n; i ++)
        {
            if(mx % a[i] == 0) st ++;
        }
        if(st < n - 1) cout << -1 << '\n'; // 验证失败
        else 
        {
            // 验证成功，输出所有频率为mx的队员编号
            for(int i = 1; i <= n; i ++)
            {
                if(a[i] == mx) cout << i << ' ';
            }
            cout << '\n';
        }
    }
    else // cnt == 1
    {
        // 情况二：最大值只有一个，需要验证mx和submx
        int st1 = 0, st2 = 0; // st1统计mx的倍数，st2统计submx的倍数
        for(int i = 1; i <= n; i ++)
        {
            if(mx % a[i] == 0) st1 ++;
            if(submx % a[i] == 0) st2 ++;
        }

        if(st1 < n - 1 and st2 < n - 1) cout << "-1\n"; // 两个候选都失败
        else 
        {
            // 至少有一个候选成功了
            for(int i = 1; i <= n; i ++)
            {
                // 如果mx是合格领袖，并且当前队员频率是mx，就输出编号
                if(st1 >= n - 1 and a[i] == mx) cout << i << ' ';
                // 如果submx是合格领袖，并且当前队员频率是submx，就输出编号
                if(st2 >= n - 1 and a[i] == submx) cout << i << ' ';
            }
            cout << '\n';
        }
    }
}

int main()
{
    cin.tie(0) -> sync_with_stdio(0);
    int T;
    for(cin >> T; T; T --) solve();
    return 0;
}

C.星际之旅

题目理解

题目要求我们在一个数组中找出满足特定条件的连续子数组（区间）的数量。这些条件是：

• 区间长度至少为3（即至少包含3个元素）
• 区间的第一个元素和最后一个元素相等
• 区间中间所有元素的和等于首尾元素的值

解题思路

1. 前缀和：使用前缀和数组可以快速计算任意区间的元素和。
2. 分组存储：使用一个map来存储每个值对应的所有位置索引。这样，我们可以快速找到所有具有相同值的位置，这些位置可能成为满足条件的区间的起点和终点。
3. 遍历检查：对于每个值，遍历其所有可能的位置组合(l, r)，检查是否满足条件：

• 确保区间长度至少为3
• 使用前缀和计算中间元素的和
• 检查中间元素的和是否等于首尾元素

标准程序代码(c++)

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
typedef vector<vector<int>> mat;
using pii = pair<int, int>;
using pdd = pair<double,double>;
constexpr int N = 2e5 + 10;

void solve()
{
    int n;
    cin>>n;
    vector<int> a(n+10),pre(n+10);  // a存储原数组，pre存储前缀和
    map<int,vector<int>> mp;  // map用于存储每个值对应的所有位置索引
    //map的键（key）的类型是int，存的是每一个出现的数;值（value）的类型是vector<int>存的是这个数出现过的位置
    // 读取数组元素，构建前缀和数组，并填充map
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];  // 读取第i个元素
        mp[a[i]].push_back(i);  // 将位置i添加到值a[i]对应的索引列表中
        pre[i]=pre[i-1]+a[i];  // 计算前缀和：pre[i] = 前i-1个元素的和 + 第i个元素
    }
    
    int ans=0;  // 答案计数器
    
    // 遍历map中的每个值及其对应的位置列表
    for(auto &[x,vis] :mp)  // x是值，vis是该值对应的位置索引列表
    {
        // 遍历所有可能的位置组合(l, r)
        for(int i=0;i<vis.size();i++)  // i表示起点在vis列表中的索引
        {
            for(int j=i+1;j<vis.size();j++)  // j表示终点在vis列表中的索引
            {
                // 检查区间长度是否至少为3
                if(vis[j]-vis[i]+1<3) continue;  // 如果长度小于3，跳过
                else 
                {
                    // 计算中间元素的和：pre[vis[j]-1] - pre[vis[i]]
                    // vis[j]-1是终点前一个位置，vis[i]是起点位置
                    int sum=pre[vis[j]-1]-pre[vis[i]];
                    
                    // 检查中间元素的和是否等于首尾元素
                    if(sum==a[vis[i]]) ans++;  // 如果相等，答案计数器加1
                } 
            }
        }
    }
    
    cout<<ans<<'\n';  // 输出答案
}

signed main()
{
    IOS;  // 加速输入输出
    int _= 1;
    //cin >> _;  // 如果有多组测试数据，取消注释
    while(_--)
    {
        solve();  // 调用解题函数
    }
    return 0;
}

D.Orange的和谐乐章

题目理解

这道题要求我们找出序列中所有连续子数组（子序列）的个数，这些子数组的总能量值能够被给定的 "和谐频率"$k$ 整除。 具体来说，给定一个长度为 $n$ 的整数序列 $a$ 和一个整数 $k$，我们需要计算有多少个连续子数组 $a [i...j]$（其中 $0≤i≤j<n$）满足：$(a [i] + a [i+1] + ... + a [j]) \% k == 0$。

解题思路

• 核心原理：子数组 $a [i...j]$ 的和等于 $pre [j] - pre [i-1]$。如果这个差值能被 $k$ 整除，即 $(pre [j] - pre [i-1]) \% k == 0，那么 pre [j] \% k == pre [i-1] \% k$
• 运用map：记录每个余数出现的次数。遍历数组时，对于当前前缀和的余数，若之前出现过相同余数，则说明这两个位置之间的子数组和能被 $k$ 整除
• 处理负余数：由于数组元素可以是负数，计算出的余数可能为负，通过 $(pre [i]\% k + k) \% k$ 的方式将其标准化到 $[0, k-1]$ 范围内

标准程序代码(c++)

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

// 优化输入输出速度
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

// 使用long long避免整数溢出
#define int long long

// 定义一些常用数据类型别名（本题未直接使用，但属于良好编程习惯）
typedef vector<vector<int>> mat;
using pii = pair<int, int>;
using pdd = pair<double,double>;

// 定义数组最大长度（本题未直接使用，但属于良好编程习惯）
constexpr int N = 2e5 + 10;

// 解题函数
void solve()
{
    int n, k;
    cin >> n >> k;  // 读取序列长度n和和谐频率k
    
    // a数组存储音符能量值，pre数组存储前缀和
    vector<int> a(n+10), pre(n+10);
    
    // 哈希表mp用于记录每个余数出现的次数
    map<int, int> mp;
    
    // ans用于累计满足条件的子数组个数
    int ans = 0;
    
    // 初始化：前缀和为0的情况（即子数组从第一个元素开始）
    mp[0] = 1;
    
    // 遍历整个序列，计算前缀和并统计满足条件的子数组
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];  // 读取当前音符的能量值
        
        // 计算前缀和：前i个元素的总和
        pre[i] = pre[i-1] + a[i];
        
        // 计算当前前缀和除以k的余数，并确保为非负数
        int md = (pre[i] % k + k) % k;
        
        // 如果之前出现过相同的余数，说明中间的子数组和能被k整除
        if(mp.count(md)) 
            ans += mp[md];
        
        // 更新当前余数的出现次数
        mp[md]++;
    }
    
    // 输出结果
    cout << ans << '\n';
}

// 主函数
signed main()
{
    IOS;  // 启用输入输出优化
    
    int _ = 1;  // 控制测试用例数量，本题默认为1
    // cin >> _;  // 如需多测试用例可取消注释
    
    // 处理所有测试用例
    while(_--)
    {
        solve();
    }
    
    return 0;
}