题目链接:http://codeforces.com/problemset/problem/320/B
题目意思:有两种操作:"1 x y" (x?<?y) 和 "2 a b" (a?≠?b) 。 问对于的"2 a b" 询问,能否从第a行的区间到达第b行的区间(行的数量是以:"1 x y" 来统计的,不包括"2 a b"这些行),当然可以直达,也可以借助某些区间间接到达。假设给定一个区间为 (a,?b) ,能到达区间 (c,?d) 的条件需要满足 c?<?a?<?d 或者c?<?b?<?d 。以题目中的数据为例,
5
1 1 5
1 5 11
2 1 2
1 2 9
2 1 2
对于第3行的 2 1 2,即问从第1行:1 1
5 是否可以到达第2行的 1 5 11,这明显是不能的,因为 5 < 1 < 11 和 5
< 5 < 11 都不满足。而第5行的 2 1 2 则是可以的,因为可以借助1 2 9
这个桥梁:(1 5) ——> (2 9) ——> (5 11)。理由是 2 <
5 < 9 和 5 < 9 < 11。
其实这条题目的解决方法是搜索,以下用dfs来解决
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 100 + 10; 8 int a[maxn], b[maxn], ans[maxn]; 9 int n; 10 11 void dfs(int k) 12 { 13 int i; 14 ans[k] = 1; // 可以到达第k行的区间 15 for (i = 1; i <= n; i++) 16 { 17 if (a[k] > a[i] && a[k] < b[i] && !ans[i]) // !ans[i]的使用防止下一次又重复访问第 i 行的区间,致使不停的无限循环 18 dfs(i); 19 else if (b[k] > a[i] && b[k] < b[i] && !ans[i]) 20 dfs(i); 21 } 22 } 23 24 int main() 25 { 26 int i, t1, t2, choice, len; 27 while (scanf("%d", &len) != EOF) 28 { 29 n = 0; 30 for (i = 1; i <= len; i++) 31 { 32 memset(ans, 0, sizeof(ans)); // 这个很重要,每次询问都要清空,询问之间是互相独立的 33 scanf("%d", &choice); 34 if (choice == 1) 35 { 36 n++; 37 scanf("%d%d", &a[n], &b[n]); 38 } 39 else if (choice == 2) 40 { 41 scanf("%d%d", &t1, &t2); 42 dfs(t1); 43 if (ans[t2]) // 如果可以到达第t2行的区间 44 puts("YES"); 45 else 46 puts("NO"); 47 } 48 } 49 } 50 return 0; 51 }