URAL1003[Parity]

(又见POJ1733,VIJOS1112)


有人用并查集还有哈希,不知道为什么,我没有用他们,就用了一个排序二叉树(STL中的std::map)。然后就AC了。


思路:


对每一个点,记录其前驱和后驱(如果有),以及到前驱和后驱的线段上1出现的奇偶性。


每次读入一条线段时,插入分四种情况:


URAL1003[Parity] - 天之骄子 - 天之骄子的家


黑线为某条已有线段。


黄线代表,左端与一条已有线段重合,且右端在这条线段及其衍生出的线段上,这样,就将图中第二条黑线段(左数,后同)分为第二红点到d和d到第三红点两条线段。


绿线代表,左端与一条已有线段重合,且右端在这条线段及其衍生出的线段外,这样,就在图中增加一条右端红点到f的线段。


粉红与蓝色线段同上面对称。


并且,这时候是不能推出矛盾的。


如果读入线段上的点不与任何已有线段有公共点,就直接插入,并且不能推出矛盾。


若两端都有公共点,就扫描整条线段,看是否有矛盾。


具体的还是看我的CODE吧。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-9


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <cstring>


using std::memset;


#include <string>


using std::string;


#include <vector>


using std::vector;


using std::pair;


using std::make_pair;


#include <map>


using std::map;


 


class Question


{


      int length;


      int Q;


      map<int,pair<int,bool> > record_l,record_r;


      bool dfs_judge_l(int l,int r,bool isEven)


      {


           map<int,pair<int,bool> >::iterator it;


           if ((it=record_l.find(l))!=record_l.end())


           {


              if (it->second.first==r)


                 return it->second.second==isEven;


              else if (it->second.first>r)


              {


                   //it->first to it->second.first it->second.second


                   record_l[r+1]=make_pair(it->second.first,isEven xor it->second.second);


                   //it->first to r isEven


                   it->second=make_pair(r,isEven);


                   return dfs_judge_r(r+1,record_l[r+1].first,record_l[r+1].second);


              }


              else


              {


                  return dfs_judge_l(it->second.first+1,r,isEven xor it->second.second);


              }


           }


           else


           {


               record_l[l]=make_pair(r,isEven);


               return true;


           }


      }


      bool dfs_judge_r(int l,int r,bool isEven)


      {


           map<int,pair<int,bool> >::iterator it;


           if ((it=record_r.find(r))!=record_r.end())


           {


              if (it->second.first==l)


                 return it->second.second==isEven;


              else if (it->second.first<l)


              {


                   //it->second.first to it->first it->second.second


                   record_r[l-1]=make_pair(it->second.first,isEven xor it->second.second);


                   //l to it->first isEven


                   it->second=make_pair(l,isEven);


                   return dfs_judge_l(record_r[l-1].first,l-1,record_r[l-1].second);


              }


              else


              {


                  return dfs_judge_r(l,it->second.first-1,isEven xor it->second.second);


              }


           }


           else


           {


               record_r[r]=make_pair(l,isEven);


               return true;


           }


      }


      public:


      bool read()


      {


           cin>>length;


           if (length==-1) return false;


           cin>>Q;


           return true;


      }


      void solve()


      {     


           int l,r;


           string answer;


          


           int answerq=1;


          


           for (;answerq<=Q;answerq++)


           {


               cin>>l>>r>>answer;


               if (!dfs_judge_l(l,r,answer==“odd”))  break;


               if (!dfs_judge_r(l,r,answer==“odd”))  break;


           }


           cout<<answerq-1<<endl;


          


           for (;answerq<Q;answerq++)


               cin>>l>>r>>answer;


           record_l.clear();


           record_r.clear();


      }


};


 


class Application


{


      public:


      int run()


      {


          Question q;


          while (q.read()) q.solve();


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

留下评论

电子邮件地址不会被公开。