题目大意:输入n个直角三角形,被第i个三角形覆盖,美观度增加,请问所有被覆盖的点中,最大美观度是多少?

暴力70分,但不开long long就只有20了。数据很水,开了long long,边加美味度边统计最大值都有70(23行放到16行之后)!

暴力做法,不需要多想:对于每个三角形,包含在里面的点全部逐个加美味度。如何判断点在直角三角形内?三角形所在正方形中的点,离直角点的曼哈顿距离不超过边长即可。

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, a, p, q, x, y, xx, yy;
long long ans, c[1005][1005];
int main(){
    scanf("%d", &n);
    while(n--){
        scanf("%d%d%d%d%d", &k, &p, &q, &m, &a);
        if(k == 1) x = p, xx = p+m, y = q, yy = q+m;
        else if(k == 2) x = p, xx = p+m, y = q-m, yy = q;
        else if(k == 3) x = p-m, xx = p, y = q, yy = q+m;
        else x = p-m, xx = p, y = q-m, yy = q;
        for(i=x; i<=xx; i++){
            for(j=y; j<=yy; j++){
                if(abs(i-p)+abs(j-q) <= m){
                    c[i][j] += a;
                }
            }
        }
    }
    for(i=1; i<=1000; i++){
        for(j=1; j<=1000; j++){
            if(c[i][j] > ans) ans = c[i][j];
        }
    }
    printf("%lld\n", ans);
    return 0;
}

逐个点统计太慢,我们可以一行一行来,如第p行第q到q+m个点加1,可以用差分标记,q位置+1(表示从这以后全部+1),q+m+1位置减1(表示从这以后全部-1),求前缀和即可得到每个点的美观度。这样的时间复杂度是100000000,竟然能过。

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, a, p, q, x, y, xx, yy;
long long ans, c[1005][1005];
int main(){
    scanf("%d", &n);
    while(n--){
        scanf("%d%d%d%d%d", &k, &p, &q, &m, &a);
        if(k == 1){
            for(i=0; i<=m; i++){
                c[p+i][q] += a, c[p+i][q+m+1-i] -= a;
            }
        }
        if(k == 2){
            for(i=0; i<=m; i++){
                c[p+i][q-m+i] += a, c[p+i][q+1] -= a;
            }
        }
        if(k == 3){
            for(i=0; i<=m; i++){
                c[p-i][q] += a, c[p-i][q+m+1-i] -= a;
            }
        }
        if(k == 4){
            for(i=0; i<=m; i++){
                c[p-i][q-m+i] += a, c[p-i][q+1] -= a;
            }
        }
    }
    for(i=1; i<=1000; i++){
        for(j=1; j<=1000; j++){
            c[i][j] += c[i][j-1];
            if(c[i][j] > ans) ans = c[i][j];
        }
    }
    printf("%lld\n", ans);
    return 0;
}

要想更保险一点,还可以对差分标记进行差分!如三角形“1 3 3 4 2”,那么需要加2的位置有:

33 34 35 36 37
43 44 45 46
53 54 55
63 64
73

差分标记:c[3][3] = 2,c[3][8] = -2、……、c[7][3] = 2、c[7][4] = -2
差分标记的开头:c[3][3]到c[7][3]都是加2,对这一列进行差分,即33处+2、83处-2;
差分标记的结尾:c[3][8]到c[7][4]都是减2,对这一斜进行差分,即38处-2、83处+2;
对于其他类型的三角形也这样对差分标记进行差分,尽量按照同一个方向:从上到下、从左到右,这样合并的时候可以只用一次顺着的循环。

#include <bits/stdc++.h>
#define N 1005
using namespace std;
int n, m, i, j, k, a, p, q;
long long ans, c[N][N], x[N][N], y[N][N], s[N][N];
int main(){
    scanf("%d", &n);
    while(n--){
        scanf("%d%d%d%d%d", &k, &p, &q, &m, &a);
        //c记录列,x记录右往左的斜,y记录左往右的斜 
        if(k == 1){
            c[p][q] += a, c[p+m+1][q] -= a;//左+1 
            x[p][q+m+1] -= a, x[p+m+1][q] += a;//斜-1 
        }
        if(k == 2){
            y[p][q-m] += a, y[p+m+1][q+1] -= a;//斜+1 
            c[p][q+1] -= a, c[p+m+1][q+1] += a;//右-1 

        }
        if(k == 3){
            c[p-m][q] += a, c[p+1][q] -= a;//左+1
            y[p-m][q+1] -= a, y[p+1][q+m+1+1] += a;//斜-1
        }
        if(k == 4){
            x[p-m][q] += a, x[p+1][q-m-1] -= a;//斜+1
            c[p-m][q+1] -= a, c[p+1][q+1] += a;//右-1
        }
    }
    for(i=1; i<=1000; i++){
        for(j=k=1; j<=1000; j++){
            c[i][j] += c[i-1][j];
            x[i][j] += x[i-1][j+1];
            y[i][j] += y[i-1][j-1]; 
            s[i][j] = c[i][j] + x[i][j] + y[i][j];//差分标记复原
            s[i][j] += s[i][j-1];//差分标记求前缀和
            if(s[i][j] > ans) ans = s[i][j];
        }
    }
    printf("%lld\n", ans);
    return 0;
}