A

矩形面积 = 竖线间距 × 横线间距。根据乘法分配律，所有矩形的面积总和等价于：

所有竖线两两间距之和 × 所有横线两两间距之和

两维可以分开计算。

例如对于其中一维：

$$\sum_{1\le i<j\le n} (a_j - a_i) = \sum_{k=1}^n a_k \cdot \big[(k-1) - (n-k)\big]$$

第 k 个元素作为右端点出现 $k-1$ 次（加） 作为左端点出现 $n-k$ 次（减） 净贡献就是 $a[k] × 系数$

#include <iostream>
using namespace std;

const int MOD = 1000000007;

int main()
{
    int n;
    cin >> n;

    long long sum_x = 0;
    for (int i = 1; i <= n; ++i)
    {
        long long x;
        cin >> x;
        long long tmp = (x % MOD) * ((i - 1 - (n - i)) % MOD) % MOD;
        sum_x = (sum_x + tmp) % MOD;
    }
    sum_x = (sum_x + MOD) % MOD;

    long long sum_y = 0;
    for (int i = 1; i <= n; ++i)
    {
        long long y;
        cin >> y;
        long long tmp = (y % MOD) * ((i - 1 - (n - i)) % MOD) % MOD;
        sum_y = (sum_y + tmp) % MOD;
    }
    sum_y = (sum_y + MOD) % MOD;

    cout << sum_x * sum_y % MOD << '\n';
    return 0;
}

B

直接暴力枚举删除每个元素再求最大子段和，时间复杂度无法满足 $10^5$ 数据范围。

采用前后缀预处理思想，线性时间求解：

• $left\_max[i]$：以下标 $i$ 位置结尾的最大连续子段和
• $right\_max[i]$：以下标 $i$ 位置开头的最大连续子段和

若删掉第 $i$ 个元素，合法最大子段存在三种形态

• 仅选取 $i$ 左侧区间最大子段
• 仅选取 $i$ 右侧区间最大子段
• 拼接左侧末尾最大段与右侧开头最大段

遍历所有删除位置，取全局最大值即为答案

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 1e5 + 10;
const ll INF = 1e18;

ll a[MAXN];
ll left_max[MAXN];   // 以i结尾的最大子段和
ll right_max[MAXN]; // 以i开头的最大子段和

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    // 预处理左边
    left_max[1] = a[1];
    for (int i = 2; i <= n; i++) {
        left_max[i] = max(a[i], left_max[i-1] + a[i]);
    }
    
    // 预处理右边
    right_max[n] = a[n];
    for (int i = n-1; i >= 1; i--) {
        right_max[i] = max(a[i], right_max[i+1] + a[i]);
    }
    
    // 枚举删除每一个位置
    ll ans = -INF;
    for (int i = 1; i <= n; i++) {
        ans = max({ans, right_max[i+1], left_max[i-1], left_max[i-1]+right_max[i+1]});
    }
    
    cout << ans << endl;
    return 0;
}

C

操作只能增大边权，最终统一权值 $W$ 一定不小于原图最大边权。单条边操作次数：$t_i=W-w_i$，总操作次数为所有边操作次数之和。$W$ 取值越大，总操作次数越少，优先寻找合法的最大权值。

合法性判定条件固定目标权值 W，需同时满足两条约束：

1. 节点翻转次数为偶数 每个节点参与操作的总次数必须是偶数，才能还原初始颜色。
2. 操作连通块颜色约束 仅把需要操作的边构建连通块：

• 单点连通块：无操作行为，默认合法
• 多点连通块：必须同时存在黑、白节点，全同色块无法执行操作

仅校验三个候选权值即可： $W=max(w),max(w)+1,max(w)+2$

原理：若某个较小合法值成立，则该值加 2 也一定合法，最优解必然落在最大边权相邻三个数内。

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

