codeforces B. Ping-Pong (Easy Version) 解题报告

题目链接：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 。以题目中的数据为例，

对于第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 }