AT2145 [ABC047B] すぬけ君の塗り絵 2 イージー / Snuke's Coloring 2 (ABC Edit) 题解

lgvc · 2022-01-25 16:31:23 · 题解

方法1：

暴力枚举，时间复杂度 O(NHW)，可以通过。

方法2：

考虑对该暴力算法进行优化。

考虑如下两次操作：

3 4 1
5 5 1

第一次操作是对所有的 x<3 进行涂色，第二次操作是对所有的 x<5 进行涂色。

可以发现第一操作已经被第二次操作覆盖了，换句话说就是第一次操作做了也是白做。

于是我们就忽略掉第一次操作。

操作 2,3,4 同理。

故对于每一种操作，我们至多可以保留一组有用的操作。

最后对剩下的 4 组操作进行数学计算答案即可，时间复杂度 O(N)。

代码：

#include <bits/stdc++.h>
int a1,a2,a3,a4,W,H,N;
signed main(void) {
    scanf("%d %d %d",&W,&H,&N);
    a2=W;
    a4=H;
    for(int i=1;i<=N;i++) {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        if(c==1) {
            a1=std::max(a1,a);
        } else if(c==2) {
            a2=std::min(a2,a);          
        } else if(c==3) {
            a3=std::max(a3,b);
        } else if(c==4) {
            a4=std::min(a4,b);
        }
    }   
    if(a1>a2||a3>a4) printf("0");else printf("%d",(a2-a1)*(a4-a3));
    return 0;
}