struct dsu {
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p = vector<int>(n);
        iota(p.begin(), p.end(), 0);
        sz = vector<int>(n, 1);
    }

    inline int get(int x) {
        if (p[x] == x) {
            return x;
        } else {
            return p[x] = get(p[x]);
        }
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return false;
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }

    inline bool same(int x, int y) {
        return (get(x) == get(y));
    }

    inline int size(int x) {
        return sz[get(x)];
    }

    inline bool root(int x) {
        return (x == get(x));
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<int> color(n);
    for (int i = 0; i < n; i++) {
        cin >> color[i];
    }
    vector<int> x(m), y(m), w(m);
    for (int i = 0; i < m; i++) {
        cin >> x[i] >> y[i] >> w[i];
        x[i]--;
        y[i]--;
    }
    long long ans = -1;
    int mx = *max_element(w.begin(), w.end());
    for (int z = mx; z <= mx + 2; z++) {
        int ok = 1;

        vector<long long> sum(n);
        for (int i = 0; i < m; i++) {
            sum[x[i]] += z - w[i];
            sum[y[i]] += z - w[i];
        }
        for (int i = 0; i < n; i++) {
            if (sum[i] % 2 == 1) {
                ok = 0;
            }
        }

        dsu d(n);
        for (int i = 0; i < m; i++) {
            if (w[i] < z) {
                d.unite(x[i], y[i]);
            }
        }
        vector<vector<int>> g(n);
        for (int i = 0; i < n; i++) {
            g[d.get(i)].emplace_back(i);
        }
        for (int i = 0; i < n; i++) {
            int black = 0, white = 0, need_ops = 0;
            for (int v : g[i]) {
                if (color[v]) {
                    black = 1;
                } else {
                    white = 1;
                }
                if (sum[v] > 0) {
                    need_ops = 1;
                }
            }
            if (need_ops) {
                if (!(black && white)) {
                    ok = 0;
                }
            }
        }
        if (ok) {
            ans = 0;
            for (int i = 0; i < m; i++) {
                ans += z - w[i];
            }
            break;
        }
    }
    cout << ans << '\n';
    
    return 0;
}

D

数据范围1：$n \le 15$（暴力枚举）

$n$ 非常小，可直接枚举所有$2^n$ 个子集，筛选出总重量不超过$W$ 的方案，记录所有方案的总价值与包含的物品。找到全局最大价值$maxv$ 后，统计每个物品是否在所有价值为$maxv$ 的方案中都出现，若不是则计算需要提升的最小价值。 复杂度$O(2^n \cdot n)$，可轻松通过前4个测试点。

---

数据范围2：$n \le 100, W \le 1000$（暴力删除+嵌套01背包）

对于每个物品$i$，暴力删除它，对剩余$n-1$ 个物品跑一次01背包，得到不选$i$ 时的最大价值$val0$：

• 若$val0 < maxv$：说明物品$i$ 本身就是所有最优方案的必选项，无需提升价值，答案为$0$；
• 若$val0 = maxv$：说明存在不选$i$ 的最优方案，需要提升其价值，使选$i$ 的方案价值超过$val0$。

该方法复杂度为$O(n^2 W)$，对于$n=100, W=1000$，总运算量约$10^8$，可通过5~8号测试点。

---

特殊情况优化

测试点9~12存在两个特殊性质，可通过贪心快速处理，无需跑完整背包：

1. 所有$w_i$ 相等：设$w_i = w$，则最多可选择$k = \lfloor W / w \rfloor$ 个物品。最优方案等价于选择价值最大的前$k$ 个物品，通过排序即可直接判断每个物品是否必选；
2. 所有$v_i$ 相等：最优方案等价于在预算内选尽可能多的物品（即优先选重量最小的物品），同样可通过排序贪心处理，快速得到答案。

---

正解：前后缀背包优化（$O(nW)$）

对于$n=500, W=10^5$ 的大数据范围，暴力删除的方法会超时，需使用前后缀背包优化，复杂度降为$O(nW)$。

