前缀和算法题（区间次方和、小蓝平衡和、大石头的搬运工、最大数组和）

for(int i = 1;i <= n; ++ i)
prefix[i]= prefix[i - 1] + a[i];

#define  _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll p = 1e9 + 7;
const int N = 1e5 + 9;
ll a[6][N], prefix[6][N];
// 设置a[6]的原因:
// 由于 k 较小(1 ~ 5), 可以直接计算各个数的 1 ~ k次方
int main()
{
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n, m; cin >> n >> m;
  // 输入两个整数 n,m 
  // n 表示 a[] 数组中有 n 个元素
  for (int i = 1; i <= n; ++i)cin >> a[1][i]; 
  // 输入 n 个整数
  for (int i = 2; i <= 5; ++i)
    for (int j = 1; j <= n; ++j)
      a[i][j] = a[i - 1][j] * a[1][j] % p;
      // 求 a[]各个数的 1 ~ 5的次方和
  for (int i = 1; i <= 5; ++i)
    for (int j = 1; j <= n; ++j)
      prefix[i][j] = (prefix[i][j - 1] + a[i][j]) % p;
      // 求 a[j] 的前缀和取余
  while (m--)
  {
    int l, r, k; cin >> l >> r >> k;
    cout << (prefix[k][r] - prefix[k][l - 1] + p) % p << '\n';
    // 求数组a[]的(l, r)的和:
  }
  return 0;
}

#define  _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char s[N];
int prefix[N];
int main()
{
  cin >> s + 1;
  // 从数组s的第2个位置开始读取字符串（即跳过s[0]），这样字符串的下标就从1开始了  
  int n = strlen(s + 1);
  // 计算字符串的长度(从 s[1] 开始计算)
  for (int i = 1; i <= n; ++i)
    prefix[i] = prefix[i - 1] + (s[i] == 'L' ? 1 : -1);
  // 求各个 (1, i) 的前缀和, 如果是 'L' 则加一
  int ans = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
  // 遍历所有可能出现平衡串的串
      if (prefix[j] - prefix[i - 1] == 0)
        ans = max(ans, j - i + 1);
        // 得到最大值    
  cout << ans << '\n';
  return 0;
}

