L1-087 机工士姆斯塔迪奥

链接:题目详情 - L1-087 机工士姆斯塔迪奥 (pintia.cn)

思路:

一开始就使用了数学规律做这题,就是 如果攻击了h行,那就少 h * m个格子,如果攻击了l列,那就少了 l * n个格子,同时,行列重合的格子数为 h * l 个,还要再加上它。故而,在被攻击后,安全的格子数为 n * m - h * m - l * n + h * l 个。

这题被卡的地方就是可能会重复攻击某一行或列,所以要对行列加上标记,避免重复计算。

#include<iostream>
using namespace std;
bool hb[100010]={false},lb[100010]={false};
int main(){
    int h=0,l=0,n,m,q,x,y,z;
    cin>>n>>m>>q;
    for(int i=0;i<q;i++){
        cin>>x>>y;
        if(x==0){
            if(!hb[y]){
                hb[y]=true;
                h++;
            }
        }
        else{
            if(!lb[y]){
                lb[y]=true;
                l++;
            }
        }
    }
    z=n*m-h*m-l*n+h*l;
    cout<<z;
}