博客
关于我
HDU 5480
阅读量:149 次
发布时间:2019-02-27

本文共 2000 字,大约阅读时间需要 6 分钟。

传送门 :

There are many rook on a chessboard, a rook can attack the row and column it belongs, including its own place. 
There are also many queries, each query gives a rectangle on the chess board, and asks whether every grid in the rectangle will be attacked by any rook? 
InputThe first line of the input is a integer 
TT, meaning that there are 
TT test cases. 
Every test cases begin with four integers 
n,m,K,Qn,m,K,Q
KK is the number of Rook, 
QQ is the number of queries. 
Then 
KK lines follow, each contain two integers 
x,yx,y describing the coordinate of Rook. 
Then 
QQ lines follow, each contain four integers 
x1,y1,x2,y2x1,y1,x2,y2 describing the left-down and right-up coordinates of query. 
1n,m,K,Q100,0001≤n,m,K,Q≤100,000
1xn,1ym1≤x≤n,1≤y≤m
1x1x2n,1y1y2m1≤x1≤x2≤n,1≤y1≤y2≤m
OutputFor every query output "Yes" or "No" as mentioned above.

Sample Input

22 2 1 21 11 1 1 22 1 2 22 2 2 11 11 22 1 2 2
Sample Output
YesNoYes

        题目大意:棋盘上的一个车可以吃掉同一行同一列的棋子,告诉你 车 的坐标和 一块区域,看看在这块区域中的棋子是不是都会被吃掉

        前缀和 ? 

        树状数组??

        代码如下    

#include 
#include
#include
#include
#include
using namespace std;const int maxn=100000+10;int row[maxn],col[maxn];int main(){ int t; scanf("%d",&t); while(t--) { int n,m,k,q; memset(row,0,sizeof(row)); memset(col,0,sizeof(col)); scanf("%d%d%d%d",&n,&m,&k,&q); while(k--) { int a,b; scanf("%d%d",&a,&b); row[a]=1,col[b]=1; //赋值为1 有可能出现相同的不能累加 } for(int i=1;i<=n;i++) { row[i]+=row[i-1]; } for(int i=1;i<=m;i++) { col[i]+=col[i-1]; } while(q--) { int x1,y1,x2,y2,res1,res2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); res1=row[x2]-row[x1-1]; res2=col[y2]-col[y1-1]; if(res1==(x2-x1+1)||res2==(y2-y1+1)) printf("Yes\n"); else printf("No\n"); } } return 0;}

转载地址:http://xiib.baihongyu.com/

你可能感兴趣的文章
MySQL 的instr函数
查看>>
MySQL 的mysql_secure_installation安全脚本执行过程介绍
查看>>
MySQL 的Rename Table语句
查看>>
MySQL 的全局锁、表锁和行锁
查看>>
mysql 的存储引擎介绍
查看>>
MySQL 的存储引擎有哪些?为什么常用InnoDB?
查看>>
Mysql 知识回顾总结-索引
查看>>
Mysql 笔记
查看>>
MySQL 精选 60 道面试题(含答案)
查看>>
mysql 索引
查看>>
MySQL 索引失效的 15 种场景!
查看>>
MySQL 索引深入解析及优化策略
查看>>
MySQL 索引的面试题总结
查看>>
mysql 索引类型以及创建
查看>>
MySQL 索引连环问题,你能答对几个?
查看>>
Mysql 索引问题集锦
查看>>
Mysql 纵表转换为横表
查看>>
mysql 编译安装 window篇
查看>>
mysql 网络目录_联机目录数据库
查看>>
MySQL 聚簇索引&&二级索引&&辅助索引
查看>>