#include <bits/stdc++.h>
// 包含所有标准库
// 绝对值表达式 |x-1| + |x-2| + |x-6| + |x-13| 取最小值时，x取中位数时最小。
// 在一组石头"坐标-重量"对应的情况下，找到一个位置x，使得移动所有石头到这个位置的总成本最小（成本定义为每个石头的重量乘以其到x的距离）。
using Pair = std::pair<int, int>;
// Pair类型用来存储石头的重量和初始位置
using LL = long long; // 长整型，用来处理可能的大数字
void solve(const int& Case) {
    int n; std::cin >> n; // n是石头的数量
    std::vector<Pair> a(n); // Pair的向量，存储石头的重量和初始位置
    LL sw = 0; // sw是所有石头的总重量
    for (auto& [w, p] : a) std::cin >> w >> p, sw += w; // 输入每个石头的重量和位置，并更新总重量sw
    std::sort(a.begin(), a.end()); // 按石头的位置进行排序
    LL nw = 0; // nw是当前处理过的石头的总重量
    int x = 0; // x是使得总成本最小的位置
    // 遍历排序后的石头，寻找满足nw * 2 < sw <= nw + w * 2的x
    for (const auto& [w, p] : a) {
        if (nw * 2 < sw && sw <= (nw + w) * 2) {
            x = p; // 当前位置p是满足条件的x
            break;
        }
        nw += w; // 更新当前处理过的石头的总重量nw
    }
    LL ans = 0; // 总成本
    for (const auto& [w, p] : a) {
        ans += (LL)w * std::abs(p - x); // 计算每个石头移动到x的成本并累加到ans
    }
    std::cout << ans << '\n'; // 输出总成本
}
int main() {
    std::ios::sync_with_stdio(false); // 同步标准C++和C的流，通常可以加速输入输出
    std::cin.tie(nullptr); // 解绑cin和cout的绑定，通常可以加速输入输出
    std::cout.tie(nullptr);
    int T = 1; // 测试用例的数量，默认为1
    for (int i = 1; i <= T; ++i) solve(i); // 处理每一个测试用例
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#define x first // 简化pair中位置的访问
#define y second // 简化pair中重量的访问
using namespace std;
typedef long long LL;
typedef pair<int, int> PII; 
// pair类型用来存储石头的重量和初始位置 
const int N = 1e5 + 10;
int n; // n, 表示石头的数量
PII q[N]; // 存储每个石头的位置和重量的数组
LL pre[N], nex[N];// 前缀和数组,后缀和数组
int main()
{
    cin >> n; // n, 表示石头的数量
    for (int i = 1; i <= n; ++i)
        cin >> q[i].y >> q[i].x;
        // 输入 重量 w 和 初始位置 p
    sort(q + 1, q + n + 1);
    // 按石头的位置进行排序
    LL s = 0; // 统计总重量
    for (int i = 1; i <= n; ++i)
    {
        pre[i] = pre[i - 1]; // 计算当前石头前的总成本
        pre[i] += s * (q[i].x - q[i - 1].x);
        // 累加前缀和
        s += q[i].y;// 更新总重量
    }
    s = 0; // 重置总重量, 用于计算后缀和
    for (int i = n; i >= 1; --i)
    {
        nex[i] = nex[i + 1]; // 计算当前石头后的总成本
        nex[i] += s * (q[i + 1].x - q[i].x);
        // 累加后缀和
        s += q[i].y;// 更新总重量
    }
    LL res = 1e18;
    for (int i = 1; i <= n; ++i)
        res = min(res, pre[i] + nex[i]);
        // 找到移动所有石头的最小总成本
    cout << res << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int t;cin >> t;
    // 输入整数 t, 表示数据组数
    while (t--) {
        int n, k;cin >> n >> k;
        // 输入 n, 表示宝石的数量
        // 输入 k, 表示规定的处理次数
        vector<ll> a(n), prefix(n + 1, 0);
        // 数组 a 用来存储每个宝石的价值
        // prefix 用来存储前缀和, 初始化为 0
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a.begin(), a.end());// 排序宝石的价值
        for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + a[i - 1];
        // 计算前缀和, 用于快速计算任意区间宝石的总价值
        ll ans = 0;int pos = 0;
        // ans 最大化宝石价值
        // pos 表示当前考虑的宝石区间的起始位置
        while (k >= 0) {
            ans = max(ans, prefix[n - k] - prefix[pos]);
            // 从剩下的宝石中选择价值最大的 n-k 个宝石
            pos += 2; // 跳过两个宝石, 因为每次处理我们都是取一对宝石
            k--;
        }
        cout << ans << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
/*
前缀和。
求出前缀和后，枚举操作一的次数，即可获得当前的答案，取 max 即可。
时间复杂度 O(n)
*/
// 排序后, 留下开的宝石一定是连续的一段
// 可以发现, 这连续的一段一共只有 k + 1 种
// 枚举删除最大的删除了多少个, 则立刻知道留下来的宝石是哪些
// 不能直接求和
// 前缀和可以解决
using LL = long long;
void solve(const int &Case) {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for (auto &x: a)std::cin >> x;
    std::sort(a.begin(), a.end());
    std::vector<LL> pre(n + 1); //注意long long 
    for (int i = 1; i <= n; i++)pre[i] = pre[i - 1] + a[i - 1]; //求前缀和
    LL ans = 0;
    for (int i = 0; i <= k; i++) { // 枚举删除最小的操作用了几次
        // 设 i = 0, 可以发现留下来的是 1 2 3 ... n - k
        // 设 i = k, 可以发现留下来的是 2 * k ... n - 1
        ans = std::max(ans, pre[n - (k - i)] - pre[2 * i]);
    }
    std::cout << ans << '\n';
}
//2 ^ 10 约等于 1000
//2 ^ 30 约等于 10^10
//计算机一秒跑 2 * 10^8
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T = 1;
    std::cin >> T;
    for (int i = 1; i <= T; i++)solve(i);
    return 0;
}