POJ1436
2024-09-03 08:54:20
题目链接:https://vjudge.net/problem/POJ-1436
解题思路:基于y轴建立线段树。
如图是根据样例画出的图。下面都以题目样例为例。
但是,如果仅仅以给出的y1, y2为边界的话会出现线段的最右点被当成一小段线段的问题,样例中的x=4的线段和x=1的线段会被判定“不可见”。为了方便处理边界情况,我们把y1和y2都乘2再存入线段树中,这也是用线段树解决问题的时候常用的处理边界争议的方法。
在每次存入线段的时候,先检查一下已有的线段树,看看以我们要存入的线段的端点[y1,y2]为边界的线段上是否已有线段,如果有,以一个二维数组记录起来。最后以几个for循环来得出ans。
注意:用bool型代替int型可节省很多空间。一开始那个link[ ][ ]数组我是用int型的,然后提交的时候一直MLE,后来看了网上的题解,知道了这个点,把int改成bool就AC了。
AC代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int y=8000*2;
const int maxn=8000+5;
int tree[y<<2];
bool link[maxn][maxn];
struct side{
int y1,y2,x;
bool operator <(const side &a)const{
return x<a.x;
}
}tmp[maxn];
void pushdown(int rt){
tree[rt<<1]=tree[rt<<1|1]=tree[rt];
tree[rt]=-1;
}
void build(int L,int R,int x,int l,int r,int rt){
if(L<=l&&r<=R){
tree[rt]=x;
return;
}
if(l==r) return;
if(tree[rt]!=-1)
pushdown(rt);
if(L<=(l+r)/2) build(L,R,x,l,(l+r)/2,rt<<1);
if((l+r)/2<R) build(L,R,x,(l+r)/2+1,r,rt<<1|1);
}
void query(int L,int R,int index,int l,int r,int rt){
if(tree[rt]!=-1){
link[tree[rt]][index]=true;
return;
}
if(l==r)
return;
if(L<=(l+r)/2) query(L,R,index,l,(l+r)/2,rt<<1);
if((l+r)/2<R) query(L,R,index,(l+r)/2+1,r,rt<<1|1);
}
int main(){
int n,ans;
int d,i,j;
scanf("%d",&d);
while(d--){
memset(tree,-1,sizeof(tree));
memset(link,false,sizeof(link));
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d%d",&tmp[i].y1,&tmp[i].y2,&tmp[i].x);
sort(tmp,tmp+n);
for(i=0;i<n;i++){
query(tmp[i].y1*2,tmp[i].y2*2,i,0,y,1);
build(tmp[i].y1*2,tmp[i].y2*2,i,0,y,1);
}
ans=0;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++){
if(link[i][j]){
for(int k=i+1;k<j;k++){
if(link[i][k]&&link[k][j])
ans++;
}
}
}
printf("%d\n",ans);
}
return 0;
}
最新文章
- ajax同步的实现
- vs2013打开 2010项目时: 请确认 <;Import>; 声明中的路径正确,且磁盘上存在该文件
- Linux下Mysql主从复制(Master-Slave)与读写分离(Amoeba)实践
- Hadoop之Hive UDAF TopN函数实现
- JavaPersistenceWithHibernate第二版笔记-第四章-Mapping persistent classes-002identity详解
- c#不重复的排序方法
- 最小费用最大流MCMF 最小增广
- jquery学习之AJAX
- 2014年度辛星解读css第四节
- (一个)AngularJS获取贴纸Hello World
- headfirst设计模式(1)—策略模式
- ubuntu 手动安装openssh-server
- 关于jmeter读取CSV文件的详细设置
- zipkin 整合elastic
- WebApi路由解析增加版本控制
- keras的LSTM函数详解
- SQL记录-PLSQL事务
- Android——碎片事务调用失败
- PHP随机浮点数
- [JS] jq绑定事件的参数传递