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

}