URAL1091[Tmutarakan exams]

看到题目的数据规模,马上想到直接搜索。但是TLE#2,然后加入一个减枝,然后TLE#8,然后优化常数一次TLE#8,然后用构造法做AC,然后在搜索中加入又一个减枝,然后又一次AC。


然后,只给出搜索的代码。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-4-13


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


      vector<int> a;


      int answer;


      void search(int begin,int rest,int pre_gcd)


      {


           if (answer==10000) return;


           if (rest)


           {


              rest–;


              for (a[rest]=begin;a[rest]<=S;)


              {


                  int _a=a[rest],_b=pre_gcd;


                  int _t;


                  while (_b) _t=_a,_b=_t%(_a=_b);


                  a[rest]++;


                  if (_a!=1&&(S-a[rest]+1>=rest))


                  {


                     search(a[rest],rest,_a);


                     if (answer==10000) return;


                  }


              }


           }


           else answer++;


      }


      public:


      Application()


      {


                   cin>>K>>S;


      }


      int run()


      {


          answer=0;


          a.resize(K);


          search(2,K,0);


          cout<<answer<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

留下评论

电子邮件地址不会被公开。