[HDU5714]拍照
题目大意:
河上有\(n(n\le10^4)\)个船只,小明希望把尽可能多的船只都完整地拍到一张照片中。
小明位于河的边上,并且可以在河边的任意位置进行拍照,照相机的视野恰好为\(90\)度角,只能以垂直于河边的方向进行拍照。河上的船只全都可看作是平行于河边的一条线段,左右坐标分别为\(x_i,y_i\),跟河边的距离为\(z_i\),有的正在向左移动,有的正在向右移动,但移动速度恰好都是一样的。小明可以等待恰当的时间让尽量多的船只都走进照相机的视野里,你不需要考虑船只之间会互相遮挡视野的情况。
思路:
根据运动的相对性,我们不妨以向右移动的船作为参照物,那么剩下的船按照相同的速度像左运动。
显然\(y_i-x_i>2z_i\)的船注定无法完全拍摄。否则初始状态下,每个船在岸上可以被看见的区间是\([y_i-z_i,x_i+z_i]\)。
用对于向左、右行驶的船只,用线段树分别维护能够看到的区间。
枚举人站的位置\(i\),由于向右行驶的船不动,能看到的向右行驶的船的数量是确定的。我们在向左行驶的线段树上查找大于等于\(i\)的位置上能看到的船数的最大值即可。
源代码:
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
register bool neg=false;
while(!isdigit(ch=getchar())) neg|=ch=='-';
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return neg?-x:x;
}
const int N=1e4+1;
struct Boat {
int x,y,z,d;
};
Boat b[N];
int tmp[N<<1];
class SegmentTree {
#define _left <<1
#define _right <<1|1
#define mid ((b+e)>>1)
private:
int val[N<<3],tag[N<<3];
void push_up(const int &p) {
val[p]=std::max(val[p _left],val[p _right]);
}
void push_down(const int &p) {
if(tag[p]==0) return;
tag[p _left]+=tag[p];
tag[p _right]+=tag[p];
val[p _left]+=tag[p];
val[p _right]+=tag[p];
tag[p]=0;
}
public:
void build(const int &p,const int &b,const int &e) {
tag[p]=val[p]=0;
if(b==e) return;
build(p _left,b,mid);
build(p _right,mid+1,e);
}
void modify(const int &p,const int &b,const int &e,const int &l,const int &r) {
if(b==l&&e==r) {
val[p]++;
tag[p]++;
return;
}
push_down(p);
if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r));
if(r>mid) modify(p _right,mid+1,e,std::max(mid+1,l),r);
push_up(p);
}
int query(const int &p,const int &b,const int &e,const int &l,const int &r) {
if(b==l&&e==r) return val[p];
push_down(p);
int ret=0;
if(l<=mid) ret=std::max(ret,query(p _left,b,mid,l,std::min(mid,r)));
if(r>mid) ret=std::max(ret,query(p _right,mid+1,e,std::max(mid+1,l),r));
return ret;
}
#undef _left
#undef _right
#undef mid
};
SegmentTree t[2];
int main() {
const int T=getint();
for(register int i=1;i<=T;i++) {
int n=getint();
tmp[0]=0;
for(register int i=1;i<=n;i++) {
const int x=getint(),y=getint(),z=getint(),d=getint();
if(y-x>z*2) {
i--;
n--;
continue;
}
b[i]=(Boat){x,y,z,d};
tmp[++tmp[0]]=x+z;
tmp[++tmp[0]]=y-x;
}
std::sort(&tmp[1],&tmp[tmp[0]]+1);
tmp[0]=std::unique(&tmp[1],&tmp[tmp[0]]+1)-&tmp[1];
t[0].build(1,1,tmp[0]);
t[1].build(1,1,tmp[0]);
for(register int i=1;i<=n;i++) {
const int &x=b[i].x,&y=b[i].y,&z=b[i].z,&d=b[i].d;
const int l=std::lower_bound(&tmp[1],&tmp[tmp[0]]+1,y-z)-tmp;
const int r=std::lower_bound(&tmp[1],&tmp[tmp[0]]+1,x+z)-tmp;
t[d==1].modify(1,1,tmp[0],l,r);
}
int ans=0;
for(register int i=1;i<=tmp[0];i++) {
ans=std::max(ans,t[1].query(1,1,tmp[0],1,i)+t[0].query(1,1,tmp[0],i,tmp[0]));
}
printf("Case #%d:\n%d\n",i,ans);
}
return 0;
}
[HDU5714]拍照的更多相关文章
-
hdu-5714 拍照(二分)
题目链接: 拍照 Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Proble ...
-
hdu5714 拍照[2016百度之星复赛C题]
由于船移动的速度都一样,那么对于往一个方向的船相对距离其实是不变的,我们可以把往一个方向移动的船都视作静止,并求出在哪些观测位置可以看到,很明显对于船[x,y,z],当x+z>=y-z的时候,可 ...
-
UWP开发之Template10实践二:拍照功能你合理使用了吗?(TempState临时目录问题)
最近在忙Asp.Net MVC开发一直没空更新UWP这块,不过有时间的话还是需要将自己的经验和大家分享下,以求共同进步. 在上章[UWP开发之Template10实践:本地文件与照相机文件操作的MVV ...
-
mono for android 获取手机照片或拍照并裁剪保存
axml <?xml version="1.0" encoding="utf-8"?> <LinearLayout xmlns:android ...
-
iOS开发系列--音频播放、录音、视频播放、拍照、视频录制
--iOS多媒体 概览 随着移动互联网的发展,如今的手机早已不是打电话.发短信那么简单了,播放音乐.视频.录音.拍照等都是很常用的功能.在iOS中对于多媒体的支持是非常强大的,无论是音视频播放.录制, ...
-
H5拍照应用开发经历的那些坑儿
一.项目简介 1.1.项目背景:这是一个在移动终端创新应用的项目,用户在浏览器端(微信/手Q)即可完成与金秀贤的合影,希望通过这样一种趣味体验,引发用户的分享与转发的热潮. 1.2.系统要求:ios6 ...
-
html5上传图片(二)一解决部分手机拍照上传图片转向问题
本以为解决跨域上传后没有问题了,不成想被测试找出一个问题,那就是在手机上拍照上传后图片会旋转.很头痛,不过没有办法,问题还是需要解决的.在查阅了一系列资料后我找到了相应的解决方案,利用exif.js获 ...
-
用AVFoundation自定义相机拍照
自定义拍照或者录视频的功能,就需要用到AVFoundation框架,目前我只用到了拍照,所以记录下自定义拍照用法,视频用法等用上了再补充,应该是大同小异 demo在这里:https://github. ...
-
微信调用照相拍照等 js 接口的权限配置 和 照片上传和下载实现
直接上代码: 1. 前端调试代码: <html> <head> <meta http-equiv="Content-Type" content=&qu ...
随机推荐
-
MySQL utf8mb4 字符集:支持 emoji 表情符号
转载地址:http://www.linuxidc.com/Linux/2013-05/84360.htm 我用他的方法解决了问题,亲测可用,不要用Nnvicat for Mysql去查询编码,在服务器 ...
-
VS2013 抛出 * exception 的追踪
本公司使用VWG.Caslte ActiveRecord.CSLA.net .Quantz.net 等组件做为公司的开发基础,自2007年以来,一直工作正常,但最近(2015.12月)以来,打开MDA ...
-
SAP中获取当前用户相关信息的两个函数
函数名:TH_USER_LIST作用:可以得到SM04界面显示样式的表. 函数名:TH_USER_INFO作用:可以得到当前特定用户的机器名.当前活动窗口数.IP地址等信息
-
Java内存模型--JMM简介
JMM:Java Memory Model(Java内存模型),围绕着在并发过程中如何处理可见性.原子性.有序性这三个特性而建立的模型. 可见性:JMM提供了volatile变量定义,final.sy ...
-
Sum of divisors
Problem Description mmm is learning division, she's so proud of herself that she can figure out the ...
-
ue4打包问题的巧妙解决——二分回退大法!
昨天突然发生了一件非常恐怖的事--我的ue4项目居然不能打包了!! 大概是这么一回事: UATHelper: 打包 (Windows (64位)): UnrealBuildTool: ERROR: ...
-
PHP多进程编程pcntl_fork解
其实PHP是支持并发的,只是平时很少使用而已.平时使用最多的应该是使用PHP-FMP调度php进程了吧. 但是,PHP的使用并不局限于做Web,我们完全也可以使用PHP来进行系统工具类的编程,做监控或 ...
-
[BX]指令
mov ax,[bx] 功能:bx中存放的数据作为一个偏移地址EA,段地址SA默认在ds中,将SA:EA处的数据送入ax中.即(ax)=((ds)*16+(bx)). mov [bx],ax 功能:b ...
-
在Eclipse中导入dtd和xsd文件,使XML自动提示
DTD 类型约束文件 1. Window->Preferences->XML->XML Catalog->User Specified Entries窗口中,选择Add ...
-
python+pymssql+selenium 获取短信验证码登录(实战练习)
登录页面输入手机号, 获取短信验证码(验证码有10分钟有效期) 1 连接sql server数据库,获取10分钟之内的有效短信验证码 2 页面输入手机号,并获取验证码.若存在有效验证码则输入验证码,若 ...