车的攻击
(https://www.luogu.com.cn/problem/P3913)
题目可能讲得有点复杂,简化一下:就是这个n*n的格子里边所有车子能走的格子数,(注意:重复走的不算)
再看一下数据范围,明显不能直接遍历了,那么就是加减乘除的方式了。
细想一下题目我们不难发现只要将车子没走过的格子统计了,再用总的格子数去减就收工了,那么问题来了,如果有不同的车子在同一行同一列的话只能算作一个车子 -->第一想到的是标记,毫无例外普通的标记会直接MLE的1e9的内存不管你用再小的类型,始终会爆掉125兆。
换个思路,我们去存每个车子的位置,再排一下序(由于车子是直线行走的,所以排序不会影响)相同位置的跳过,直到读到不同的数字就+1,就ok了
要注意一定要用long long不然会Wa的很难看
Acode
ll n,k; cin >> n >> k;
vector<ll> vex(k+1),vey(k+1);
ll countx = 0,county = 0;
for (int i = 1; i <= k; i++) {
ll x,y;cin >> x >> y;
vex[i] = x,vey[i] = y;
}
sort(vex.begin(),vex.end());
sort(vey.begin(),vey.end());
for (int i = 1; i <= k; i++) {
if(vey[i] == vey[i+1])continue;
else county++;
}
for (int i = 1; i <= k; i++) {
if(vex[i] == vex[i+1])continue;
else countx++;
}
ll sh = n - countx;
ll ans1 = sh*n - sh * county;
ll ans = n*n - ans1;
cout << ans << endl;
标签:车子,格子,ll,vex,vey,match,mistake
From: https://www.cnblogs.com/TFOREVERY/p/17061765.html