# BJTUOJ tower 题解(二维前缀和+代码能力+手速题)

1.原题

(考虑到阅读体验问题,决定把原题贴过来方便查看) 链接: .

描述 A国遭到了邪恶的B国的侵略。为了抵御B国的空袭,A国计划修建大量的防空炮。

然而这时一个可恶的叛徒窃取了大量机密,并潜逃到了B国,将记有防空炮详细信息的地图交给了B国的国王。

A国的地图可看作一个 n×m 个格子组成的矩阵,将A国分成 n×m 个地区。它的左上角为 (1,1) ,右下角为 (n,m) 。地图中一共有 k 个防空炮。

其中防空炮 i 位于地区 (xi,yi) ,它的攻击方向为 di ,攻击力为 ai 。

每个防空炮攻击距离为无限远,但是它只能攻击到一定的角度范围,其范围为其正对方向正负 45°。

注意,每个防空炮也可以攻击到它自己所在的格子。一个格子上可以有多个防空炮。

我们规定:

如果 di=1,炮塔正对方向向左;

如果 di=2,炮塔正对方向向上;

如果 di=3,炮塔正对方向向右;

如果 di=4,炮塔正对方向向下。

毫无疑问,你就是那个叛徒。B国的国王希望你能计算出A国每一个地区的火力值,以便重点进攻A国火力薄弱的地区。一个地区的火力值为所有能攻击到该地区的防空炮的攻击力之总和。如果你能完成这项任务,国王会给你 1000000000 % 10 元和一个气球作为奖励。

输入数据 第一行是两个整数 n 和 m (1≤n,m≤1000),表示A国的地图大小; 第二行输入一个整数 k (1≤k≤105) ,表示地图中的防空炮数量 ; 接下来 k 行,每行 4 个整数 xi,yi,di,ai (1≤xi≤n,1≤yi≤m,1≤di≤4,1≤ai≤1000),分别表示防空炮的 x,y 坐标,炮塔正对方向,炮塔的攻击力。

输出数据 输出 n 行,每行 m 个数,表示A国每一个地区的火力值。

样例输入 4 4 2 3 3 1 2 2 3 2 3 样例输出 2 3 3 3 2 2 3 0 2 2 2 0 2 2 0 0 样例说明 在 (3,3) 格子上有一个向左的炮台,在 (2,3) 格子上有一个向上的炮台。

2.题意

维护一个矩阵,求出在指定覆盖规则下每个坐标被覆盖的值。

3.思路

如果不用前缀和优化,必然超时。但是本题不能直接用前缀和,需想办法把原矩阵“旋转”45°映射到新矩阵,而后在新矩阵中求前缀和。这里我想到了八皇后问题中开一维数组维护45°斜线的技巧,于是如法炮制,开二维数组维护横纵两条45°斜线,两条斜线确定唯一交点,即为矩阵元素。 唯一需要注意的是,我们开的新数组横纵坐标范围是m+n-1(m,n为原来的列数、行数),那么这意味着新数组有一些格子在原矩阵外,是多余的,不过这部分对答案没有影响。 最后就是二维差分+前缀和了,别忘了有4个方向。

4.代码

```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1e3+10,M=2020;

int g[M][M];
int n,m,k;

inline void accelarate()
 {
          
   
    ios::sync_with_stdio(false);
    cin.tie(0);
 }

void Insert(int x1,int y1,int x2,int y2,int ad)
{
          
   
    g[x2+1][y2+1]+=ad;g[x1][y1]+=ad;g[x1][y2+1]-=ad;g[x2+1][y1]-=ad;//注意差分的写法!!

}

int main()
{
          
   
    accelarate();
    cin>>n>>m;
    m--,n--;
    cin>>k;
    while(k--)
    {
          
   
        int x,y,dir,a;
        cin>>x>>y>>dir>>a;
        x--,y--;
        int k1=x+y+1,k2=y-x,k3=y-x+n+1;
        int i=k1,j=k3;
        if(dir==2)
        {
          
   
            Insert(1,j,i,n+m-1+2,a);
        }
        else if(dir==3)
        {
          
   
            Insert(i,j,n+m-1+2,n+m-1+2,a);

        }
        else if(dir==4)
        {
          
   
            Insert(i,1,n+m-1+2,j,a);
        }
        else
        {
          
   
            Insert(1,1,i,j,a);
        }

    }
    for(int i=1;i<=n+m+1;i++)
    {
          
   
        for(int j=1;j<=n+m+1;j++)
    {
          
   
        g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];

    }
    }



    for(int i=0;i<=n;i++)
    {
          
   
        for(int j=0;j<=m;j++)
        {
          
   
            int k1=i+j+1,k2=j-i,k3=j-i+n+1;
            int x=k1,y=k3;
            printf("%d ",g[x][y]);
        }
        printf("
");
    }
}

``

5.收获

1 巩固了相关知识 二维前缀和数组:f[i][j]表示从(1,1)到(i,j)的元素和, 二维差分数组:f[i][j]表示所有(x,y),其中x>=i&&y>=j都加一个数,所以insert函数写法是:(设左下角为(x1,y1).右上角为(x2,y2))

void Insert(int x1,int y1,int x2,int y2,int ad)
{
          
   
    g[x2+1][y2+1]+=ad;g[x1][y1]+=ad;g[x1][y2+1]-=ad;g[x2+1][y1]-=ad;//注意差分的写法!!

}

而求前缀和写法是:

for(int i=1;i<=n+m+1;i++)
        for(int j=1;j<=n+m+1;j++)
        g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];

2.此题纯靠自己写挺锻炼码力,值得一做。

经验分享 程序员 微信小程序 职场和发展