由于船移动的速度都一样,那么对于往一个方向的船相对距离其实是不变的,我们可以把往一个方向移动的船都视作静止,并求出在哪些观测位置可以看到,很明显对于船[x,y,z],当x+z>=y-z的时候,可以在[y-z,x+z]这些位置观测到它,这些位置的观测数全都+1,然后考虑不同方向,假设初始在x位置观测往右的船,在y位置观测到往左的船,只要x<=y,则经过一段时间的移动,必然存在一个位置可以同时观测到x位置和y位置能观测到的船。复杂度O(nlogn)。
代码
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
using namespace std;
const int N = ;
const int M = ;
int test,a,b,c,d,i,f1[N],f2[N],g1[N],g2[N],n,s1[N],s2[N],tmp,ans,ii,tot;
int cnt1,cnt2,tt,ttt,vv[N];
struct g{
int l,r,id;
}v[N];
map<int,int> ma;
int main()
{
scanf("%d",&test);
while (test--)
{
scanf("%d",&n);
tt=;ttt=;ma.clear();tot=;
for (i=;i<=n;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
if (a+c>=b-c)
{
tot++;
v[tot].l=b-c;
v[tot].r=a+c;
v[tot].id=d;
vv[++tt]=b-c;
vv[++tt]=a+c;
}
}
sort(vv+,vv++tt);
for (i=;i<=tt;i++)
if (ma[vv[i]]==) ma[vv[i]]=++ttt;
for (i=;i<=tot;i++)
if (v[i].id==)
{
f1[ma[v[i].l]]++;
g1[ma[v[i].r]]--;
}
else
{
f2[ma[v[i].l]]++;
g2[ma[v[i].r]]--;
}
tmp=ans=cnt1=cnt2=;
for (i=;i<=ttt;i++)
{
cnt1+=f1[i];
s1[i]=cnt1;
cnt1+=g1[i];
cnt2+=f2[i];
s2[i]=cnt2;
cnt2+=g2[i];
if (s1[i]>tmp) tmp=s1[i];
ans=max(ans,tmp+s2[i]);
f1[i]=f2[i]=g1[i]=g2[i]=;
}
ii++;
printf("Case #%d:\n%d\n",ii,ans);
}
}
hdu5714 拍照[2016百度之星复赛C题]的更多相关文章
-
hdu5713 K个联通块[2016百度之星复赛B题]
dp 代码 #include<cstdio> ; ; int n,m,k,cnt[N]; ]; ][],i,j,l,a,b; int check(int x,int y) { int i; ...
-
hdu5715 XOR 游戏 [2016百度之星复赛D题]
比赛的时候没仔细想,赛后一想这题其实挺简单的,先求出序列的异或前缀和,然后将异或前缀和建出一颗trie树,然后我们可以二分答案,把问题变成判定性问题,判定是否存在一种方案,使得所有的分组的异或和都大 ...
-
2016";百度之星"; - 复赛(Astar Round3) 1003 拍照
拍照 思路:先静态,离线树状数组,分别统计每个点向左向右能看到的船的数量.再枚举整个区间求最大值. 应为人和船都是动态的,假设船往左走,处理每个点看到向左最大船的数量,满足动态条件.就是向左的船一开始 ...
-
2016百度之星 初赛2A ABEF
只做了1001 1002 1005 1006.剩下2题可能以后补? http://acm.hdu.edu.cn/search.php?field=problem&key=2016%22%B0% ...
-
2016百度之星 资格赛ABCDE
看题:http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=690 交题:http://acm.hdu.edu.cn/search.php ...
-
HDU 5690:2016";百度之星"; - 初赛 All X
原文链接:https://www.dreamwings.cn/hdu5690/2657.html All X Time Limit: 2000/1000 MS (Java/Others) Mem ...
-
HDU 5688:2016";百度之星"; - 资格赛 Problem D
原文链接:https://www.dreamwings.cn/hdu5688/2650.html Problem D Time Limit: 2000/1000 MS (Java/Others) ...
-
HDU 5686:2016";百度之星"; - 资格赛 Problem B
原文链接:https://www.dreamwings.cn/hdu5686/2645.html Problem B Time Limit: 2000/1000 MS (Java/Others) ...
-
HDU 5685:2016";百度之星"; - 资格赛 Problem A
原文链接:https://www.dreamwings.cn/hdu5685/2637.html Problem A Time Limit: 2000/1000 MS (Java/Others) ...
随机推荐
-
Android调用手机摄像头使用MediaRecorder录像并播放
最近在项目开发中需要调用系统的摄像头录像并播放. 在开发中遇到了两个问题,记录下: (1)开发过程中出现摄像头占用,启动失败,报错.但是我已经在onDestory()中关闭了资源. 报错原因:打开程序 ...
-
hdu4747——Mex
1.题目大意:对一个序列的每一个区间求Mex,最后所有的mex相加(mex就是SG的那个),力求nlogn... 2.分析:最近开始刷线段树了,还是有很多不会啊 首先把1-1 1-2 1-- 1-n这 ...
-
强大的JQuery(一)--基础篇
JQuery是一个优秀的Javascript框架,是轻量级的js库,使用jQuery将极大的提高编写javascript代码的效率,,让写出来的代码更加优雅,更加健壮. 学好了jquery,我们相当于 ...
-
struts2.1笔记05:struts2开发环境的搭建
1.找到开发Struts应用需要使用到的jar文件. 首先我们要在myEclipse中新建一个Web Project,我们这里命名为"struts2".然后我们就要使用jar文件, ...
-
个人Python常用Package及其安装
为了避免每次重装系统时又要东翻西找,现在此记录一下目前常用的Python包安装过程. 1) Python: 2.7.11, 下载地址:www.python.org.由于个人喜欢使用PyQt4(其实是不 ...
-
rhel6.4 配置本地yum的源
1 创建rhel-debuginfo.repo,如果有则先备份再删除 cd /etc/yum.repos.d rm rhel-debuginfo.repo vi rhel ...
-
GeoServer初识与安装
学习过程中发现官网上的东西足够基础了,所以在这只做一下索引和补充. 官方网址:http://live.osgeo.org/zh/overview/geoserver_overview.html 安装: ...
-
前端开发之基础知识-HTML(一)
1.1 html概述和基本结构 html概述 HTML是 HyperText Mark-up Language 的首字母简写,意思是超文本标记语言,超文本指的是超链接,标记指的是标签,是一种用来制作网 ...
-
大数据计算框架Hadoop, Spark和MPI
转自:https://www.cnblogs.com/reed/p/7730338.html 今天做题,其中一道是 请简要描述一下Hadoop, Spark, MPI三种计算框架的特点以及分别适用于什 ...
-
Python——Flask框架——程序的基本结构
一.安装 pip install flask 二.初始化 from flask import Flask app = Flash(__name__) 三.路由:处理URL和函数之间的关系的程序称为路由 ...