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 。以题目中的数据为例,

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来解决

    

codeforces   B. Ping-Pong (Easy Version)   解题报告
 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 }
codeforces   B. Ping-Pong (Easy Version)   解题报告

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

上一篇:移植u-boot-2010.03 --- 内核烧写到NandFlash


下一篇:eclipse 与 tomcat 的那些路径