L3-041 影响力 - java

题目解析

求每个国家影响全球所有国家所需要付出的代价。

每个国家的代价为 $C_{AB} = S_A \times \sum{dist(A, B)}, dist(A, B) = max(|i_A - i_B|, |j_A - j_B|)$

解题思路

emmmmmmm

其实这道题目和坐标轴很相似，求范围内的所有点到原点的$dist$距离即可。

那针对于范围内的所有点距离原点的$dist$距离的话，可以使用前缀和的思想快速求得。

假设当前求的是$(x, y) (1 < x < n, 1 < y < m)$ 。那么

• $(1, m)$ 就是针对于$(x, y)$ 中的第一象限中的点；

• $(n, m)$ 就是针对于$(x, y)$ 中的第二象限中的点；

• $(n, 1)$ 就是针对于$(x, y)$ 中的第三象限中的点；

• $(1, 1)$就是针对于$(x, y)$ 中的第四象限中的点；

那么就需要求 $\sum dist ( (x, y), \begin{Bmatrix} (1, y) & (1, m) \\ (x, y) & (x, m) \end{Bmatrix} ) + \sum dist ( (x, y), \begin{Bmatrix} (x, y) & (x, m) \\ (n, y) & (n, m) \end{Bmatrix} ) + \sum dist ( (x, y), \begin{Bmatrix} (x, 1) & (x, y) \\ (n, 1) & (n, y) \end{Bmatrix} ) + \sum dist ( (x, y), \begin{Bmatrix} (1, 1) & (1, y) \\ (x, 1) & (x, y) \end{Bmatrix} )$ , 但是也可以发现关于以 $(x, y)$ 的坐标轴上重复计算了一边，那么只需要将其减去即可。

那么可以发现关于这些点来说，可以发现

• $\sum dist ( (x, y), \begin{Bmatrix} (1, y) & (1, m) \\ (x, y) & (x, m) \end{Bmatrix} ) = \sum dist( (1, 1), \begin{Bmatrix} (1, 1) & (1, m - y + 1) \\ (x, 1) & (x, m - y + 1) \end{Bmatrix} )$
• $\sum dist ( (x, y), \begin{Bmatrix} (x, y) & (x, m) \\ (n, y) & (n, m) \end{Bmatrix} ) = \sum dist( (1, 1), \begin{Bmatrix} (1, 1) & (1, m - y + 1) \\ (n - x + 1, 1) & (n - x + 1, m - y + 1) \end{Bmatrix} )$
• $\sum dist ( (x, y), \begin{Bmatrix} (x, 1) & (x, y) \\ (n, 1) & (n, y) \end{Bmatrix} ) = \sum dist( (1, 1), \begin{Bmatrix} (1, 1) & (1, y) \\ (n - x + 1, 1) & (n - x + 1, y) \end{Bmatrix} )$
• $\sum dist ( (x, y), \begin{Bmatrix} (1, 1) & (1, y) \\ (x, 1) & (x, y) \end{Bmatrix} ) = \sum dist ( (x, y), \begin{Bmatrix} (1, 1) & (1, y) \\ (x, 1) & (x, y) \end{Bmatrix} )$

（注：这道题目我Java代码超时了。对于我写的C++代码来说这道都需要快读实现，这道题目Java不超时的办法暂时还没想到）

代码

java

import java.io.*;
import java.util.*;

public class Main 
{

    public static void main(String[] args) 
    {
        int n = sc.nextInt();
        int m = sc.nextInt();
        long[][] shu = new long[n + 10][m + 10];
        // 计算 (1, 1) 到 (i, j) 的二维前缀和
        for (int i = 1; i <= n; i++) 
        {
            for (int j = 1; j <= m; j++) 
            {
                shu[i][j] = Math.max(i - 1, j - 1); // dist( (1, 1), (i, j) )
                shu[i][j] += shu[i - 1][j] + shu[i][j - 1] - shu[i - 1][j - 1]; // 求二位前缀和
            }
        }

        for (int i = 1; i <= n; i++) 
        {
            for (int j = 1; j <= m; j++) 
            {
                long x = sc.nextInt(); // 国家A的自身实力

                long y = 0;
                y += shu[i][m - j + 1]; // 第一象限
                y += shu[n - i + 1][m - j + 1]; // 第二象限
                y += shu[n - i + 1][j]; // 第三象限
                y += shu[i][j]; // 第四象限

                y -= shu[i][1]; // (i, j) 朝上的
                y -= shu[1][m - j + 1]; // (i, j) 朝右的
                y -= shu[n - i + 1][1]; // (i, j) 朝下的
                y -= shu[1][j]; // (i, j) 朝左的

                x *= y; // 乘上国家的自身实力

                if (j != 1) out.print(" ");
                out.print(x);
            }
            out.println();
        }

        out.flush();
        out.close();
    }

    static Scanner sc = new Scanner(System.in);
    static PrintWriter out = new PrintWriter(System.out);

}

c++

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main()
{
	int n, m; scanf("%d%d", &n, &m);
	vector<vector<ll>> shu (n + 10, vector<ll>(m + 10));
	for (int i = 1; i <= n; i ++)
	{
		for (int j = 1; j <= m; j ++)
		{
			ll x = max(i - 1, j - 1);
			x += shu[i - 1][j] + shu[i][j - 1] - shu[i - 1][j - 1];
			shu[i][j] = x;
		}
	}

	for (int i = 1; i <= n; i ++)
	{
		for (int j = 1; j <= m; j ++)
		{
			ll x; scanf("%lld", &x);

			ll y = 0;
			y += shu[i][j];
			y += shu[i][m - j + 1];
			y += shu[n - i + 1][m - j + 1];
			y += shu[n - i + 1][j];

			y -= shu[i][1];
			y -= shu[1][m - j + 1];
			y -= shu[n - i + 1][1];
			y -= shu[1][j];

			x *= y;
			
			if (j != 1) printf(" ");
            printf("%lld", x);
		}
        printf("\n");
	}

	return 0;
}

前缀和

团体程序设计天梯赛-练习集-java