CodeForces - 320B Ping-Pong (Easy Version)

题目最开始完全不懂配合案例也看不懂-_-

总之就是用传递性问能否从a区间到b区间

dfs(x,y) 走遍与第x区间所有的联通区间最后检验第y区是否被访问过

是一道搜索好题搜索还需加强

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 using namespace std;

 typedef long long ll;

 typedef pair<ll,ll> P;

 int N,n = ;//record how many intervals

 bool vis[];

 P p[];

 bool check(int x, int y)

 {

     return ( (p[x].first < p[y].second && p[x].first > p[y].first) || (p[x].second < p[y].second && p[x].second > p[y].first) );

 }

 void dfs(int x, int y)//x-->>start interval; y-->>end interval 把所有与x联通的区间都走一遍

 {

     //if(x == n) return false;//

     if ( vis[x] || vis[y] ) return ;

     vis[x] = true;//经过了x

     for (int i = ; i < n; i++)

     {

         if (vis[i]) continue;//hes been visited

         if ( check(x, i) )//之前版本 if (dfs(x,i) && dfs(i,Y) return true;//每次进函数都会找 x连通的

         {

             dfs(i, y);

         } //不需要dfs(x,i) check即可 因为 跳转到dfs(i, y ) 小看了dfs()想多了

     }

     return ;//最终只需要检查 vis[b]即可 ->b是否被走过

 }

 int main()

 {

     int query, a, b;

     freopen("in.txt", "r", stdin);

     scanf("%d", &N);

     for (int i = ; i < N; i++)

     {

         scanf("%d%d%d", &query, &a, &b);

         if (query == )

         {

             p[n].first = a;

             p[n].second = b;

             n++;

         }

         else if (query == )

         {

             memset(vis, , sizeof(vis));

             dfs(a-, b-);

             if (vis[b-]) printf("YES\n");

             else printf("NO\n");

         }

     }

     return ;

 }

同样的这道题用bfs也可以做

理解一下 dfs和bfs的区别

dfs-->> 一条路走到黑知道无法走然后再走另外一条路

如果正确结果在最后一个分支那么相当于就是把所有可能都遍历了一遍

bfs-->> 每条路都先走第一步到下一个点后又走下一层的所有第一步这样每一次都想外扩展

因为每次都是走第一步每一个节点都向下一层扩展一层所以可以找到最短路径

bfs :

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <queue>

 //bfs解F题

 using namespace std;

 typedef pair<long long, long long> P;

 P interval[];

 int T, num = ;

 bool vis[];

 bool check(int x, int y)

 {

     if ( interval[x].first > interval[y].first && interval[x].first < interval[y].second || interval[x].second > interval[y].first && interval[x].second < interval[y].second)

     return true;

     return false;

 }

 bool bfs(int x, int y)

 {

     queue<int> que;

     que.push(x);

     while(!que.empty())

     {

         int tx = que.front();

         P crt = interval[tx];

         que.pop();

         if (vis[tx]) continue;

         vis[tx] = true;

         if ( check(tx, y) ) return true;

         for (int i = ; i < num; i++)

         {

             if (check(tx, i) && !vis[i])

             {

                 que.push(i);

             }

         }

     }

     return false;

 }

 int main()

 {

     freopen("in.txt", "r", stdin);

     scanf("%d", &T);

     int cas, a, b;

     while (T--)

     {

         memset(vis, , sizeof(vis));

         scanf("%d%d%d", &cas, &a, &b);

         if(cas == )

         {

             interval[num].first = a;

             interval[num].second = b;

             num++;

         }

         else

         {

             if (bfs(a-, b-)) printf("YES\n");

             else printf("NO\n");

         }

     }

     return ;

 }

巴特西

CodeForces - 320B Ping-Pong (Easy Version)

最新文章

热门文章