Boleyn Su's Blog

无语，WA了很多次，出错的地方分别是精度，还有就是两句同样的错误。

思路是找出比X小的数一共有几个，再找出不超过Y的数一共有几个，然后相减得答案。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-28

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 <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 long long int Type;

      Type X,Y;

      int K,B;

      static Type C(Type n,Type m)

      {

             if (m<0||m>n) return 0;

             Type c=1;

             for (int i=m+1;i<=n;i++) c=c*i/(i-m);

             return c;

      }

      public:

      Application()

      {

                   cin>>X>>Y

                      >>K

                      >>B;

      }

      int run()

      {

          vector<Type> b;

          b.push_back(1);

          while (b.back()*B<=Y) b.push_back(b.back()*B);

         

          Type min=0,max=0;

          vector<bool> min_state(b.size(),false),max_state(b.size(),false);

          int counter;

         

          counter=0;

          for (int i=b.size()-1;i>=0;i–)

              if (min+b[i]<X&&counter<K) min+=b[i],counter++,min_state[i]=true;

          counter=0;

          for (int i=b.size()-1;i>=0;i–)

              if (max+b[i]<=Y&&counter<K) max+=b[i],counter++,max_state[i]=true;

         

          Type min_index=1,max_index=1;

          counter=K;

          for (int i=min_state.size()-1;i>=0;i–)

              if (min_state[i]) min_index+=C(i,counter–);

          if (counter) min_index–;

          counter=K;

          for (int i=max_state.size()-1;i>=0;i–)

              if (max_state[i]) max_index+=C(i,counter–);

          if (counter) max_index–;

          cout<<max_index-min_index<<endl;

         

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

 

想到了NOIP2007的core，然后先求出树的直径（从一点DFS找最远点，再从最远点DFS找最远点，两个最远点的距离为直径）。然后由一条直径的两个端点分别标记距它们不超过(直径+1)/2的点，两次都被标记的就输出。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-28

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

      vector<vector<int> > link;

      int max;

      int maxid;

      vector<bool> visited;

      vector<int> mark;

      void dfs(int node,int depth=0)

      {

           if (visited[node]) return;

          

           visited[node]=true;

           if (depth>max)

           {

              max=depth;

              maxid=node;

           }

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

               dfs(link[node][i],depth+1);

           visited[node]=false;

      }

      void dfs_mark(int node,int R)

      {

           if (visited[node]) return;

           if (R<0) return;

          

           visited[node]=true;

           mark[node]++;

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

               dfs_mark(link[node][i],R-1);

           visited[node]=false;

      }

      public:

      Application()

      {

                   cin>>N;

                   link.resize(N);

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

                       cin>>p,link[p-1].push_back(i),link[i].push_back(p-1);

      }

      int run()

      {

          int head,tail,R;

          visited.resize(N,false);

         

          max=0;

          dfs(0);

          head=maxid;

         

          max=0;

          dfs(maxid);

          tail=maxid;

         

          R=(max+1)/2;

         

          mark.resize(N,0);

          dfs_mark(head,R);

          dfs_mark(tail,R);

         

          vector<int> answer;

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

              if (mark[i]==2) answer.push_back(i+1);

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

              cout<<answer[i]<<char(i+1==answer.size()?’\n’:’ ‘);

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，分解质因数。

好像必须先打素数表，反正我打了的。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-27

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 <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=50000;

      int N,M;

      int answer;

      vector<int> prime;

      vector<int> counter;

      void get_prime()

      {

           prime.push_back(2);

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

           {

               bool can=true;

               for (int j=0;j<prime.size();j++)

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

                   {

                      can=false;

                      break;

                   }

               if (can) prime.push_back(i);

           }

      }

      void get_counter(int n,int m)

      {

           counter.resize(prime.size(),0);

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

               for (int j=0,k=i;j<prime.size();j++)

                   while (k%prime[j]==0) k/=prime[j],counter[j]++;

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

               for (int j=0,k=i;j<prime.size();j++)

                   while (k%prime[j]==0) k/=prime[j],counter[j]–;

           for (int i=n-m;i>=1;i–)

               for (int j=0,k=i;j<prime.size();j++)

                   while (k%prime[j]==0) k/=prime[j],counter[j]–;

      }

      public:

      Application()

      {

                   cin>>N>>M;

      }

      int run()

      {

          get_prime();

          get_counter(N,M);

          answer=0;

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

              if (counter[i]) answer++;

          cout<<answer<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

就是倒着放回去，一直放到初始状态。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-27

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

      vector<int> pos;

      static void swap(int& a,int& b)

      {

             static int s;

             s=a;

             a=b;

             b=s;

      }

      public:

      Application()

      {

                   cin>>N;

                   pos.resize(N);

                   for (int i=0;i<N;i++) cin>>pos[i];

      }

      int run()

      {

          int step=0;

          bool can=true;

          int a=1,b=2,c=3;

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

          {

              if (pos[i]==a) 

                 swap(b,c);

              else if (pos[i]==b)

                   swap(a,c),step+=1<<i;

              else can=false;

          }

          if (can) cout<<step<<endl;

          else cout<<-1<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

推荐去看NOCOW的翻译，而不是百度一下题解。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-27

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

      vector<int> a;

      static int gcd(int a,int b)

      {

             return b?gcd(b,a%b):a;

      }

      public:

      Application()

      {

                   cin>>N;

                   a.resize(N);

                   for (int i=0;i<N;i++) cin>>a[i];

      }

      int run()

      {

          int answer=a[0];

          for (int i=1;i<N;i++) answer=gcd(answer,a[i]);

          cout<<answer<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，O(n^3)过了。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-27

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

      vector<pair<int,int> > rabbit;

      public:

      Application()

      {

                    cin>>N;

                    rabbit.resize(N);

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

                        cin>>rabbit[i].first>>rabbit[i].second;

      }

      int run()

      {

          #define can(a,b,c) (rabbit[a].first-rabbit[b].first)\

                             *(rabbit[a].second-rabbit[c].second)\

                             ==(rabbit[a].first-rabbit[c].first)\

                             *(rabbit[a].second-rabbit[b].second)

          int K=0;

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

              for (int b=a+1;b<N;b++)

              {

                  int counter=2;

                  for (int c=b+1;c<N;c++)

                      if (can(a,b,c)) counter++;

                  if (counter>K) K=counter;

              }

          cout<<K<<endl;

          #undef can

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

看了题解做的，不好讲。主要思路就是逐步降低问题规模，一直降到m,n都很小，和3有关系。然后就得到了下面的程序。恩，还是不太懂。

OCDE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-27

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

      public:

      Application()

      {

                    cin>>M>>N;

      }

      int run()

      {

          if (M==1||N==1) cout<<(M+N)/2<<endl;

          else cout<<((M*N)%3?1:2)<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

无语的水题，我又写了很长的代码，而WSC的好短哦。

字符串处理，首先分段，然后如果有偶数个双引号，则单的变“，双的变”，如果有奇数个双引号，则最后一个省略，其他同前。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-27

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 <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 <cstdio>

//using std::EOF;

 

class Application

{

      string file;

      public:

      Application()

      {

                    char c;

                    while ((c=cin.get())!=EOF) file.push_back(c);

      }

      int run()

      {

          for (int i=0,j;i<file.length();i=j)

          {

              bool endinput=false;

              for (int k=i;;k++)

              {

                  if (file.substr(k,4)==“\\par”)

                  {

                     j=k+4;

                     break;

                  }

                  if (file.substr(k,9)==“\\endinput”)

                  {

                     endinput=true;

                     j=file.length();

                     break;

                  }

                  if (file.substr(k,2)==“\n\n”)

                  {

                     j=k+2;

                     break;

                  }

              }

             

              int total=0;

              bool printed;

              int counter=0;

             

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

                  if (k==0||file[k-1]!=’\\’)

                     if (file[k]=='”‘)

                        total++;

             

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

              {

                  printed=false;

                  if (k==0||file[k-1]!=’\\’)

                  {

                     if (file[k]=='”‘)

                     {

                        if (counter%2)

                        {

                           counter++;

                           cout<<“””;

                           printed=true;

                        }

                        else

                        {

                            counter++;

                            if (total!=counter) cout<<““”;

                            printed=true;

                        }

                     }

                  }

                  if (!printed) cout<<file[k];

              }

             

              if (endinput) break;

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，将十个数的乘积分解成a1^n1*a2^n2*…*ak^nk的形式（当然不要先乘再分解）。然后结果为(n1+1)*(n2+1)*…*(nk+1) mod 10。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-26

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 <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 NUMBER=10;

      static const int oo=10000;

      vector<int> a;

      int last_digit_of_N;

      vector<int> counter;

      public:

      Application()

                   :a(NUMBER)

      {

                   for (int i=0;i<NUMBER;i++) cin>>a[i];

      }

      int run()

      {

          counter.resize(oo+1,1);

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

              for (int j=2;j<=oo;j++)

                  while (a[i]%j==0) counter[j]++,a[i]/=j;

          last_digit_of_N=1;

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

              last_digit_of_N=last_digit_of_N*counter[i]%10;

          cout<<last_digit_of_N<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水水的高精加法，然后让我明白了，库的确效率低。我起初用std::stack（因为要倒序输出），结果TLE，无语。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-25

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 <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

{

      public:

      Application()

      {

      }

      int run()

      {

          int N;

          cin>>N;

          vector<pair<int,int> > data;

          data.resize(N);

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

              cin>>data[i].first>>data[i].second;

         

          string answer;

          answer.resize(N);

          int over=0;

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

          {

              answer[i]=’0’+((data[i].first+data[i].second+over)%10);

              over=(data[i].first+data[i].second+over)/10;

          }

          cout<<answer<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}