洛谷——P3913 车的攻击
2024-09-26 08:49:01
P3913 车的攻击
题目描述
N \times NN×N 的国际象棋棋盘上有KK 个车,第ii个车位于第R_iRi行,第C_iCi 列。求至少被一个车攻击的格子数量。
车可以攻击所有同一行或者同一列的地方。
输入输出格式
输入格式:
第1 行,2 个整数N,KN,K。
接下来K 行,每行2 个整数R_i,C_iRi,Ci。
输出格式:
1 个整数,表示被攻击的格子数量。
输入输出样例
说明
• 对于30% 的数据,1 \le N \le 10^3; 1 \le K \le 10^31≤N≤103;1≤K≤103;
• 对于60% 的数据,1 \le N \le 10^6; 1 \le K \le 10^61≤N≤106;1≤K≤106;
• 对于100% 的数据,1 \le N \le 10^9; 1 \le K \le 10^6; 1 \le R_i , C_i \le N1≤N≤109;1≤K≤106;1≤Ri,Ci≤N。
我们看下面的一个例题
因为有些格子会重复计算,所以我们需要去掉重复的小道。
具体如图:(图有点丑……)
图中第二列重复了,所以我们只算一条。行中算两行,所以剩下的面积(蓝色区域)面积就是(3-2)*(3-1)=2(3−2)∗(3−1)=2,
所以被车攻击的面积就是3*3-2=73∗3−2=7。
所以我们计算的公式就是n*n-(n-r)*(n-c)n∗n−(n−r)∗(n−c)(可以展开消元,但没必要)
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 1001000 using namespace std; int n,k,sx,sy,x[N],y[N]; long long ans; int read() { ,f=; char ch=getchar(); ;ch=getchar();} +ch-',ch=getchar(); return x*f; } int main() { n=read(),k=read(); ;i<=k;i++) x[i]=read(),y[i]=read(); sort(x+,x++k),sort(y+,y++k); ;i<=k;i++) { ]) sx++; ]) sy++; } ans=1ll*n*n-1ll*(n-sx)*(n-sy); printf("%lld",ans); ; }
最新文章
- 渗透技术--SQL注入写一句话木马原理
- Vmware player 12
- webstorm与SAE的svn仓库链接进行版本控制
- 【英语】Bingo口语笔记(20) - i长短音
- 1009-2的N次方
- [转载]mongoDB学习笔记——存取图片(C#)
- 英文Ubuntu下Emacs 使用 ibus 五笔
- EasyUI easyui-combobox 重复发送请求
- 中国本土管理咨询公司排名TOP50
- Perl入门(四)Perl的正則表達式
- MySQL 性能优化神器 Explain 使用分析
- DotNetCore跨平台~问题~NETCoreAPP, Version=v1.0&#39; compatible with one of the target runtimes: &#39;win10-x64
- 【学习】js学习笔记:数组(一)
- wpf C# 数据库 c/s 个人信息管理 wpf局域网通信
- RocketMq发送消息出现com.alibaba.rocketmq.client.exception.MQBrokerException: CODE: 2 DESC: [TIMEOUT_CLEAN_QUEUE]broker busy, start flow control for a while, period in queue: 201ms, size of queue: 1
- GLSL ES 中的存储变量修饰符(const/attribute/uniform/varying/in/centroid in/out/centroid out)
- day 09
- 学习下知然网友写的taskqueue
- hibernate事务规范写法
- 九校模拟——餐馆(restaurant)