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; }