本文共 3000 字,大约阅读时间需要 10 分钟。
1、
2、题目大意:
给出n段垂直的线段,如果两条线段可以用一条水平的线连接起来,且中间不能跟别的垂直的线相交,那么这两条线段称作是可见的,如果有三条线段两两是可见的,那么称作是线段三角形,求给出的这n条垂直的线段可以组成多少个线段三角形?
3、思路分析
要求多少个线段三角形,就是求有多少个三条线段两两相交的,首先我们先求出两条线段相交的情况,也就是求一下跟第一条线段相交的线段有那几条,定义一个vector容器,比如跟第一条相交的有2,3,4;跟第二条线段相交的有3
那么vector里存的就是这样的:
1 2,3,4
2 3
那么我们知道了他们之间的关系,就可以三重for循环遍历一遍求出来即可
例如我们现在已经知道1-2,1-3,我们要证明1,2,3是线段三角形,只需再证明2-3也是可见的就行了,此时去2后面查找是否有3,如果有那么这个就是线段三角形,计数器+1,
对于区间覆盖来说,用一个cover[rt]数组表示,例如cover[rt]=1,表示rt对应的区间被第一条边覆盖了
4、题目:
Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 3463 | Accepted: 1275 |
Description
Input
Output
Sample Input
150 4 40 3 13 4 20 2 20 2 3
Sample Output
1
Source
5、AC代码:
#include#include #include #include using namespace std;#define N 16005#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1int cover[N*4];int hash[N*4];vector adj[N];struct node{ int s; int e; int x;}a[N];void pushdown(int rt){ if(cover[rt]!=-1) { cover[rt<<1]=cover[rt<<1|1]=cover[rt]; cover[rt]=-1; }}void query(int L,int R,int id,int l,int r,int rt){ if(cover[rt]!=-1) { if(hash[cover[rt]]!=id) { adj[cover[rt]].push_back(id); hash[cover[rt]]=id; } return ; } if(l==r) return ; pushdown(rt); int m=(l+r)>>1; if(L<=m) query(L,R,id,lson); if(R>m) query(L,R,id,rson);}void update(int L,int R,int id,int l,int r,int rt){ if(L<=l && R>=r) { cover[rt]=id; return ; } pushdown(rt); int m=(l+r)>>1; if(L<=m) update(L,R,id,lson); if(R>m) update(L,R,id,rson);}int cmp(node a,node b){ return a.x
转载地址:http://swcdi.baihongyu.com/