Boleyn Su's Blog

由于数据加强了，这个程序已经不能AC了。(我又写了一个程序，这个能AC了。)

麻烦的几何题，先选两条边，再定比分点，其中一个点枚举，另一个用面积算，然后算它们的距离更新最优解，注意精度。（原来朴素的枚举，不是超时，就是精度不够，后来写的程序用了三分法。）

还有有更好的算法，不用枚举点，不过仿佛写着更累，因为WSC就写了很久。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2011-10-27

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <cmath>

using namespace std;

 

#define point pair<double,double>

#define x first

#define y second

 

const int MAXN=50;

int N;

point P[MAXN];

 

double cross(point a,point b,point c)

{

    return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);

}

double sqr(double x)

{

    return x*x;

}

double calc(int A,int B,int C,int D,double S,double SAB,double t1)

{

    point M,N;

    M.x=P[B].x*(1-t1)+P[C].x*t1;

    M.y=P[B].y*(1-t1)+P[C].y*t1;

    double S1=abs(cross(P[A],P[B],P[C])/2)*t1;

    double S2=S/2-SAB-S1;

    double t2=S2/(abs(cross(P[A],M,P[D])/2));

    N.x=P[A].x*(1-t2)+P[D].x*t2;

    N.y=P[A].y*(1-t2)+P[D].y*t2;

    return sqrt(sqr(M.x-N.x)+sqr(M.y-N.y));

}

int main()

{

    cin>>N;

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

       cin>>P[i].x>>P[i].y;

    double S;

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

       S+=abs(cross(P[0],P[i],P[(i+1)%N])/2);

    double answer=1e10;

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

    {

       double SAB=0;

       int D=(A+N-1)%N;

       for (int B=(A+1)%N;;B=(B+1)%N)

       {

           int C=(B+1)%N;

           double SCD=S-SAB-abs(cross(P[A],P[B],P[C])/2)-abs(cross(P[A],P[C],P[D])/2);

           if (SAB>S*0.5) break;

           else if (SCD<=S*0.5)

           {

              double L=max(0.0,1.0-(SAB+abs(cross(P[A],P[B],P[C])/2)+abs(cross(P[A],P[C],P[D])/2)-S/2)/abs(cross(P[D],P[B],P[C])/2)),R=min(1.0,(S/2-SAB)/abs(cross(P[A],P[B],P[C])/2));

              for (;;)

              {

                  double LM=(L*2+R)/3;

                  double RM=(L+R*2)/3;

                  double LV=calc(A,B,C,D,S,SAB,LM);

                  double RV=calc(A,B,C,D,S,SAB,RM);

                  if (abs(LM-RM)<=0.0000001&&abs(LV-RV)<0.0000001)

                  {

                     if (answer>LV) answer=LV;

                     break;

                  }

                  else if (LV<RV) R=RM;

                  else L=LM;

              }

           }

           SAB+=abs(cross(P[A],P[B],P[C])/2);

       }

    }

    cout.setf(ios::fixed);

    cout.precision(4);

    cout<<answer<<endl;

    return 0;

}

 

无语，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();

}