核心思路

1. 前缀背包：定义$dp1[i][j]$ 表示前$i$ 个物品，在容量为$j$ 时的最大价值；
2. 后缀背包：定义$dp2[i][j]$ 表示第$i \sim n$ 个物品，在容量为$j$ 时的最大价值；
3. 全局最优：$maxv = dp1[n][W]$，即所有物品在预算$W$ 下的最大价值。

物品判断与答案计算

对每个物品 $i$，我们需要计算两个关键值：

• 不选 $i$，容量为 W 的最大价值 $f$： 枚举前 $i-1$ 个物品占用体积 $j$，后 $i+1$ 个物品占用 $W-j$： $f = \max_{0\le j\le W} \big( dp1[i-1][j] + dp2[i+1][W-j] \big)$
• 不选 $i$，容量为 $W-w_i$ 的最大价值 $g$ 枚举前 $i-1$ 个物品占用体积 $j$，后 $i+1$ 个物品占用 $W-w_i-j$： $g = \max_{0\le j\le W-w_i} \big( dp1[i-1][j] + dp2[i+1][W-w_i-j] \big)$

若 $f < maxv$： 不存在不选 $i$ 的最优方案，物品 $i$ 本身必选，答案为 0； 若 $f = maxv$： 存在不选 i 的最优方案，需要提升价值。 选 $i$ 的总价值为 $v_i + g$，最小提升量： $ans = maxv - (v_i + g) + 1$

该方法复杂度为$O(nW)$，对于$n=500, W=10^5$，总运算量约$5 \times 10^7$，可通过所有测试点。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1005;   // 物品数量上限
const int MAXW = 1005;   // 预算上限

int n, W;
int w[MAXN], v[MAXN];   // 1~n 存储物品
int dp1[MAXN][MAXW];    // 前缀背包：前i个物品，容量j的最大价值
int dp2[MAXN][MAXW];    // 后缀背包：i~n物品，容量j的最大价值

int main() {
    // 1. 输入
    cin >> n >> W;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i] >> v[i];
    }

    // 2. 构建 前缀背包 dp1 (前i个物品)
    memset(dp1, 0, sizeof(dp1));
    for (int i = 1; i <= n; ++i) {
        // 继承前i-1个的状态
        for (int j = 0; j <= W; ++j) dp1[i][j] = dp1[i-1][j];
        // 01背包：选第i个物品
        for (int j = w[i]; j <= W; ++j) {
            dp1[i][j] = max(dp1[i][j], dp1[i-1][j - w[i]] + v[i]);
        }
    }
    int maxv = dp1[n][W];  // 全局最大价值

    // 3. 构建 后缀背包 dp2 (i~n个物品)
    memset(dp2, 0, sizeof(dp2));
    for (int i = n; i >= 1; --i) {
        // 继承后i+1个的状态
        for (int j = 0; j <= W; ++j) dp2[i][j] = dp2[i+1][j];
        // 01背包：选第i个物品
        for (int j = w[i]; j <= W; ++j) {
            dp2[i][j] = max(dp2[i][j], dp2[i+1][j - w[i]] + v[i]);
        }
    }

    // 4. 枚举每个物品，计算答案
    for (int i = 1; i <= n; ++i) {
        // 不选物品i的最大价值
        int no_i = dp1[i-1][W] + dp2[i+1][W];
        
        if (no_i < maxv) {
            // 本身必选，增值0
            cout << 0 << endl;
            continue;
        }

        // 选物品i的情况下，剩余容量的最大价值
        int cap = W - w[i];
        int yes_i = 0;
        if (cap >= 0) {
            yes_i = dp1[i-1][cap] + dp2[i+1][cap];
        }

        // 计算最小增值
        int delta = maxv - yes_i - v[i] + 1;
        cout << max(delta, 0) << endl;
    }

    return 0;
}