URAL1019[A Line painting]

被这道题整惨了,好无语。用类似矩形切割的方法做。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-16


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <sstream>


using std::stringstream;


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


      vector<int> a;


      vector<int> b;


      vector<char> c;


      public:


      Application()


      {


                    cin>>N;


                    a.resize(N);


                    b.resize(N);


                    c.resize(N);


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


                        cin>>a[i]>>b[i]>>c[i];


      }


      int run()


      {


          vector<pair<int,int> > q;    


          q.push_back(make_pair(0,1000000000));


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


          {


              switch (c[i])


              {


                     case ‘w’:


                          q.push_back(make_pair(a[i],b[i]));


                          break;


                     case ‘b’:


                          int end=q.size();


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


                          {


                              if (q[j].first<b[i]&&q[j].second>a[i])


                              {


                                 if (q[j].first<a[i])


                                    q.push_back(make_pair(q[j].first,a[i]));


                                 if (b[i]<q[j].second)


                                    q.push_back(make_pair(b[i],q[j].second));


                              }


                              else q.push_back(make_pair(q[j].first,q[j].second));


                          }


                          q.erase(q.begin(),q.begin()+end);


                          break;


              }


          }


         


          sort(q.begin(),q.end());


         


          pair<int,int> answer=make_pair(0,0);


          for (int i=0,j;i<q.size();i=j)


          {


              int first=q[i].first,second=q[i].second;


              for (j=i+1;j<q.size();j++)


                  if (q[j].first<=second)


                  {


                     if (q[j].second>second)


                        second=q[j].second;


                  }


                  else break;


              if (second-first>answer.second-answer.first)


                 answer=make_pair(first,second);


          }


          cout<<answer.first<<” “<<answer.second<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 



 


 


URAL1018[A Binary Apple Tree]

树形动规,不知为什么,写的第一个程序始终WA#8,后重写,AC,无语。

恩,方程见注释。

CODE:

/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-16


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <sstream>


using std::stringstream;


#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


{


      static const int NOTLINKED=~(1<<31);


      int N,Q;


      vector<vector<int> > length;


      public:


      Application()


      {


                    cin>>N>>Q;


                    length=vector<vector<int> >(N,vector<int>(N,NOTLINKED));


                    int a,b,c;


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


                    {


                        cin>>a>>b>>c;


                        length[a-1][b-1]=length[b-1][a-1]=c;


                    }


                    if (Q>N-1) Q=N-1;


      }


      /*


      f for father


      l for left child


      r for right child


      f.f[n]=max{


           l.f[i-1]+lenght[f][l]+r.f[n-i-1]+length[f][r],//if have two children


           l.f[n-1]+lenght[f][l],//if have left child


           r.f[n-1]+lenght[f][r],//if have right child


           0//if no child


           }


      */


      vector<vector<int> > get;


      int dp(int f,int have,int ff)


      {


          if (get[f][have]==NOTLINKED)


          {


             int l=NOTLINKED,r=NOTLINKED;


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


                 if ((i!=ff)&&(length[f][i]!=NOTLINKED))


                 {


                    if (l==NOTLINKED)


                    {


                       l=i;


                       continue;


                    }


                    if (r==NOTLINKED)


                    {


                       r=i;


                       continue;


                    }


                 }


             get[f][have]=0;


             int dpl,dpr;


             if (l!=NOTLINKED&&r!=NOTLINKED)


             {


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


                {


                    dpl=dp(l,i-1,f)+length[f][l];


                    dpr=dp(r,have-i-1,f)+length[f][r];


                    if (dpl+dpr>get[f][have])


                       get[f][have]=dpl+dpr;


                }


             }


             if (l!=NOTLINKED)


                if (have>0)


                {


                   dpl=length[f][l]+dp(l,have-1,f);


                   if (dpl>get[f][have])


                      get[f][have]=dpl;


                }


             if (r!=NOTLINKED)


                if (have>0)


                {


                   dpr=length[f][r]+dp(r,have-1,f);


                   if (dpr>get[f][have])


                      get[f][have]=dpr;


                }


          }


          return get[f][have];


      }


      int run()


      {


          get=vector<vector<int> >(N,vector<int>(Q+1,NOTLINKED));


          cout<<dp(11,Q,NOTLINKED)<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

URAL1017[The Staircases]

把N分堆,每堆不同,一共有多少分法?
f[n][i]=N分堆后最大的为i一共有几种分法
f[n][n]=1
f[n][i]=sum{f[n-i][j],1<=j<i<n}
answer=sum{f[n][i],1<=i<=n}-1
(减一是减去只有一堆的情况)
CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-16


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <sstream>


using std::stringstream;


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


      public:


      Application()


      {


                    cin>>N;


      }


      int run()


      {


          //N分堆,每堆不同,一共有多少分法?


          //f[n][i]=N分堆后最大的为i一共有几种分法


          //f[n][n]=1


          //f[n][i]=sum{f[n-i][j],1<=j<i<n}


          //answer=sum{f[n][i],1<=i<=n}-1


         


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


          for (int i=1;i<=N;i++) f[i][i]=1;


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


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


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


                      f[n][i]+=f[n-i][j];


          long long int answer=-1;


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


              answer+=f[N][i];


          cout<<answer<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}

URAL1016[A Cube on the Walk]

变态的最短路,害我写了很多行。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-16


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <sstream>


using std::stringstream;


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


 


struct Cube


{


       int left,right,top,forward,bottom,backward;


       inline


       void swap(int& a,int& b,int& c,int& d)


       {


            int s=a;


            a=b;


            b=c;


            c=d;


            d=s;


       }


       inline


       void goup()


       {


            swap(bottom,backward,top,forward);


       }


       inline


       void godown()


       {


            swap(bottom,forward,top,backward);


       }


       inline


       void goright()


       {


            swap(bottom,right,top,left);


       }


       inline


       void goleft()


       {


            swap(bottom,left,top,right);


       }


};


struct Compare


{


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


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


       {


            return a.second>b.second;


       }


};


 


class Application


{


      static const int SIDE=6;


      static const int top=0,


                       bottom=SIDE-1-top,


                       left=1,


                       right=SIDE-1-left,


                       forward=2,


                       backward=SIDE-1-forward;


      static const int SIZE=8;


      static const int ID=24;


      static const int oo=1<<29;


      pair<int,int> f,t;


      vector<int> get_point;


      vector<vector<int> > get_id;


      public:


      Application()


                   :get_point(SIDE),get_id(SIDE,vector<int>(SIDE))


      {


                    char x,y;


                    cin>>x>>y;


                    f.first=x-‘a’;


                    f.second=y-‘1’;


                    cin>>x>>y;


                    t.first=x-‘a’;


                    t.second=y-‘1’;


                    //forward, backward, top, right, bottom and left


                    cin>>get_point[forward]


                       >>get_point[backward]


                       >>get_point[top]


                       >>get_point[right]


                       >>get_point[bottom]


                       >>get_point[left];


      }


      int run()


      {


          //init get_id


          for (int i=0,id=0;i<SIDE;i++)


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


                  if ((j!=i)&&(j+i+1!=SIDE))


                     get_id[i][j]=id++;


         


          //dijkstra


          typedef pair<pair<int,int>,int> pre_type;


          vector<vector<vector<int> > >


          dist(SIZE,vector<vector<int> >(SIZE,vector<int>(ID,oo)));


          vector<vector<vector<pre_type> > >


          pre(SIZE,vector<vector<pre_type> >(SIZE,vector<pre_type>(ID)));


         


          std::priority_queue<pair<pair<Cube,pair<int,int> >,int>,


                              vector<pair<pair<Cube,pair<int,int> >,int> >,


                              Compare> q;


          //push start state


          Cube start;


          start.top=top;


          start.bottom=bottom;


          start.left=left;


          start.right=right;


          start.forward=forward;


          start.backward=backward;


          q.push(make_pair(make_pair(start,f),get_point[start.bottom]));


         


          while (!q.empty())


          {


                pair<pair<Cube,pair<int,int> >,int> now=q.top();


                #define getdist(who) (dist[who.first.second.first]\


                                          [who.first.second.second]\


                                          [get_id[who.first.first.top]\


                                                 [who.first.first.left]]\


                                     )


               


                if (getdist(now)==oo)


                {


                   getdist(now)=now.second;


                   #define assignpre(dir,dx,dy)\


                   from.first.first=now.first.first;\


                   from.first.first.go##dir();\


                   from.first.second=make_pair(now.first.second.first+(dx),\


                                               now.first.second.second+(dy));\


                   if ((from.first.second.first>=0)\


                       &&(from.first.second.first<SIZE)\


                       &&(from.first.second.second>=0)\


                       &&(from.first.second.second<SIZE)\


                       &&(getdist(from)+get_point[now.first.first.bottom]==now.second))\


                   {\


                       pre[now.first.second.first]\


                          [now.first.second.second]\


                          [get_id[now.first.first.top]\


                                 [now.first.first.left]]\


                       =make_pair(from.first.second,\


                                  get_id[from.first.first.top]\


                                        [from.first.first.left]\


                                 );\


                   }


                   pair<pair<Cube,pair<int,int> >,int> from;


                   assignpre(left,-1,0);


                   assignpre(right,1,0);


                   assignpre(up,0,1);


                   assignpre(down,0,-1);                  


                   #undef assignpre


                  


                   #define letusgo(dir,dx,dy)\


                   go.first.first=now.first.first;\


                   go.first.first.go##dir();\


                   go.first.second=make_pair(now.first.second.first+(dx),\


                                             now.first.second.second+(dy));\


                   if ((go.first.second.first>=0)\


                       &&(go.first.second.first<SIZE)\


                       &&(go.first.second.second>=0)\


                       &&(go.first.second.second<SIZE)\


                       &&(getdist(go)==oo))\


                   {\


                      go.second=now.second+get_point[go.first.first.bottom];\


                      q.push(go);\


                   }


                   pair<pair<Cube,pair<int,int> >,int> go;


                   letusgo(left,-1,0);


                   letusgo(right,1,0);


                   letusgo(up,0,1);


                   letusgo(down,0,-1);


                   #undef letusgo


                }


                if (now.first.second==t) break;


                q.pop();


                #undef getdist


          }


          stack<pre_type> s;


          s.push(make_pair(q.top().first.second,


                           get_id[q.top().first.first.top]


                                 [q.top().first.first.left]));


          for (pre_type from=make_pair(f,get_id[start.top][start.left]);


               s.top()!=from;)


          {


              pre_type getpre=pre[s.top().first.first]


                        [s.top().first.second]


                        [s.top().second];


              s.push(getpre);


          }


          cout<<q.top().second<<” “;


          while (!s.empty())


          {


                cout<<char(s.top().first.first+’a’)


                    <<char(s.top().first.second+’1′);


                s.pop();


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


                else cout<<” “;


          }


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

URAL1015[Test the Difference!]

水题,先把1转到顶部,在使左边尽量小,然后,这个骰子就固定了。然后再编码一下。因为顶都为1,所以就不管了,然后就剩下几个6进制编码。如果两个骰子经过这样的处理后,编码相同,则他们相同。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-15


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <sstream>


using std::stringstream;


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


 


struct Dice


{


       static const int SIDE=6;


       static const int TURN=4;


       int left,//the number of points on the left side of the die,


           right,//then on the right side,


           top,//on the top,


           forward,//on the forward side,


           bottom,//on the bottom


           backward;//and on the backward side


       int id;


       void read()


       {


            cin>>left>>right>>top>>forward>>bottom>>backward;


       }


       inline


       void swap(int& a,int& b,int& c,int& d)


       {


            int s=a;


            a=b;


            b=c;


            c=d;


            d=s;


       }


       inline


       void turnLR()


       {


            swap(top,backward,bottom,forward);


       }


       inline


       void turnTB()


       {


            swap(right,forward,left,backward);


       }


       inline


       void turnFB()


       {


            swap(right,top,left,bottom);


       }


       void getid()


       {


            //let top=1


            for (int i=0;(top!=1)&&(i<TURN);i++)


                turnTB();


            for (int i=0;(top!=1)&&(i<TURN);i++)


                turnLR();


            for (int i=0;(top!=1)&&(i<TURN);i++)


                turnFB();


            //assert(top==1);


           


            //let left min


            int min_left=SIDE;


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


            {


                turnTB();


                if (min_left>left) min_left=left;


            }


            for (int i=0;(left!=min_left)&&(i<TURN);i++)


                turnTB();


           


            id=((((left)*SIDE+right)*SIDE+forward)*SIDE+bottom)*SIDE+backward;


       }


};


 


class Application


{


      int N;


      vector<Dice> dice;


      public:


      Application()


      {


                    cin>>N;


                    dice.resize(N);


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


                        dice[i].read();


      }


      int run()


      {


          map<int,vector<int> > idToIndex;


          map<int,vector<int> >::iterator it;


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


          {


              dice[i].getid();


              idToIndex[dice[i].id].push_back(i+1);


          }


         


          cout<<idToIndex.size()<<endl;


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


              if ((it=idToIndex.find(dice[i].id))!=idToIndex.end())


              {


                 for (int j=0;j<it->second.size();j++)


                     cout<<it->second[j]<<char((j+1==it->second.size())?’\n’:’ ‘);


                 idToIndex.erase(it);


              }


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


URAL1014[The Product of Digits]

水题,就是要注意一下细节。特殊对待N=0和1的情况。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-13


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <sstream>


using std::stringstream;


#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


{


      static const int BASE=10;


      int N;


      vector<int> counter;


      public:


      Application()


                   :counter(BASE,0)


      {


                    cin>>N;


      }


      int run()


      {


          if (N==0) cout<<10<<endl;


          else if (N==1) cout<<1<<endl;


          else


          {


              for (int i=BASE-1;i>1;i–)


                  while (N%i==0)


                  {


                        N/=i;


                        counter[i]++;


                  }


              if (N!=1) cout<<-1<<endl;


              else


              {


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


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


                          cout<<i;


                  cout<<endl;


              }


          }


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


URAL1013[K-based numbers. Version 3]

URAL1009URAL1012的加强版,需要高精再加优化。

sum{f[i],0<=i<=N/2}
f[i]=C(N-i,i)*(K-1)^(N-i)
f[i-1]=C(N-i+1,i-1)*(K-1)^(N-i+1)
f[i]/f[i-1]=C(N-i,i)/C(N-i+1,i-1)/(K-1)
=((N-i)!/(N-i+1)!) * ((N-i*2+2)!/(N-i*2)!) * ((i-1)!/i!) / (K-1)
=1/(N-i+1)         * (N-i*2+2)*(N+i*2+1)   * 1/i           / (K-1)
=((N-i*2+2)*(N+i*2+1))/((N-i+1)*i*(K-1))
f[i]=f[i-1]*((N-i*2+2)*(N+i*2+1))/((N-i+1)*i*(K-1))

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-13

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <sstream>

using std::stringstream;

#include <iomanip>

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

{

      static const int BASE=10000;

      vector<int> d;

      public:

      BigNumber(int value=0)

                    :d(1,value)

      {

                    //assert(value<BASE);

      }

      friend BigNumber operator+(const BigNumber& a,const BigNumber& b)

      {

             BigNumber c;

             c.d.resize(a.d.size()>b.d.size()?a.d.size():b.d.size());

             int over=0;

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

                 if (i<a.d.size()&&i<b.d.size())

                 {

                    c.d[i]=(a.d[i]+b.d[i]+over)%BASE;

                    over=(a.d[i]+b.d[i]+over)/BASE;

                 }

                 else if (i<a.d.size())

                 {

                    c.d[i]=(a.d[i]+over)%BASE;

                    over=(a.d[i]+over)/BASE;

                 }

                 else if (i<b.d.size())

                 {

                    c.d[i]=(b.d[i]+over)%BASE;

                    over=(b.d[i]+over)/BASE;

                 }

             if (over) c.d.push_back(over);

             return c;

      }

      BigNumber& operator*=(int mul)

      {

                 int over=0;

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

                 {

                     int old=d[i];

                     d[i]=(old*mul+over)%BASE;

                     over=(old*mul+over)/BASE;

                 }

                 if (over) d.push_back(over);

                 return *this;

      }

      BigNumber& operator/=(int div)

      {

                 int rest=0;

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

                 {

                     int old=d[i];

                     d[i]=(rest*BASE+old)/div;

                     rest=(rest*BASE+old)%div;

                 }

                 if (d[d.size()-1]==0) d.resize(d.size()-1);

                 return *this;

      }

      void print()

      {

           cout<<d[d.size()-1];

           for (int i=d.size()-11;i>=0;i–)

               cout<<std::setfill(‘0’)<<std::setw(4)<<d[i]<<std::setw(1)<<std::setfill(‘ ‘);

           cout<<endl;

      }

};

 

class Application

{

      int N,K;

      public:

      Application()

      {

                    cin>>N>>K;

      }

      int run()

      {

          //sum{(N-i)!/(((N-i*2)!)*(i!))*((K-1)^(N-i)), 0<=i<=N/2}

          //f[i]=C(N-i,i)*(K-1)^(N-i)

          //f[i-1]=C(N-i+1,i-1)*(K-1)^(N-i+1)

         

          //f[i]/f[i-1]=C(N-i,i)/C(N-i+1,i-1)/(K-1)

          //           =((N-i)!/(N-i+1)!) * ((N-i*2+2)!/(N-i*2)!) * ((i-1)!/i!) / (K-1)

          //           =1/(N-i+1)         * (N-i*2+2)*(N+i*2+1)   * 1/i           / (K-1)

          //           =((N-i*2+2)*(N+i*2+1))/((N-i+1)*i*(K-1))

          //f[i]=f[i-1]*((N-i*2+2)*(N+i*2+1))/((N-i+1)*i*(K-1))

          BigNumber answer(0);

          BigNumber get(1);

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

          {

              if (i==0)

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

                     get*=K-1;

              else

              {

                  get*=(N-i*2+2);

                  get*=(N-i*2+1);

                  get/=(N-i+1);

                  get/=(i);

                  get/=K-1;

              }

              answer=answer+get;

          }

          answer.print();

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

URAL1012[K-based numbers. Version 2]

题目同URAL1009,但是数据范围变了,需要用高精度。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-13


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <sstream>


using std::stringstream;


#include <iomanip>


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


{


      static const int BASE=10000;


      vector<int> d;


      public:


      BigNumber(int value=0)


                    :d(1,value)


      {


                    //assert(value<BASE);


      }


      friend BigNumber operator+(const BigNumber& a,const BigNumber& b)


      {


             BigNumber c;


             c.d.resize(a.d.size()>b.d.size()?a.d.size():b.d.size());


             int over=0;


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


                 if (i<a.d.size()&&i<b.d.size())


                 {


                    c.d[i]=(a.d[i]+b.d[i]+over)%BASE;


                    over=(a.d[i]+b.d[i]+over)/BASE;


                 }


                 else if (i<a.d.size())


                 {


                    c.d[i]=(a.d[i]+over)%BASE;


                    over=(a.d[i]+over)/BASE;


                 }


                 else if (i<b.d.size())


                 {


                    c.d[i]=(b.d[i]+over)%BASE;


                    over=(b.d[i]+over)/BASE;


                 }


             if (over) c.d.push_back(over);


             return c;


      }


      BigNumber& operator*=(int mul)


      {


                 int over=0;


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


                 {


                     int old=d[i];


                     d[i]=(old*mul+over)%BASE;


                     over=(old*mul+over)/BASE;


                 }


                 if (over) d.push_back(over);


                 return *this;


      }


      BigNumber& operator/=(int div)


      {


                 int rest=0;


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


                 {


                     int old=d[i];


                     d[i]=(rest*BASE+old)/div;


                     rest=(rest*BASE+old)%div;


                 }


                 if (d[d.size()-1]==0) d.resize(d.size()-1);


                 return *this;


      }


      void print()


      {


           cout<<d[d.size()-1];


           for (int i=d.size()-11;i>=0;i–)


               cout<<std::setfill(‘0’)<<std::setw(4)<<d[i]<<std::setw(1)<<std::setfill(‘ ‘);


           cout<<endl;


      }


};


 


class Application


{


      int N,K;


      public:


      Application()


      {


                    cin>>N>>K;


      }


      int run()


      {


          BigNumber answer(0);


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


          {


              BigNumber get(1);


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


                  get*=j;


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


                  get/=j;


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


                  get/=j;


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


                  get*=K-1;


              answer=answer+get;


          }


          answer.print();


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 

URAL1011[Conductors]

水题,就是精度要注意一下。(哎,害我WA3次,重写1次)


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-13


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <sstream>


using std::stringstream;


#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


{


      static const int oo=~(1<<31);


      double P,Q;


      public:


      Application()


      {


                    cin>>P>>Q;


      }


      int run()


      {


          int Pi=int(P*double(100)+0.5);


          int Qi=int(Q*double(100)+0.5);


         


          int answer;


          for (answer=1;;answer++)


          {


              int min=answer*Pi;


              int max=answer*Qi;


              int l=min/100001;


              int r=max/10000+1;


              int counter=0;


              for (int i=l;i<=r;i++)


                  if ((i*10000>min)&&(i*10000<max))


                     counter++;


              if (counter)


                 break;


          }


          cout<<answer<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}



 

URAL1010[Discrete Function]

可以证明这样的两个点一定是相邻的。
如图:
URAL1010[Discrete Function] - 天之骄子 - 天之骄子的家


明显红线没有绿线优,绿线又没有紫线优,如此一直推,会发现最后一定是两个相邻点。
CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-13


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <sstream>


using std::stringstream;


#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


{


      static const int oo=~(1<<31);


      int N;


      vector<double> f;


      public:


      Application()


      {


                   cin>>N;


                   f.resize(N);


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


                       cin>>f[i];


      }


      int run()


      {


          //max{abs(f[i-1]-f[i]) ,2<=i<=N}


          double max=-oo;


          int max_i;


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


          {


              double abs_k=f[i-1]>f[i]?f[i-1]-f[i]:f[i]-f[i-1];


              if (abs_k>max)


              {


                 max=abs_k;


                 max_i=i;


              }


          }


          cout<<max_i+11<<” “<<max_i+1<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}