SRM 408(1-250pt, 1-500pt)

2023-02-12 09:42:31

DIV1 250pt

题意：每天晚上需要点蜡烛，且每晚蜡烛燃烧1cm，第i天晚上需要点i根蜡烛。第一天白天的时候，拥有一些蜡烛，用vector<int>can表示他们的长度，问最多能烧几个晚上。

解法：模拟+贪心，每次烧长度最长的k支蜡烛即可。

tag:simulation, greedy

 // BEGIN CUT HERE

 /*

  * Author:  plum rain

  * score :

  */

 /*

  */

 // END CUT HERE

 #line 11 "OlympicCandles.cpp"

 #include <sstream>

 #include <stdexcept>

 #include <functional>

 #include <iomanip>

 #include <numeric>

 #include <fstream>

 #include <cctype>

 #include <iostream>

 #include <cstdio>

 #include <vector>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <cstdlib>

 #include <set>

 #include <queue>

 #include <bitset>

 #include <list>

 #include <string>

 #include <utility>

 #include <map>

 #include <ctime>

 #include <stack>

 using namespace std;

 #define clr0(x) memset(x, 0, sizeof(x))

 #define clr1(x) memset(x, -1, sizeof(x))

 #define pb push_back

 #define sz(v) ((int)(v).size())

 #define all(t) t.begin(),t.end()

 #define zero(x) (((x)>0?(x):-(x))<eps)

 #define out(x) cout<<#x<<":"<<(x)<<endl

 #define tst(a) cout<<a<<" "

 #define tst1(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 typedef vector<int> vi;

 typedef vector<string> vs;

 typedef vector<double> vd;

 typedef pair<int, int> pii;

 typedef long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int inf =  / ;

 bool cmp(int a, int b)

 {

     return a > b;

 }

 class OlympicCandles

 {

     public:

         int numberOfNights(vector <int> can){

             int ans = ;

             while (ans <= ){

                 if (ans > sz(can)) return sz(can);

                 sort(all(can), cmp);

                 for (int i = ; i < ans; ++ i){

                     if (can[i]) can[i] --;

                     else return ans - ;

                 }

                 ++ ans;

             }

             return ans;

         }

 // BEGIN CUT HERE

     public:

     void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); if ((Case == -) || (Case == )) test_case_4(); }

     private:

     template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }

     void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }

     void test_case_0() { int Arr0[] = {, , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, numberOfNights(Arg0)); }

     void test_case_1() { int Arr0[] = {, , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, numberOfNights(Arg0)); }

     void test_case_2() { int Arr0[] = {, , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, numberOfNights(Arg0)); }

     void test_case_3() { int Arr0[] = {, , , , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, numberOfNights(Arg0)); }

     void test_case_4() { int Arr0[] = {, , , , , , , , , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, numberOfNights(Arg0)); }

 // END CUT HERE

 };

 // BEGIN CUT HERE

 int main()

 {

 //    freopen( "a.out" , "w" , stdout );

     OlympicCandles ___test;

     ___test.run_test(-);

        return ;

 }

 // END CUT HERE

DIV1 500pt

题意：做一个游戏，在一个无向图上，每个点上有一些糖果，每次可以选择任意一个糖果数大等于2的点i，拿出其中两个糖果，吃掉一个，将剩下的一个放在i点的一个相邻点上。初始时，每个点上有一些糖果，有一个特定点k，要求无论如何操作，都不能使k点出现有且仅有一个糖果的情况，问初始时图上最多有多少个糖果。如果可以有多余2*10^9个糖果，直接输出-1。

解法：首先，若图不联通，则可以放无数糖果，输出-1。

　　　考虑末态，要使糖果数量最多，末态肯定为除了k点，每个点一个糖果。考虑末态向初态转移。将无向图转化成以k点为根的树，则每个父亲节点的1个糖果可以有它的某个子节点的两个糖果变出来，所以，应该尽量将所有糖果都放在非叶子节点。下面考虑，从树的顶端把所有糖果放回底端，即是考虑这个游戏的逆过程。

