Boleyn Su's Blog

简单博弈。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-12

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,M;

      vector<int> k;

      public:

      Application()

      {

                   cin>>N>>M;

                   k.resize(M);

                   for (int i=0;i<M;i++) cin>>k[i];

      }

      int run()

      {

          vector<bool> f(N+1);

          f[0]=true;

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

          {

              f[i]=false;

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

                  if ((i-k[j]>=0)&&(not f[i-k[j]]))

                     f[i]=true;

          }

          cout<<(f[N]?1:2)<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，分解质因数。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-12

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

{

      static const int oo=200000;

      int n;

      vector<int> prime;

      void get_prime()

      {

           prime.push_back(2);

           for (int i=3;i<oo;i++)

           {

               bool can=true;

               for (int j=0;prime[j]*prime[j]<=i;j++)

                   if (i%prime[j]==0)

                   {

                      can=false;

                      break;

                   }

               if (can) prime.push_back(i);

           }

      }

      public:

      Application()

      {

                   cin>>n;

      }

      int run()

      {

          get_prime();

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

          {

              int order;

              cin>>order;

              cout<<prime[order-1]<<endl;

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

最短路，可以直接Floyd。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-11

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 Record

{

       int money,start;

       bool have_card;

};

class Application

{

      static const int oo=1<<20;

      int N,M;

      vector<vector<int> > bus;

      int K;

      vector<Record> data;

      vector<vector<int> > cost;

      public:

      Application()

      {

                   cin>>N>>M;

                   bus.resize(M);

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

                   {

                       int total;

                       cin>>total;

                       bus[i].resize(total);

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

                       {

                           int get;

                           cin>>get;

                           bus[i][j]=get-1;

                       }

                   }

                   cin>>K;

                   data.resize(K);

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

                   {

                       int get;

                       cin>>data[i].money>>get>>data[i].have_card;

                       data[i].start=get-1;

                   }

      }

      int run()

      {

          cost.resize(N,vector<int>(N,oo));

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

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

                  for (int k=0;k<bus[i].size();k++)

                      cost[bus[i][j]][bus[i][k]]=1;

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

              cost[i][i]=0;

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

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

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

                      if (cost[i][j]>cost[i][k]+cost[k][j])

                         cost[i][j]=cost[i][k]+cost[k][j];

          int station,money=oo;

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

          {

              int use=0;

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

                  if (!data[j].have_card)

                  {

                     use+=cost[data[j].start][i]*4;

                     if (cost[data[j].start][i]*4>data[j].money)

                     {

                        use=oo;

                        break;

                     }

                  }

                  else if (cost[data[j].start][i]==oo)

                  {

                       use=oo;

                       break;

                  }

              if (use<money)

              {

                 money=use;

                 station=i+1;

              }

          }

          if (money==oo) cout<<0<<endl;

          else cout<<station<<” “<<money<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，分三种情况讨论就行了。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-11

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::M_PI;

#define M_PI 3.141592653589793238462643383279f

using std::sqrt;

 

class Application

{

      double A,R;

      public:

      Application()

      {

                   cin>>A>>R;

      }

      int run()

      {

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

          if (R*2<=A)

             cout<<M_PI*R*R<<endl;

          else if (R*sqrt(2.0)>=A) cout<<A*A<<endl;

          else

          {

              double a=A/2;

              double c=R;

              double b=sqrt(c*c-a*a);

              cout<<(b*a+M_PI*R*R*((M_PI/2)-acos(a/c)*2)/(M_PI*2))*4<<endl;

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，不说。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-11

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,k;

      unsigned long long int answer;

      public:

      Application()

      {

                   cin>>n;

                   k=0;

                   char mark;

                   while (cin>>mark) if (mark==’!’) k++;

      }

      int run()

      {

          answer=1;

          for (int i=n;i>0;i-=k)

              answer*=i;

          cout<<answer<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

恩，就是让那个快排的时间复杂度达到最坏的O(N^2)，那么，我们自然想到给它一个1到N的数列啦。

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;

 

class Application

{

      int N;

      public:

      Application()

      {

                   cin>>N;

      }

      int run()

      {

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

              cout<<i<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

恩，先递推f[i][0]表示第i位为0且长度为i的合法串的数目，f[i][1]表示第i位为1且长度为i的合法串的数目。

然后f[0][0]=1，f[0][1]=0，f[i][0]=f[i-1][0]+f[i-1][1]，f[i][1]=f[i-1][0]。

最后，用这些信息来判断每一位该是0还是1。具体看代码。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-11

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,K;

      public:

      Application()

      {

                   cin>>N>>K;

      }

      int run()

      {

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

          f[0][0]=1;

          f[0][1]=0;

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

          {

              f[i][0]=f[i-1][0]+f[i-1][1];

              f[i][1]=f[i-1][0];

          }

          bool noanswer=false;

          string output;

          output.resize(N);

          for (int i=N;i>=1;i–)

          {

              if (K>f[i][1]+f[i][0])

              {

                 noanswer=true;

                 break;

              }

              if (K>f[i][0])

              {

                 K-=f[i][0];

                 output[N-i]=’1′;

              }

              else

              {

                 output[N-i]=’0′;

              }

          }

          if (noanswer) cout<<-1<<endl;

          else cout<<output<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

判断此图是否可能为二分图。

然后DFS染色就OK了。

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;

 

class Application

{

      static const int RED=0;

      static const int BLUE=1;

      static const int NOTCOLORED=-1;

      int N;

      vector<vector<int> > link;

      vector<int> color;

      bool color_it(int who,int with)

      {

           if (color[who]!=NOTCOLORED)

              return color[who]==with;

           else

           {

               color[who]=with;

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

                   if (!color_it(link[who][i],with==RED?BLUE:RED)) return false;

               return true;

           }

      }

      public:

      Application()

      {

                   cin>>N;

                   link.resize(N);

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

                   {

                       int get;

                       for (;;)

                       {

                           cin>>get;

                           if (get)

                           {

                              link[i].push_back(get-1);

                              link[get-1].push_back(i);

                           }

                           else break;

                       }

                   }

      }

      int run()

      {

          bool can_color_it_in_red_and_blue=true;

          color.resize(N,NOTCOLORED);

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

              if (color[i]==NOTCOLORED)

                 if (!color_it(i,RED))

                 {

                    can_color_it_in_red_and_blue=false;

                    break;

                 }

          if (can_color_it_in_red_and_blue)

          {

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

                 cout<<color[i];

             cout<<endl;

          }

          else cout<<-1<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，直接递推。O(N)预处理后，O(1)回答询问。

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;

 

class Application

{

      static const int MAXN=100000;

      public:

      Application()

      {

      }

      int run()

      {

          vector<int> a(MAXN+1);

          vector<int> max(MAXN+1);

          a[0]=0;

          a[1]=1;

          for (int i=2;i<MAXN;i++)

              if (i%2==0) a[i]=a[i/2];

              else a[i]=a[i/2]+a[i/2+1];

          max[0]=0;

          max[1]=1;

          for (int i=2;i<MAXN;i++)

              if (a[i]>max[i-1]) max[i]=a[i];

              else max[i]=max[i-1];

         

          int get;

          for (;;)

          {

              cin>>get;

              if (get) cout<<max[get]<<endl;

              else break;

          }

         

          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;

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();

}