POJ 1436 수평 가시 성 세그먼트 (선분 트 리 구간 수정)
제목: n 개의 세로 선분, 만약 두 선분 사 이 를 볼 수 있다 면 (즉, 하나의 수평 선분 으로 연결 하여 다른 선분 에 닿 지 않 고) 볼 수 있다 고 합 니 다. 만약 세 개의 선분 을 임의의 두 개 로 볼 수 있다 면, 그것 을 a triangle of segments 라 고 부 르 고, a triangle of segments 의 개 수 를 구하 십시오.
사고방식: 처음 엔 n ^ 3 의 복잡 도가 지나 갈 줄 몰랐어 요... 그렇다면 문 제 는 두 선분 이 보 이 는 지 여 부 를 어떻게 판단 하 느 냐 하 는 것 이다.
그러면 Y 좌표 에 구간 을 만 들 면 선분 나무의 구간 커버 문제 가 된다.
또한 선분 을 점 으로 대체 하기 때문에 '가시 적' 이라는 문제 에 대해 문제 가 생 길 수 있다. 예 를 들 어 세 개의 선분 [1, 4], [1, 2], [3, 4] 가 있 으 면 [1, 4] 구간 에서 세 개의 선분 을 볼 수 있다. 즉, [2, 3] 의 틈 을 통 해 첫 번 째 선분 을 볼 수 있다. 해결 방법 은 간단 하 다. 좌 표를 2 배로 늘 리 면 된다. 이렇게 [1, 2] 는 [2, 4], [3, 4] 는 [6, 8] 로 바 꾸 고 5 를 비 웠 다.
자세 한 참조 코드:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 1000000000 + 7;
const int INF = 1000000000;
const int maxn = 8000 + 10;
int T,n,t,q,l,r,c,col[maxn<<3],y[maxn<<1];
bool vis[maxn][maxn];
struct node {
int ly, ry, x;
node(int l=0, int r=0, int xx=0):ly(l),ry(r),x(xx) {}
bool operator < (const node& rhs) const {
return x < rhs.x || (x == rhs.x && ly < rhs.ly);
}
}a[maxn];
void pushdown(int o) {
if(col[o] >= 0) {
col[o<<1] = col[o<<1|1] = col[o];
col[o] = -1;
}
}
void update(int L, int R, int c, int l, int r, int o) {
int m = (l + r) >> 1;
if(L <= l && r <= R) {
col[o] = c;
return ;
}
pushdown(o);
if(L <= m) update(L, R, c, l, m, o<<1);
if(m < R) update(L, R, c, m+1, r, o<<1|1);
}
void query(int L, int R, int id, int l, int r, int o) {
int m = (l + r) >> 1;
if(col[o] >= 0) {
vis[id][col[o]] = true; return ;
}
if(l == r) return ;
if(L <= m) query(L, R, id, l, m, o<<1);
if(m < R) query(L, R, id, m+1, r, o<<1|1);
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
int m = 0;
for(int i=0;i<n;i++) {
scanf("%d%d%d",&a[i].ly, &a[i].ry, &a[i].x);
m = max(m, max(a[i].ly, a[i].ry));
}
sort(a, a+n);
memset(col, -1, sizeof(col));
memset(vis, false, sizeof(vis));
for(int i=0;i<n;i++) {
int l = a[i].ly;
int r = a[i].ry;
query(2*l, 2*r, i, 0, 2*m, 1);
update(2*l, 2*r, i, 0, 2*m, 1);
}
int ans = 0;
for(int i=n-1;i>=0;i--) {
for(int j=i-1;j>=0;j--) {
if(vis[i][j]) {
for(int k=j-1;k>=0;k--) {
if(vis[i][k] && vis[j][k]) ++ans;
}
}
}
}
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.