Boleyn Su's Blog

看到题目就想到了线段树，不过这却是一道动态规划题。

然后，先将左端点按降序排，然后求右端点的最长上升子序列（当然，也可以右端升序排，左端最长下降子序列，随你便）。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-10

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

using std::priority_queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

struct Compare

{

       inline

       bool operator ()(const pair<pair<int,int>,int>& a,

                        const pair<pair<int,int>,int>& b)

       {

            if (a.first.first>b.first.first) return true;

            else if (a.first.first<b.first.first) return false;

            else return a.first.second<b.first.second;

       }

};

class Application

{

      int N;

      vector<pair<pair<int,int>,int> > segment;

      public:

      Application()

      {

            cin>>N;

            segment.resize(N);

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

            {

                cin>>segment[i].first.first

                   >>segment[i].first.second;

                segment[i].second=i+1;

            }

      }

      int run()

      {

          sort(segment.begin(),segment.end(),Compare());

          static const int NOPRE=-1;

          vector<int> f(N);

          vector<int> pre(N);

          int answer=0;

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

          {

              f[i]=1;

              pre[i]=NOPRE;

              for (int j=0;j<i;j++)

                  if (segment[i].first.first<segment[j].first.first

                      &&segment[j].first.second<segment[i].first.second)

                     if (f[j]+1>f[i])

                     {

                        f[i]=f[j]+1;

                        pre[i]=j;

                     }

              if (f[i]>f[answer]) answer=i;

          }

          cout<<f[answer]<<endl;

          stack<int> output;

          int now=answer;

          while (now!=NOPRE)

          {

                output.push(segment[now].second);

                now=pre[now];

          }

          while (!output.empty())

          {

                cout<<output.top();

                output.pop();

                if (output.empty()) cout<<endl;

                else cout<<” “;

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

图论，在图中找尽可能多的环，且一个环的边的集合不是其它环的边的集合的子集。

然后，具体操作有看题解，所以我没必要讲了。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-10

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

//using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      int N,M;

      vector<vector<bool> > map;

      vector<vector<bool> > spaning_tree;

      vector<bool> visited;

      vector<int> path;

      void dfs(int node)

      {

           visited[node]=true;

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

               if (map[node][i]&&(!visited[i]))

               {

                  map[node][i]=false;

                  map[i][node]=false;

                  spaning_tree[node][i]=true;

                  spaning_tree[i][node]=true;

                  dfs(i);

               }

      }

      void print(int node,const int& end)

      {

           if (!visited[node])

           {

              visited[node]=true;

              path.push_back(node);

              if (node==end)

              {

                 cout<<path.size();

                 for (int i=0;i<path.size();i++) cout<<” “<<path[i]+1;

                 cout<<endl;

              }

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

                  if (spaning_tree[node][i])

                     print(i,end);

              path.pop_back();

              visited[node]=false;

           }

      }

      public:

      Application()

      {

                    cin>>N>>M;

                    map.resize(N,vector<bool>(N,false));

                    for (int i=0;i<M;i++)

                    {

                        int u,v;

                        cin>>u>>v;

                        map[u-1][v-1]=map[v-1][u-1]=true;

                    }

      }

      int run()

      {

          spaning_tree.resize(N,vector<bool>(N,false));

          visited.resize(N,false);

          int part=0;

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

              if (!visited[i]) dfs(i),part++;

          cout<<M-N+part<<endl;

         

          visited=vector<bool>(N,false);

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

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

                  if (map[i][j])

                     print(i,j);

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

第一次写最小费用最大流（以前只写过最大流），第二次写bellman-ford加优化（即SPFA）。

然后一次AC，呵呵。

还有感谢WSC提供的解题思路。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-10

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

using std::priority_queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

using std::min;

#include <cassert>

//using std::assert;

 

class Application

{

      static const int oo=1<<20;

      int N;

      vector<vector<int> > data;

      vector<vector<int> > cost;

      vector<vector<int> > c;

      int answer;

      void max_flow_with_min_cost(const int& S,const int& T)

      {

           static const int NOPRE=-1;

           answer=0;

           vector<vector<int> > f((N+1)*2,vector<int>((N+1)*2,0));

           for (;;)

           {

               vector<int> pre((N+1)*2,NOPRE);

               vector<int> dis((N+1)*2,oo);

               queue<int> q;

               vector<bool> inq((N+1)*2,false);

               pre[S]=S;

               dis[S]=0;

               q.push(S);

               inq[S]=true;

               while (!q.empty())

               {

                     int now=q.front();

                     for (int i=0;i<(N+1)*2;i++)

                         if ((f[now][i]<c[now][i])

                             &&(dis[i]>dis[now]+cost[now][i]))

                         {

                            pre[i]=now;

                            dis[i]=dis[now]+cost[now][i];

                            if (!inq[i])

                            {

                               q.push(i);

                               inq[i]=true;

                            }

                         }

                     q.pop();

                     inq[now]=false;

               }

               if (pre[T]==NOPRE) break;

               else

               {

                   int delta=oo;

                   int now;

                   now=T;

                   for (;;)

                   {

                       delta=min(delta,c[pre[now]][now]-f[pre[now]][now]);

                       now=pre[now];

                       if (pre[now]==now) break;

                   }

                   now=T;

                   for (;;)

                   {

                       f[pre[now]][now]+=delta;

                       f[now][pre[now]]-=delta;

                       now=pre[now];

                       if (pre[now]==now) break;

                   }

                   answer+=delta*dis[T];

               }

           }

      }

      public:

      Application()

      {

                   cin>>N;

                   data.resize(N,vector<int>(N));

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

                       for (int j=0;j<N;j++)

                           cin>>data[i][j];

      }

      int run()

      {

          const int S=N*2,T=N*2+1;

          cost.resize((N+1)*2,vector<int>((N+1)*2,oo));

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

          {

              int sum=0;

              for (int j=0;j<N;j++)

                  sum+=data[i][j];

              for (int j=0;j<N;j++)

              {

                  cost[i][N+j]=sum-data[i][j];

                  cost[N+j][i]=data[i][j]-sum;

              }

          }

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

          {

              cost[S][i]=0;

              cost[i][S]=0;

          }

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

          {

              cost[i+N][T]=0;

              cost[T][i+N]=0;

          }

          c.resize((N+1)*2,vector<int>((N+1)*2,0));

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

              for (int j=0;j<N;j++)

                  c[i][j+N]=oo;

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

              c[S][i]=1;

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

              c[i+N][T]=1;

          max_flow_with_min_cost(S,T);

          cout<<answer<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

数学题。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-9

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

using std::priority_queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <iomanip>

#include <cassert>

//using std::assert;

#include <cmath>

using std::sqrt;

using std::acos;

 

struct Point{double x,y,z;};

double d(const Point& A,const Point& B)

{

       return sqrt((A.x-B.x)*(A.x-B.x)

                  +(A.y-B.y)*(A.y-B.y)

                  +(A.z-B.z)*(A.z-B.z));

}

double s(double a,double b,double c)

{

       double p=(a+b+c)/2;

       return sqrt(p*(p-a)*(p-b)*(p-c));

}

 

class Application

{

      Point A,B,C;

      double R;

      public:

      Application()

      {

                   cin>>A.x>>A.y>>A.z

                      >>B.x>>B.y>>B.z

                      >>C.x>>C.y>>C.z

                      >>R;

      }

      int run()

      {

          double AB=d(A,B);

          double AC=d(A,C);

          double BC=d(B,C);

         

          cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);

          if (acos((AC*AC+BC*BC-AB*AB)/(2*AC*BC))-acos(R/AC)-acos(R/BC)<0)

             cout<<AB<<endl;

          else

          {

              double answer=0;

              answer=

              sqrt(AC*AC-R*R)

              +sqrt(BC*BC-R*R)

              +R*(acos((AC*AC+BC*BC-AB*AB)/(2*AC*BC))-acos(R/AC)-acos(R/BC));

              cout<<answer<<endl;

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

 一道有点意思的题目，主要是写起巨麻烦，先是判定，我很朴素，但是没问题。

然后，输出那一段，先写的WA#2，无语，改，然后再次WA#2，如此几次。

然后，到教室上数学课。最后重写输出的那一段，AC。

恩，无语。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-9

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

using std::priority_queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

#include <cmath>

using std::floor;

 

class Application

{

      bool read(string& s,int& N)

      {

           s.clear();

           char c;

           while ((c=cin.get())!=’\n’) s.push_back(c);

           if (s==“#”) return false;

           cin>>N;

           while ((c=cin.get())!=’\n’);

           return true;

      }

      //<simple unsigned real number> ::=

      //                  <unsigned integer number>

      //                 |.<unsigned integer number>

      //                 |<unsigned integer number>.<unsigned integer number>

      bool simple_unsigned_real_number(const string& s)

      {

           if (unsigned_integer_number(s)) return true;

           if (s.substr(0,1)==“.”

               &&unsigned_integer_number(s.substr(1,s.length()-1)))

              return true;

           for (int i=1;i<s.length();i++)

               if (unsigned_integer_number(s.substr(0,i))

                   &&s.substr(i,1)==“.”

                   &&unsigned_integer_number(s.substr(i+1,s.length()-i-1)))

               return true;

           return false;          

      }

      //<simple real number> ::= <simple unsigned real number>

      //                        |<sign><simple unsigned real number>

      bool simple_real_number(const string& s)

      {

           if (simple_unsigned_real_number(s)) return true;

           for (int i=1;i<s.length();i++)

               if (sign(s.substr(0,i))

                   &&simple_unsigned_real_number(s.substr(i,s.length()-i)))

               return true;

           return false;

      }

      //<digit> ::= 0|1|2|3|4|5|6|7|8|9

      bool digit(const string& s)

      {

           return s==“0”

                  ||s==“1”

                  ||s==“2”

                  ||s==“3”

                  ||s==“4”

                  ||s==“5”

                  ||s==“6”

                  ||s==“7”

                  ||s==“8”

                  ||s==“9”;

      }

      //<unsigned integer number> ::= <digit>

      //                             |<digit><unsigned integer number>

      bool unsigned_integer_number(const string& s)

      {

           if (digit(s)) return true;

           for (int i=1;i<s.length();i++)

               if (digit(s.substr(0,i))

                   &&unsigned_integer_number(s.substr(i,s.length()-i)))

               return true;

           return false;

      }

      //<sign> ::= +|-

      bool sign(const string& s)

      {

           return s==“+”||s==“-“;

      }

      //<integer number> ::= <unsigned integer number>

      //                    |<sign><unsigned integer number>

      bool integer_number(const string& s)

      {

           if (unsigned_integer_number(s)) return true;

           for (int i=1;i<s.length();i++)

               if (sign(s.substr(0,i))

                   &&unsigned_integer_number(s.substr(i,s.length()-i)))

               return true;

           return false;

      }

      //<exponent symbol> ::= e|E

      bool exponent_symbol(const string& s)

      {

           return s==“e”||s==“E”;

      }

      //<exponent> ::= <exponent symbol><integer number>

      bool exponent(const string& s)

      {

           for (int i=1;i<s.length();i++)

               if (exponent_symbol(s.substr(0,i))

                   &&integer_number(s.substr(i,s.length()-i)))

               return true;

           return false;

      }

      //<real number> ::= <simple real number>

      //                 |<simple real number><exponent>

      bool real_number(const string& s)

      {

           if (simple_real_number(s)) return true;

           for (int i=1;i<s.length();i++)

               if (simple_real_number(s.substr(0,i))

                   &&exponent(s.substr(i,s.length()-i)))

               return true;

           return false;

      }

      void print_real_number(const string& s,int N)

      {

           static const int MAXLENGTH=200;

           static const int MAXN=100;

           int position_of_e=std::string::npos;

           if (s.find(“e”)!=std::string::npos) position_of_e=s.find(“e”);

           if (s.find(“E”)!=std::string::npos) position_of_e=s.find(“E”);

          

           string simple_real_number_part;

           int value_of_e;

           if (position_of_e!=std::string::npos)

           {

              simple_real_number_part=s.substr(0,position_of_e);

              stringstream

              in(s.substr(position_of_e+1,s.length()-(position_of_e+1)));

              double get;

              in>>get;

              if (get>MAXLENGTH) value_of_e=MAXLENGTH;

              else if (get<-MAXLENGTH) value_of_e=-MAXLENGTH;

              else value_of_e=floor(get+0.5);

           }

           else

           {

               simple_real_number_part=s;

               value_of_e=0;

           }

          

           string integral_part;

           string fractional_part;

           int position_of_dot=simple_real_number_part.find(“.”);

           if (position_of_dot!=std::string::npos)

           {

              integral_part=simple_real_number_part.substr(0,position_of_dot);

              fractional_part=

              simple_real_number_part

                  .substr(position_of_dot+1,

                          simple_real_number_part.length()-(position_of_dot+1));

           }

           else

              integral_part=simple_real_number_part;

           string flag;

           if (integral_part[0]==’-‘)

           {

              flag=“-“;

              integral_part.erase(0,1);

           }

           else if (integral_part[0]==’+’)

                integral_part.erase(0,1);

          

           do integral_part=“0”+integral_part;

           while (int(integral_part.length())+value_of_e-1<=0);

           do fractional_part=fractional_part+“0”;

           while (int(fractional_part.length())-value_of_e-1<=0);

           if (value_of_e<0)

           {

              fractional_part=

              integral_part.substr(integral_part.length()+value_of_e,

                                   -value_of_e)

              +fractional_part;

              integral_part.erase(integral_part.length()+value_of_e,

                                  -value_of_e);

           }

           if (value_of_e>0)

           {

              integral_part=

              integral_part

              +fractional_part.substr(0,value_of_e);

              fractional_part.erase(0,value_of_e);

           }

                     

           bool equal_to_zero=true;

           for (int i=0;i<integral_part.length();i++)

               if (integral_part[i]!=’0′) equal_to_zero=false;

           for (int i=0;i<fractional_part.length()&&i<N;i++)

               if (fractional_part[i]!=’0′) equal_to_zero=false;

           if (equal_to_zero) flag.clear();

          

           while (integral_part[0]==’0’&&integral_part.length()>1)

                 integral_part.erase(0,1);

           while (fractional_part.length()<MAXN)

                 fractional_part=fractional_part+“0”;

          

           cout<<flag<<integral_part;

           if (N)

           {

                 cout<<“.”;

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

                     cout<<fractional_part[i];

           }

      }

      public:

      Application()

      {

      }

      int run()

      {

          string s;

          int N;

          while (read(s,N))

                if (real_number(s))

                {

                   print_real_number(s,N);

                   cout<<endl;

                }

                else cout<<“Not a floating point number”<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

简单的DP。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-8

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

using std::priority_queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      int N;

      public:

      Application()

      {

                   cin>>N;

      }

      int run()

      {

          vector<int> f(N+1,N);

          f[0]=0;

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

          {

              for (int j=1;j*j<=i;j++)

                  if (f[i-j*j]+1<f[i]) f[i]=f[i-j*j]+1;

          }

          cout<<f[N]<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，BFS。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-8

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

using std::priority_queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      typedef unsigned int bit;

      vector<vector<bit> > computer;

      int f,t;

      public:

      Application()

      {

                   int n,k;

                   cin>>n;

                   computer.resize(n);

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

                   {

                       cin>>k;

                       computer[i].resize(k);

                       for (int j=0;j<k;j++)

                       {

                           bit a,b,c,d;

                           bit A,B;

                           char dot;

                           cin>>a>>dot>>b>>dot>>c>>dot>>d;

                           A=(a<<24)|(b<<16)|(c<<8)|(d);

                           cin>>a>>dot>>b>>dot>>c>>dot>>d;

                           B=(a<<24)|(b<<16)|(c<<8)|(d);

                           computer[i][j]=A&B;

                       }

                   }

                   cin>>f>>t;

      }

      int run()

      {

          static const int NOPRE=-1;

          vector<int> pre(computer.size(),NOPRE);

          queue<int> q;

          pre[f-1]=f-1;

          q.push(f-1);

          while (!q.empty())

          {

                int now=q.front();

                for (int i=0;i<computer.size();i++)

                    if (pre[i]==NOPRE)

                    {

                       for (int j=0;j<computer[i].size();j++)

                           for (int k=0;k<computer[now].size();k++)

                               if (computer[i][j]==computer[now][k])

                               {

                                  pre[i]=now;

                                  q.push(i);

                                  break;

                               }

                    }

                q.pop();

          }

          if (pre[t-1]==NOPRE) cout<<“No”<<endl;

          else

          {

              cout<<“Yes”<<endl;

              stack<int> path;

              int u=t-1;

              for (;;)

              {

                    path.push(u);

                    if (pre[u]==u) break;

                    u=pre[u];

              }

              while (!path.empty())

              {

                    cout<<path.top()+1;

                    path.pop();

                    if (path.empty()) cout<<endl;

                    else cout<<” “;

              }

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

进制转换。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-8

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

using std::priority_queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      int x,y;

      int answer;

      public:

      Application()

      {

                   cin>>x>>y;

      }

      int run()

      {

          answer=0;

          for (int base=2;base<=x+1;base++)

          {

              int Y=y;

              int X=x;

              bool match=true;

              while (Y)

              {

                    while (X%base!=Y%base)

                    {

                          X/=base;

                          if (X==0)

                          {

                             match=false;

                             break;

                          }

                    }

                    if (!match) break;

                    match=true;

                    X/=base;

                    Y/=base;

              }

              if (match)

              {

                 answer=base;

                 break;

              }

          }

          if (answer) cout<<answer<<endl;

          else cout<<“No solution”<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

又被水了，交了几次，先是编译错误（URAL用的编译器好神奇哦），然后还WA了两次。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-8

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

using std::priority_queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

struct Clock{int h,m;};

struct Flight{Clock start,end;};

class Application

{

      Flight gof,returnf;

      Clock distance(Clock a,Clock b)

      {

            while (a.h>=24) a.h-=24;

            while (b.h>=24) b.h-=24;

            while (a.h<0) a.h+=24;

            while (b.h<0) b.h+=24;

           

            if ((a.h<b.h)||(a.h==b.h&&a.m<b.m))

            {

               Clock s=a;

               a=b;

               b=s;

            }

            Clock d;

            d.h=a.h-b.h;

            d.m=a.m-b.m;

            if (d.m<0)

            {

               d.m+=60;

               d.h–;

            }

            if (d.h>12)

            {

               d.h=24-d.h-1;

               d.m=60-d.m;

               if (d.m>60)

               {

                  d.m-=60;

                  d.h++;

               }

            }

            return d;

      }

      bool check()

      {

           Clock god=distance(gof.start,gof.end),

                 returnd=distance(returnf.start,returnf.end);

           if ((god.h>6)||(god.h==6&&god.m!=0)) return false;

           if ((returnd.h>6)||(returnd.h==6&&returnd.m!=0)) return false;

           Clock d=distance(god,returnd);

           if ((d.h>0)||(d.h==0&&d.m>10)) return false;

          

           return true;

      }

      int abs(int n)

      {

          return n>0?n:-n;

      }

      public:

      Application()

      {

                   char dot;

                   cin>>gof.start.h>>dot>>gof.start.m

                      >>gof.end.h>>dot>>gof.end.m

                      >>returnf.start.h>>dot>>returnf.start.m

                      >>returnf.end.h>>dot>>returnf.end.m;

      }

      int run()

      {

          for (int answer=-5;answer<=5;answer++)

          {

              gof.start.h+=answer;

              returnf.start.h-=answer;

              if (check()) cout<<abs(answer)<<endl;

              returnf.start.h+=answer;

              gof.start.h-=answer;             

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

 

恩，看题解的，我也不太懂。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-8

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

using std::priority_queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      vector<int> out;

      vector<int> rest;

      vector<vector<int> > link;

      public:

      Application()

      {

                   int get;

                   while (cin>>get) out.push_back(get-1);

      }

      int run()

      {

          rest.resize(out.size()+1,0);

          link.resize(out.size()+1);

         

          priority_queue<int> q;

          for (int i=0;i<out.size();i++)

              rest[out[i]]++;

          for (int i=0;i<rest.size();i++)

              if (rest[i]==0) q.push(-i);

          for (int i=0;i<out.size();i++)

          {

              link[out[i]].push_back(-q.top());

              link[-q.top()].push_back(out[i]);

              rest[out[i]]–;

              q.pop();

              if (rest[out[i]]==0) q.push(-out[i]);

          }

          for (int i=0;i<link.size();i++)

          {

              sort(link[i].begin(),link[i].end());

              cout<<i+1<<“:”;

              for (int j=0;j<link[i].size();j++)

                  cout<<” “<<link[i][j]+1;

              cout<<endl;

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}