URAL1003[Parity]

(又见POJ1733,VIJOS1112) 有人用并查集还有哈希,不知道为什么,我没有用他们,就用了一个排序二叉树(STL中的std::map)。然后就AC了。 思路: 对每一个点,记录其前驱和后驱(如果有),以及到前驱和后驱的线段上1出现的奇偶性。 每次读入一条线段时,插入分四种情况: 黑线为某条已有线段。 黄线代表,左端与一条已有线段重合,且右端在这条线段及其衍生出的线段上,这样,就将图中第二条黑线段(左数,后同)分为第二红点到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 […]

URAL1002[Phone numbers]

动态规划。(又见POJ1732) f[i]=min{f[j],从j到i可以被匹配}+1 CODE: /* PROGRAM: $PROGRAM AUTHOR: Su Jiao DATE: 2010-3-8 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; #include <stack> using std::stack;   class Question {       int get_num[256];       string number;       vector<string> dictionary;       bool match(int f,int […]

URAL1001[Reverse root]

这是一道很水的题,有人会看题解吗? CODE: /* PROGRAM: $PROGRAM AUTHOR: Su Jiao DATE: 2010-3-8 DESCRIPTION: $DESCRIPTION */ #include <iostream> using std::cin; using std::cout; using std::endl; #include <cstring> using std::memset; #include <stack> using std::stack; #include <cmath> using std::sqrt; #include <iomanip> using std::setiosflags; using std::setprecision;   class Application {       stack<long long int> A;       public:       Application()       {                     […]

URAL1000[A+B Problem]

这是一道十分水的题,所以没人想写题解。 CODE:   /* PROGRAM: $PROGRAM AUTHOR: Su Jiao DATE: 2010-3-8 DESCRIPTION: $DESCRIPTION */ #include <iostream> using std::cin; using std::cout; using std::endl; #include <cstring> using std::memset;   class Application {       int a,b;       public:       Application()       {                     cin>>a>>b;       }       int run()       {           cout<<(a+b)<<endl;           return 0;       } […]