天梯赛编程题 L3-041 影响力 题解

天梯赛编程题 L3-041 影响力 题解

题面如下：

根据题面和简单的逻辑思维可以很快想出一种题解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int n, m;
cin >> n >> m;

vector<vector<ll>> grid(n, vector<ll>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
}
}

for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
ll current_strength = grid[i][j];
ll total_cost = 0;

for (int k = 0; k < n; ++k) {
for (int l = 0; l < m; ++l) {
if (i == k && j == l) continue;

int dist = max(abs(i – k), abs(j – l));

total_cost += current_strength * dist;
}
}

cout << total_cost << (j == m – 1 ? "" : " ");
}
cout << "\\n";
}

return 0;
}

此题解非常易于理解 但是时间复杂度达到了O（(nm)²)
在算法比赛中一定会TLE
所以接下来我们需要思考一种时间复杂度更低的算法
最简单的暴力算法降低时间复杂度的方式就是前缀和与差分!

算法思路：高效计算影响力总代价

1. 问题建模

核心公式

一个国家 $A$ 影响另一个国家 $B$ 的代价定义为：
$$C_{AB}=S_A\times dist(A,B)$$

其中，距离 $dist(A,B)$ 为切比雪夫距离（Chebyshev distance）：
$$dist(A,B)=\max (|i_A-i_B|，|j_A-j_B|)$$
这里 $(i_A,j_A)$ 和 $(i_B,j_B)$ 分别是国家 $A$ 和国家 $B$ 在矩阵中的行号和列号（从 1 开始）。

目标函数

对于矩阵中的每一个位置 $(i,j)$，我们需要计算它对所有其他位置 $(k,l)$ 的影响代价之和：
$$TotalCos{t}_{(i,j)}=\sum _{(k,l)\ne (i,j)}{C}_{(i,j)(k,l)}=\sum _{(k,l)\ne (i,j)}{S}_{(i,j)}\times dist((i,j),(k,l))$$

提取公因子 $S_{(i,j)}$：
$$TotalCos{t}_{(i,j)}=S_{(i,j)}\times \underset{D_{(i,j)}}{\sum _{(k,l)\ne (i,j)}dist((i,j),(k,l))}$$

关键结论：问题的核心转化为高效计算任意点 $(i,j)$ 到矩阵中所有其他点的距离之和 $D_{(i,j)}$。最终答案即为 $S_{(i,j)}\times D_{(i,j)}$。

2. 复杂度分析与优化方向

• 暴力解法：直接对每个点遍历整个矩阵计算距离和。
  • 时间复杂度：$O((nm{)}^2)$。
  • 瓶颈：若 $n=1000,m=1000$，运算次数达 $10^{12}$，必然超时（TLE）。
• 优化目标：利用数学性质将单次计算复杂度降至 $O(1)$，使总复杂度降为 $O(nm)$。

3. 数学推导与前缀和思想

区域分解

对于固定点 $(r,c)$，总距离和可以分解为四个象限区域的贡献：
$$\sum _{i=1}^n\sum _{j=1}^m\max (|r-i|，|c-j|)$$

由于对称性，我们只需解决一个通用子问题：计算矩形区域 $\sum \max (x,y)$ 的和。

以右下方区域为例（即 $i\ge r,j\ge c$）：
令 $x=i-r$, $y=j-c$，则需计算：
$$\sum _{x=0}^X\sum _{y=0}^Y\max (x,y)$$
其中 $X=n-r$, $Y=m-c$。

分类讨论

将求和区域分为两部分：

通过等差数列求和公式推导，可得闭合形式解。

4. 核心函数 calc_sum(X, Y)

定义函数 calc_sum(X, Y) 用于计算 ${\sum }_{x=0}^X{\sum }_{y=0}^Y\max (x,y)$。

计算公式

假设 $X\ge Y$（若 $X<Y$，利用对称性交换参数）：

$$\begin{array}{rl}\text{calc\_sum}(X,Y)& =\frac{Y\cdot (Y+1)\cdot (3X-Y+1)}{6}\\ & +\frac{(X-Y)\cdot (X-Y+1)\cdot (2X+Y+2)}{6}\end{array}$$

• 第一项：对应 $y>x$ 部分及 $x\ge y$ 中 $x\le Y$ 部分的贡献。
• 第二项：对应 $x\ge y$ 中 $x>Y$ 部分的贡献。

5. 最终算法流程

对于矩阵中任意点 $(r,c)$，其总距离和 $D_{(r,c)}$ 由四个方向的 calc_sum 累加得到：

$$D_{(r,c)}=calc\_sum(r-1,c-1)+calc\_sum(r-1,m-c)+calc\_sum(n-r,c-1)+calc\_sum(n-r,m-c)$$

其中：

• $calc\_sum(r-1,c-1)$ → 左上区域
• $calc\_sum(r-1,m-c)$ → 右上区域
• $calc\_sum(n-r,c-1)$ → 左下区域
• $calc\_sum(n-r,m-c)$ → 右下区域

复杂度总结

• 单次查询：$O(1)$（仅涉及常数次算术运算）。
• 总时间复杂度：$O(nm)$（遍历矩阵每个点一次）。
• 空间复杂度：$O(1)$（若不存储输入矩阵）或 $O(nm)$（存储输入）。

该算法完全满足 $nm\le 10^6$ 的数据规模限制。

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

using namespace std;

typedef long long ll;

ll calc_sum(ll X, ll Y) {
if (X < 0 || Y < 0) return 0;
if (X < Y) swap(X, Y);

ll term1 = Y * (Y + 1) * (3 * X – Y + 1) / 6;

ll term2 = (X – Y) * (X – Y + 1) * (2 * X + Y + 2) / 6;

return term1 + term2;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int n, m;
if (!(cin >> n >> m)) return 0;

vector<vector<ll>> grid(n, vector<ll>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
}
}

for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {

ll dist_sum = 0;

dist_sum += calc_sum(i – 1, j – 1);

dist_sum += calc_sum(i – 1, m – 1 – j);

dist_sum += calc_sum(n – 1 – i, j – 1);

dist_sum += calc_sum(n – 1 – i, m – 1 – j);

ll total_cost = grid[i][j] * dist_sum;

cout << total_cost << (j == m – 1 ? "" : " ");
}
cout << "\\n";
}

return 0;
}