hdu5714 拍照[2016百度之星复赛C题]

时间:2022-08-31 00:29:12

  由于船移动的速度都一样,那么对于往一个方向的船相对距离其实是不变的,我们可以把往一个方向移动的船都视作静止,并求出在哪些观测位置可以看到,很明显对于船[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题]的更多相关文章

  1. hdu5713 K个联通块&lbrack;2016百度之星复赛B题&rsqb;

    dp 代码 #include<cstdio> ; ; int n,m,k,cnt[N]; ]; ][],i,j,l,a,b; int check(int x,int y) { int i; ...

  2. hdu5715 XOR 游戏 &lbrack;2016百度之星复赛D题&rsqb;

     比赛的时候没仔细想,赛后一想这题其实挺简单的,先求出序列的异或前缀和,然后将异或前缀和建出一颗trie树,然后我们可以二分答案,把问题变成判定性问题,判定是否存在一种方案,使得所有的分组的异或和都大 ...

  3. 2016&quot&semi;百度之星&quot&semi; - 复赛(Astar Round3) 1003 拍照

    拍照 思路:先静态,离线树状数组,分别统计每个点向左向右能看到的船的数量.再枚举整个区间求最大值. 应为人和船都是动态的,假设船往左走,处理每个点看到向左最大船的数量,满足动态条件.就是向左的船一开始 ...

  4. 2016百度之星 初赛2A ABEF

    只做了1001 1002 1005 1006.剩下2题可能以后补? http://acm.hdu.edu.cn/search.php?field=problem&key=2016%22%B0% ...

  5. 2016百度之星 资格赛ABCDE

    看题:http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=690 交题:http://acm.hdu.edu.cn/search.php ...

  6. HDU 5690:2016&quot&semi;百度之星&quot&semi; - 初赛 All X

    原文链接:https://www.dreamwings.cn/hdu5690/2657.html All X Time Limit: 2000/1000 MS (Java/Others)    Mem ...

  7. HDU 5688:2016&quot&semi;百度之星&quot&semi; - 资格赛 Problem D

    原文链接:https://www.dreamwings.cn/hdu5688/2650.html Problem D Time Limit: 2000/1000 MS (Java/Others)    ...

  8. HDU 5686:2016&quot&semi;百度之星&quot&semi; - 资格赛 Problem B

    原文链接:https://www.dreamwings.cn/hdu5686/2645.html Problem B Time Limit: 2000/1000 MS (Java/Others)    ...

  9. HDU 5685:2016&quot&semi;百度之星&quot&semi; - 资格赛 Problem A

    原文链接:https://www.dreamwings.cn/hdu5685/2637.html Problem A Time Limit: 2000/1000 MS (Java/Others)    ...

随机推荐

  1. Android调用手机摄像头使用MediaRecorder录像并播放

    最近在项目开发中需要调用系统的摄像头录像并播放. 在开发中遇到了两个问题,记录下: (1)开发过程中出现摄像头占用,启动失败,报错.但是我已经在onDestory()中关闭了资源. 报错原因:打开程序 ...

  2. hdu4747——Mex

    1.题目大意:对一个序列的每一个区间求Mex,最后所有的mex相加(mex就是SG的那个),力求nlogn... 2.分析:最近开始刷线段树了,还是有很多不会啊 首先把1-1 1-2 1-- 1-n这 ...

  3. 强大的JQuery(一)--基础篇

    JQuery是一个优秀的Javascript框架,是轻量级的js库,使用jQuery将极大的提高编写javascript代码的效率,,让写出来的代码更加优雅,更加健壮. 学好了jquery,我们相当于 ...

  4. struts2&period;1笔记05:struts2开发环境的搭建

    1.找到开发Struts应用需要使用到的jar文件. 首先我们要在myEclipse中新建一个Web Project,我们这里命名为"struts2".然后我们就要使用jar文件, ...

  5. 个人Python常用Package及其安装

    为了避免每次重装系统时又要东翻西找,现在此记录一下目前常用的Python包安装过程. 1) Python: 2.7.11, 下载地址:www.python.org.由于个人喜欢使用PyQt4(其实是不 ...

  6. rhel6&period;4 配置本地yum的源

    1 创建rhel-debuginfo.repo,如果有则先备份再删除       cd  /etc/yum.repos.d    rm  rhel-debuginfo.repo    vi  rhel ...

  7. GeoServer初识与安装

    学习过程中发现官网上的东西足够基础了,所以在这只做一下索引和补充. 官方网址:http://live.osgeo.org/zh/overview/geoserver_overview.html 安装: ...

  8. 前端开发之基础知识-HTML(一)

    1.1 html概述和基本结构 html概述 HTML是 HyperText Mark-up Language 的首字母简写,意思是超文本标记语言,超文本指的是超链接,标记指的是标签,是一种用来制作网 ...

  9. 大数据计算框架Hadoop&comma; Spark和MPI

    转自:https://www.cnblogs.com/reed/p/7730338.html 今天做题,其中一道是 请简要描述一下Hadoop, Spark, MPI三种计算框架的特点以及分别适用于什 ...

  10. Python——Flask框架——程序的基本结构

    一.安装 pip install flask 二.初始化 from flask import Flask app = Flash(__name__) 三.路由:处理URL和函数之间的关系的程序称为路由 ...