20190829模拟赛画画画

发表于 更新于 分类于

$Problem’s$ $Website$

画画画

（因权限问题查看不了题目的同学不要打我）

根据题意直接进行模拟肯定会超时。。。

于是我们来优化，我们可以对$x$坐标进行普通的枚举，对$y$坐标进行差分。

因为等腰直角三角形的直角顶点有四种情况，所以要分类讨论

因为作者太懒了，所以请读者自行画图，我只在下文给出结论。。。

  • 写在前面：$num$，每次循环前为$0$，然后不断递增。

  • $opt = 1$

    $for$ $i$ $x$ ~ $(x + l)$

    $a[i][y]$ $+=$ $c$

    $a[i][y + l - num + 1] -= c$

-
$opt = 2$

$for$  $i$ $x$ ~ $(x + l)$

$a[i][y - l + num] += c$

$a[i][y + 1] -= c$

  • $opt = 3$

    $for$ $i$ $x$ ~ $(x - l)$

    $a[i][y] += c$

    $a[i][y + l - num + 1] -= c$

-
$opt = 4$

$for$ $i$ $x$ $(x - l)$

$a[i][y - l + num] += c$

$a[i][y + 1] -= c$

最后直接枚举，计算最大值即可。

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//Coded by dy.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
#define pc(x) putchar(x)
inline int sc() {
    int xx = 0, ff = 1; char cch = gc;
    while(!isdigit(cch)) {
        if(cch == '-') ff = -1; cch = gc;
    }
    while(isdigit(cch)) {
        xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
    }
    return xx * ff;
}
typedef long long ll;
inline void out(ll x) {
    if(x < 0)
        pc('-'), x = -x;
    if(x >= 10)
        out(x / 10);
    pc(x % 10 + '0');
}
#define re register
using std :: max;
int n;
ll ans;
ll a[1010][1010];
int main() {
    n = sc();
    for(re int i = 1; i <= n; ++i) {
        int opt = sc(), x = sc(), y = sc(), l = sc(), c =sc();
        if(opt == 1) {
            int num = 0;
            for(re int j = x; j <= x + l; ++j) {
                a[j][y] += c;
                a[j][y + l - num + 1] -= c;
                ++num;
            }
        }
        else if(opt == 2) {
            int num = 0;
            for(re int j = x; j <= x + l; ++j) {
                a[j][y - l + num] += c;
                a[j][y + 1] -= c;
                ++num;
            }
        }
        else if(opt == 3) {
            int num = 0;
            for(re int j = x; j >= x - l; --j) {
                a[j][y] += c;
                a[j][y + l - num + 1] -=c;
                ++num;
            }
        }
        else {
            int num = 0;
            for(re int j = x; j >= x - l; --j) {
                a[j][y - l + num] += c;
                a[j][y + 1] -= c;
                ++num;
            }
        }
    }
    for(re int i = 1; i <= 1000; ++i) {
        ll num = 0;
        for(re int j = 1; j <= 1000; ++j) {
            num += a[i][j];
            ans = max(ans, num);
        }
    }
    out(ans), pc('\n');
    return 0;
}

$rp++$