牛客NOIP暑期七天营-普及组4-D火龙果画

题目大意：输入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;
}