注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3718][PA2014]Parking  

2014-09-14 08:44:15|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3718: [PA2014]Parking

还算比较水的题

一开始由于我傻逼所以写麻烦了

但是码长最长+速度最慢是怎么个情况QAQ

按照惯例题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
const int N = 5e4+10;
struct Rect{
int x1,x2,y1,y2,id;
int len(){return y2-y1;}
void init(int i){
id = i;
x1=scan();y1=scan();
x2=scan();y2=scan();
if(x2<x1)swap(x1,x2);
if(y2<y1)swap(y1,y2);
}
}move[N],cpy[N];
bool operator < (Rect a,Rect b){return a.x2<=b.x1;}
bool operator == (Rect a,Rect b){return (!(a<b)&&!(b<a));}
int T,lson[N],rson[N],tree[N],ROOT;
int bh[N];
inline int max(int a,int b){return a>b?a:b;}
void push(int x,int val){for(;x<=n;x+=x&-x) tree[x] = max(tree[x],val);}
int get(int x){if(x>n)return 0;int re=0;for(;x;x-=x&-x) re = max(re,tree[x]);return re;}
int main(){
//freopen("input.txt","r",stdin);
int i,j,w;
int nn=scan();
for(int ii=1;ii<=nn;ii++){
bool ok=1;bh[0]=0;
n=scan();w=scan();
for(i=1;i<=n;i++) cpy[i].init(i);
for(i=1;i<=n;i++) move[i].init(i);
sort(cpy+1,cpy+1+n);
sort(move+1,move+1+n);
bh[cpy[1].id] = ++bh[0];
for(i=2;i<=n;i++)
if(cpy[i]==cpy[i-1]) bh[cpy[i].id] = bh[0];
else bh[cpy[i].id] = ++bh[0];
for(i=1;i<=bh[0];i++)tree[i]=0;
for(i=n;i&&ok;i--){
j = get(bh[move[i].id]-1);
if(j + move[i].len() > w)ok=0;
push(bh[move[i].id],move[i].len());
}
if(ok)printf("TAK\n");
else printf("NIE\n");
}

return 0;
}

题解:
考虑什么情况下不能移动
如果两个车的长度加起来超过了w并且需要互相越过,那么就不能移动
就得到了n^2暴力的做法
但是会TLE
想想怎么优化,发现所谓“互相越过”可以看成构成了逆序对
所以定义给每个车定义“小于”运算符
然后排序并且编号,相同位置的两个车a,b要编成一个号(a不小于b 且 b不小于a)
想想用树状数组统计逆序对的方法
这里只是稍稍变一下型,把统计和变成了获取前缀/后缀max判断可行性
  评论这张
 
阅读(88)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017