2025“釘耙編程”中國大學(xué)生算法設(shè)計暑期聯(lián)賽_3 1012
發(fā)現(xiàn)AI題解寫得比我清晰易懂多得多，嗚嗚嗚
好的，我結(jié)合你的代碼和提供的思路，幫你詳細梳理這道題的思維過程，講得盡量規(guī)范和清晰，適合新手理解。可以一步步跟著思考，掌握關(guān)鍵點。
題目簡述
你有 n 個能量核心，每個核心有坐標 \((x_i, y_i)\) 和能量強度 \(a_i\)。
對任意一對核心 i 和 j，會產(chǎn)生共振能量：
\( f_{i,j} = (a_i + a_j) \times \max(|x_i - x_j|, |y_i - y_j|) \)
我們需要計算所有不同對的共振能量之和（包括 i=j 時也算，但 i=j 的能量為 0），即：
\( Ans = \sum_{1 \le i < j \le n} f_{i,j} \)
并對答案取模 \(10^9 + 7\)。
主要難點
- \(n\) 最多可達 2×10^5，所有詢問中 $ \sum n \le 10^6 $。
- 直接兩兩枚舉計算，會超時（O(n2) 時間復(fù)雜度不可接受）。
- 如何用數(shù)學(xué)方法和數(shù)據(jù)結(jié)構(gòu)優(yōu)化計算。
關(guān)鍵觀察和轉(zhuǎn)化
- max 距離的特殊性
函數(shù)中的距離是以 max（最大值）為度量：
\( d(i,j) = \max(|x_i - x_j|, |y_i - y_j|) \)
這實際上是 L∞范數(shù)距離，不是歐幾里得距離。
L∞ 距離，也被稱為切比雪夫距離，是在多維空間中定義的距離度量，表示兩個點在任意一個坐標軸上的最大差值。
- 把 L∞ 距離轉(zhuǎn)成對坐標的操作
一個比較經(jīng)典的技巧是：
定義
\( u = x + y, \quad v = x - y \)
有一個結(jié)論：
\( \max(|x_i - x_j|, |y_i - y_j|) = \frac{|u_i - u_j| + |v_i - v_j|}{2} \)
為什么？
- \(u_i - u_j = (x_i - x_j) + (y_i - y_j)\)
- \(v_i - v_j = (x_i - x_j) - (y_i - y_j)\)
取絕對值后，兩個表達式的和除以 2，恰好等于 L∞ 距離。
這個變換讓問題變得更容易拆分，因為絕對值的結(jié)構(gòu)更簡單。
目標轉(zhuǎn)化
將目標表達式寫成：
\( Ans = \sum_{i<j} (a_i + a_j) \cdot \max(|x_i - x_j|, |y_i - y_j|) = \sum_{i<j} (a_i + a_j) \cdot \frac{|u_i - u_j| + |v_i - v_j|}{2} \)
拆開：
\( Ans = \frac{1}{2} \left( \sum_{i<j} (a_i + a_j) |u_i - u_j| + \sum_{i<j} (a_i + a_j) |v_i - v_j| \right) \)
關(guān)鍵問題變成：
計算下面兩個和：
\( S_u = \sum_{i<j} (a_i + a_j) |u_i - u_j| \)
\( S_v = \sum_{i<j} (a_i + a_j) |v_i - v_j| \)
如何快速計算 \(\sum_{i<j} (a_i + a_j) |coord_i - coord_j|\) ？
這里的 \(coord\) 指代 \(u\) 或 \(v\)。
思考絕對值拆分
先排序所有點，使坐標遞增：
\( coord_1 \le coord_2 \le \cdots \le coord_n \)
對于 \(i < j\):
\( |coord_j - coord_i| = coord_j - coord_i \)
因為 \(coord_j \ge coord_i\)，絕對值去掉了。
將和拆成兩部分
\( S = \sum_{i<j} (a_i + a_j)(coord_j - coord_i) \)
展開：
\( S = \sum_{i<j} a_i (coord_j - coord_i) + \sum_{i<j} a_j (coord_j - coord_i) \)
換順序為：
\( S = \sum_j \sum_{i<j} a_i (coord_j - coord_i) + \sum_j \sum_{i<j} a_j (coord_j - coord_i) \)
其中，第二部分注意 \(a_j\) 不依賴 \(i\)，可以寫成：
\( \sum_j a_j \sum_{i<j} (coord_j - coord_i) = \sum_j a_j (j \cdot coord_j - \sum_{i<j} coord_i) \)
第一部分：
\( \sum_j \sum_{i<j} a_i (coord_j - coord_i) = \sum_j \left( coord_j \sum_{i<j} a_i - \sum_{i<j} a_i coord_i \right) \)
計算前綴和
為了快速計算 \(\sum_{i<j} coord_i\), \(\sum_{i<j} a_i\), \(\sum_{i<j} a_i coord_i\)，我們使用前綴和數(shù)組。
分別定義：
- \(prefix\_coord_j = \sum_{i=1}^{j-1} coord_i\)
- \(prefix\_a_j = \sum_{i=1}^{j-1} a_i\)
- \(prefix\_a\_coord_j = \sum_{i=1}^{j-1} a_i \cdot coord_i\)
這樣，對每個 \(j\)：
\( term1 = a_j \times (j \times coord_j - prefix\_coord_j) \)
\( term2 = coord_j \times prefix\_a_j - prefix\_a\_coord_j \)
然后
\( S = \sum_{j=1}^n (term1 + term2) \)
最后求出答案
計算 \(S_u\) 和 \(S_v\) 后，
\( Ans = \frac{S_u + S_v}{2} \mod (10^9 + 7) \)
代碼中的具體實現(xiàn)技巧
- 先讀入所有核心，計算 u 和 v。
- 分別排序 u 和 v 序列。
- 用前綴和方法計算 \(S_u\) 和 \(S_v\)。
- 注意取模和大數(shù)溢出問題。
- 計算答案，輸出。
詳細代碼注釋版講解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
// 結(jié)構(gòu)體保存坐標與能量
struct Core {
ll coord; // u 或 v 坐標
ll a; // 能量強度
};
// 計算 S = sum_{i<j} (a_i + a_j)*|coord_i - coord_j|
// 注意：arr 已經(jīng)按 coord 升序排列
ll computeSum(vector<Core>& arr) {
ll res = 0; // 最終結(jié)果
ll sum_coord = 0; // 前綴坐標和 ∑ coord[i], i<j
ll sum_a = 0; // 前綴能量強度和 ∑ a[i], i<j
ll sum_a_coord = 0; // 前綴 a[i]*coord[i] 和
int n = (int)arr.size();
for (int j = 0; j < n; j++) {
ll coord = arr[j].coord % MOD;
ll a = arr[j].a % MOD;
// 計算第 j 個點的貢獻
// term1 = a_j * (j*coord_j - sum_coord)
ll term1 = a * (( (ll)j * coord - sum_coord + MOD) % MOD) % MOD;
// term2 = coord_j * sum_a - sum_a_coord
ll term2 = (coord * sum_a - sum_a_coord + MOD) % MOD;
ll add = (term1 + term2) % MOD;
res = (res + add) % MOD;
// 更新前綴和
sum_coord = (sum_coord + coord) % MOD;
sum_a = (sum_a + a) % MOD;
sum_a_coord = (sum_a_coord + a * coord) % MOD;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
const ll inv2 = 500000004; // 2 的逆元 (mod MOD)
while (t--) {
int n;
cin >> n;
vector<Core> arrU(n), arrV(n);
for (int i = 0; i < n; i++) {
ll x, y, a;
cin >> x >> y >> a;
ll u = x + y;
ll v = x - y;
arrU[i] = {u, a};
arrV[i] = {v, a};
}
// 按 u 和 v 升序排序
sort(arrU.begin(), arrU.end(), [](const Core& c1, const Core& c2){
return c1.coord < c2.coord;
});
sort(arrV.begin(), arrV.end(), [](const Core& c1, const Core& c2){
return c1.coord < c2.coord;
});
ll sumU = computeSum(arrU);
ll sumV = computeSum(arrV);
// 最終答案
ll ans = (sumU + sumV) % MOD;
ans = ans * inv2 % MOD; // 除以 2 的逆元
cout << ans << "\n";
}
return 0;
}
總結(jié)
- 題目里用到了 L∞距離，我們把它轉(zhuǎn)化成 u 和 v 坐標絕對差的和，成功將問題拆成兩部分。
- 然后利用排序和前綴和，把雙重求和的復(fù)雜度降為 O(n log n) （排序）+ O(n)（求和）。
- 利用數(shù)學(xué)推導(dǎo)將 \(\sum_{i<j}(a_i + a_j)(coord_j - coord_i)\) 拆成了兩個前綴和表達式計算。
- 模運算和逆元是常見的技巧，保證答案不溢出
你可以這樣復(fù)習(xí)鞏固
- 先理解 L∞ 距離與 u, v 坐標的轉(zhuǎn)換。
- 理解為什么排序后絕對值可以去掉。
- 理解雙重求和如何拆成前綴和。
- 確認掌握代碼實現(xiàn)細節(jié)（前綴和更新，模運算）。
- 多練習(xí)類似的雙重求和化簡題目.
這樣，你就扎實掌握了本題的核心思想和做法。
浙公網(wǎng)安備 33010602011771號