2020年第十八届绍兴市少儿信息学竞赛复赛试题粉刷匠题解

Tzh2012 · 2024-08-23 21:16:14 · 题解

题解：

这一道题用传统方法很难做哦，光开二维数组就不行了，刚看到这道题时我真的很无语哦哦，所以用二维数组来存储直接out

这题的问题无非就是2个：

1.二维数组开不了。

2.二维循环用不了

到这里估计劝退了很多人了吧

so~~~该干嘛呢？？？

真相只有一个！！！

好的欢迎回来。

开启思维环节。

因为n,m,k都有10^6

所以我们只能开一个1~k的循环（如下）

for(int i=1;i<=k;i++){
}

在这个循环内操作 （输入部分我就不讲了）

废话太多！！！

emm我们可以用逆向思维 这样就不会局限了

so ~~你知道了吗？？

for（int i=k;i>=1;i--){
}

倒着来

这样就不用考虑覆盖的问题了（但是这一行是否涂过还要看，所以要开二个标记的数组（行列））

并统计行列的个数。

设sum为蓝格总数

if->蓝色：

if->行:->y行标记，行数++，sum=sum+m-列数

if->列:->y列标记，列数++，sum=sum+n-行数

温馨提示：

用过的行列直接continue。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int x[N],y[N],z[N],vh[N],vl[N];
int main(){
    long long n,m,k,h=0,l=0;
    long long sum=0;
    scanf("%ld%ld%ld",&n,&m,&k);
    for(int i=1;i<=k;i++){
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
    }
    for(int i=k;i>=1;i--){
        if(x[i]==0&&vh[y[i]]==1) continue;
        if(x[i]==1&&vl[y[i]]==1) continue;//用过了 
        if(z[i]==0){//红色 
            if(x[i]==0){//行
                h++;//行增加
                vh[y[i]]=1;//标记
            }else if(x[i]==1){
                l++;//列
                vl[y[i]]=1; 
            }
        }else{//蓝色
            if(x[i]==0){
                h++;
                vh[y[i]]=1;
                sum=sum+m-l;
            }else if(x[i]==1){
                l++;
                vl[y[i]]=1;
                sum=sum+n-h;
            }
        }
    }
    printf("%ld",sum);
    return 0;
}