牛客网 - [北京信息科技大学第十一届程序设计竞赛]kotori和n皇后(set)
发布日期:2021-07-01 00:18:56
浏览次数:3
分类:技术文章
本文共 1465 字,大约阅读时间需要 4 分钟。
题目链接:
时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K 64bit IO Format: %lld题目描述
kotori最近在研究n皇后的问题。
所谓n皇后问题是这样的:一个n*n的地图,上面一共放n个皇后,保证任意两个皇后都不能互相攻击(每个皇后可以攻击同一行、同一列以及同一45度角斜线和135度角斜线上的所有其他皇后)。
kotori思考了很久都无法得出答案,整个人都变成琴梨了。她于是拿了一堆皇后在一个无穷大的棋盘上模拟,按照次序一共放了k个皇后。
但是,皇后的站位太复杂了,kotori甚至不知道是否存在两个皇后会互相攻击。于是她想问问聪明的你,在第i个皇后放置在棋盘上之后,是否存在两个皇后可以互相攻击?
输入描述
第一行输入一个正整数k,代表总共放置的皇后的个数。(1<=k<=1e5)
接下来的k行,每行两个正整数xi和yi,代表每个皇后的坐标。(1<=xi,yi<=1e9) 之后输入一个正整数t,代表t次询问。(1<=t<=1e5) 接下来的t行,每行一个正整数i,代表询问第i个皇后放置后,是否存在互相攻击的情况。(1<=i<=k) 保证不存在两个皇后放置的位置相同。输出描述
共t行。每行对应当前的询问是否存在两个皇后可以互相攻击,若是则输出“Yes”,否则输出“No”
输入
5
1 2 2 5 3 1 6 7 4 8 2 2 4
输出
No
Yes
说明
第四个皇后放置后,第四个和第一个皇后可以互相攻击。
解题思路
题意:判断是否存在两个皇后可以互相攻击。
思路:利用n皇后相互攻击的规律,利用set求解。Accepted Code:
#includeusing namespace std;const int inf = 0x3f3f3f3f;set setr, setc, set45, set135;bool Judge(int x, int y) { if (setr.count(x) || setc.count(y) || set45.count(x - y) || set135.count(x + y)) return true; return false;}int main() { int n, m, t, x, y, min_ = inf; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d", &x, &y); if (min_ >= inf) { if (Judge(x, y)) min_ = i; setr.insert(x); setc.insert(y); set45.insert(x - y); set135.insert(x + y); } } scanf("%d", &t); while (t--) { scanf("%d", &m); if (m >= min_) printf("Yes\n"); else printf("No\n"); } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/94551301 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月12日 12时34分34秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Nginx URL重写(rewrite)配置及信息详解
2019-05-01
Nginx rewrite模块深入浅出详解
2019-05-01
mysql 数据库优化配置实例
2019-05-01
crontab定时任务写法
2019-05-01
nginx: [emerg] unknown directive "if($remote_addr" in /usr/local/tools/nginx/conf/nginx.conf:57
2019-05-01
module pip has no attribute main问题解决
2019-05-01
LeetCode 130.Surrounded Regions (被围绕的区域)
2019-05-01
muduo网络库——详解muduo多线程模型
2019-05-01
muduo网络库源码分析——整体架构
2019-05-01
LeetCode 131.Palindrome Partitioning (分割回文串)
2019-05-01
LeetCode 134.Gas Station (加油站)
2019-05-01
LeetCode 135.Candy (分发糖果)
2019-05-01
Python之命名元组 (namedtuple)
2019-05-01
使用libpcap过滤arp
2019-05-01
微软C/C++ 编译器选项参考
2019-05-01
VS 2005使用map文件查找程序崩溃原因
2019-05-01