　　　如果某个父亲节点仅有一个子节点，直接将父亲节点的k个糖果变为子节点的2*k个糖果即可。若父亲节点有多个子节点，有两种处理方式，父亲节点的k个糖果均由一个某一个子节点转移得到，或者由多个子节点转移得到。显然，前者更优。那么，要选择哪个子节点呢？子树深度最深的那个自己子节点。

　　　至此，问题得到完整解决。这是一道想法非常自然，而且所用结论均为简单贪心的题，稍微想一下即可明白。

tag:greedy, tree

 // BEGIN CUT HERE

 /*

  * Author:  plum rain

  * score :

  */

 /*

  */

 // END CUT HERE

 #line 11 "CandyGame.cpp"

 #include <sstream>

 #include <stdexcept>

 #include <functional>

 #include <iomanip>

 #include <numeric>

 #include <fstream>

 #include <cctype>

 #include <iostream>

 #include <cstdio>

 #include <vector>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <cstdlib>

 #include <set>

 #include <queue>

 #include <bitset>

 #include <list>

 #include <string>

 #include <utility>

 #include <map>

 #include <ctime>

 #include <stack>

 using namespace std;

 #define clr0(x) memset(x, 0, sizeof(x))

 #define clr1(x) memset(x, -1, sizeof(x))

 #define pb push_back

 #define sz(v) ((int)(v).size())

 #define all(t) t.begin(),t.end()

 #define zero(x) (((x)>0?(x):-(x))<eps)

 #define out(x) cout<<#x<<":"<<(x)<<endl

 #define tst(a) cout<<a<<" "

 #define tst1(a) cout<<#a<<endl

 #define CINBEQUICKER std::ios::sync_with_stdio(false)

 typedef vector<int> vi;

 typedef vector<string> vs;

 typedef vector<double> vd;

 typedef pair<int, int> pii;

 typedef long long int64;

 const double eps = 1e-;

 const double PI = atan(1.0)*;

 const int inf =  / ;

 const int maxx = ; 

 class CandyGame

 {

     public:

         vs g;

         int64 ans;

         vi son[];

         int64 an[];

         int len[];

         bool v[];

         void dfs (int tar)

         {

             len[tar] = ; v[tar] = ;

             for (int i = ; i < sz(g); ++ i)

                 if (g[i][tar] == 'Y' && !v[i]){

                     son[tar].pb (i);

                     dfs (i);

                     len[tar] = max(len[tar], len[i]);

                 }

             ++ len[tar];

         }

         void gao(int tar, int64 num)

         {

             bool ok = ;

             an[tar] = num > maxx ? - : num;

             for (int i = ; i < sz(son[tar]); ++ i){

                 if (ok || len[son[tar][i]]+ != len[tar])

                     gao (son[tar][i], );

                 else

                     ok = , gao (son[tar][i], *num> ? *num : );

                 if (an[tar] != -){

                     if(an[son[tar][i]] == -) an[tar] = -;

                     else an[tar] += an[son[tar][i]];

                     if (an[tar] > maxx) an[tar] = -;

                 }

             }

         }

         int maximumCandy(vector <string> G, int tar){

             g = G;

             clr0 (v);

             for (int i = ; i < sz(g); ++ i) son[i].clear();

             dfs (tar);

             for (int i = ; i < sz(g); ++ i) if (!v[i]) return -;

             if (sz(g) == ) return ;

             if (sz(g) == ) return ;

             gao(tar, );

             return an[tar];

         }

 // BEGIN CUT HERE

     public:

     void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); if ((Case == -) || (Case == )) test_case_4(); if ((Case == -) || (Case == )) test_case_5(); }

     //void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_1();}

     private:

     template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }

     void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }

     void test_case_0() { string Arr0[] = {"NYN", "YNY", "NYN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, maximumCandy(Arg0, Arg1)); }

     void test_case_1() { string Arr0[] = {"NYN", "YNY", "NYN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, maximumCandy(Arg0, Arg1)); }

     void test_case_2() { string Arr0[] = {"NYYY", "YNNN", "YNNN", "YNNN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, maximumCandy(Arg0, Arg1)); }

     void test_case_3() { string Arr0[] = {"NYYY", "YNNN", "YNNN", "YNNN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, maximumCandy(Arg0, Arg1)); }

     void test_case_4() { string Arr0[] = {"NYNNNYN",

  "YNYNYNN",

  "NYNYNNN",

  "NNYNNNN",

  "NYNNNNN",

  "YNNNNNY",

  "NNNNNYN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, maximumCandy(Arg0, Arg1)); }

     void test_case_5() { string Arr0[] = {"NYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",

  "YNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",

  "NYNYNNNNNNNNNNNNNNNNNNNNNNNNNNNN",

  "NNYNYNNNNNNNNNNNNNNNNNNNNNNNNNNN",

  "NNNYNYNNNNNNNNNNNNNNNNNNNNNNNNNN",

  "NNNNYNYNNNNNNNNNNNNNNNNNNNNNNNNN",

  "NNNNNYNYNNNNNNNNNNNNNNNNNNNNNNNN",

  "NNNNNNYNYNNNNNNNNNNNNNNNNNNNNNNN",

  "NNNNNNNYNYNNNNNNNNNNNNNNNNNNNNNN",

  "NNNNNNNNYNYNNNNNNNNNNNNNNNNNNNNN",

  "NNNNNNNNNYNYNNNNNNNNNNNNNNNNNNNN",

  "NNNNNNNNNNYNYNNNNNNNNNNNNNNNNNNN",

  "NNNNNNNNNNNYNYNNNNNNNNNNNNNNNNNN",

  "NNNNNNNNNNNNYNYNNNNNNNNNNNNNNNNN",

  "NNNNNNNNNNNNNYNYNNNNNNNNNNNNNNNN",

  "NNNNNNNNNNNNNNYNYNNNNNNNNNNNNNNN",

  "NNNNNNNNNNNNNNNYNYNNNNNNNNNNNNNN",

  "NNNNNNNNNNNNNNNNYNYNNNNNNNNNNNNN",

  "NNNNNNNNNNNNNNNNNYNYNNNNNNNNNNNN",

  "NNNNNNNNNNNNNNNNNNYNYNNNNNNNNNNN",

  "NNNNNNNNNNNNNNNNNNNYNYNNNNNNNNNN",

  "NNNNNNNNNNNNNNNNNNNNYNYNNNNNNNNN",

  "NNNNNNNNNNNNNNNNNNNNNYNYNNNNNNNN",

  "NNNNNNNNNNNNNNNNNNNNNNYNYNNNNNNN",

  "NNNNNNNNNNNNNNNNNNNNNNNYNYNNNNNN",

  "NNNNNNNNNNNNNNNNNNNNNNNNYNYNNNNN",

  "NNNNNNNNNNNNNNNNNNNNNNNNNYNYNNNN",

  "NNNNNNNNNNNNNNNNNNNNNNNNNNYNYNNN",

  "NNNNNNNNNNNNNNNNNNNNNNNNNNNYNYNN",

  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNYNYN",

  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNY",

  "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = -; verify_case(, Arg2, maximumCandy(Arg0, Arg1)); }

 // END CUT HERE

 };

 // BEGIN CUT HERE

 int main()

 {

     //freopen( "a.out" , "w" , stdout );

     CandyGame ___test;

     ___test.run_test(-);

        return ;

 }

 // END CUT HERE
上一篇：PHP和js判断访问设备是否是微信浏览器实例


下一篇：在windows2012&2008中设置防火墙允许filezilla的passive模式