SRM 408(1-250pt, 1-500pt)-白红宇

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

阅读量：7113 次

发布时间：2019-06-28

本文共 9819 字，大约阅读时间需要 32 分钟。

DIV1 250pt

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

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

tag:simulation, greedy

1 // BEGIN CUT HERE  2 /*  3  * Author:  plum rain  4  * score :  5  */  6 /*  7   8  */  9 // END CUT HERE 10 #line 11 "OlympicCandles.cpp" 11 #include 
      
        12 #include 
       
         13 #include 
        
          14 #include 
         
           15 #include 
          
            16 #include 
           
             17 #include 
            
              18 #include 
             
               19 #include 
              
                20 #include 
               
                 21 #include 
                
                  22 #include 
                 
                   23 #include 
                  
                    24 #include 
                   
                     25 #include 
                    
                      26 #include 
                     
                       27 #include 
                      
                        28 #include 
                       
                         29 #include 
                        
                          30 #include 
                         
                           31 #include 
                           32 #include 
                           
                             33 #include 
                            
                              34 35 using namespace std; 36 37 #define clr0(x) memset(x, 0, sizeof(x)) 38 #define clr1(x) memset(x, -1, sizeof(x)) 39 #define pb push_back 40 #define sz(v) ((int)(v).size()) 41 #define all(t) t.begin(),t.end() 42 #define zero(x) (((x)>0?(x):-(x))

vi; 49 typedef vector

vs; 50 typedef vector

vd; 51 typedef pair

pii; 52 typedef long long int64; 53 54 const double eps = 1e-8; 55 const double PI = atan(1.0)*4; 56 const int inf = 2139062143 / 2; 57 58 bool cmp(int a, int b) 59 { 60 return a > b; 61 } 62 63 class OlympicCandles 64 { 65 public: 66 int numberOfNights(vector

can){ 67 int ans = 1; 68 while (ans <= 55){ 69 if (ans > sz(can)) return sz(can); 70 sort(all(can), cmp); 71 for (int i = 0; i < ans; ++ i){ 72 if (can[i]) can[i] --; 73 else return ans - 1; 74 } 75 ++ ans; 76 } 77 return ans; 78 } 79 80 // BEGIN CUT HERE 81 public: 82 void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); } 83 private: 84 template

string print_array(const vector

&V) { ostringstream os; os << "{ "; for (typename vector

::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); } 85 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; } } 86 void test_case_0() { int Arr0[] = { 2, 2, 2}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 3; verify_case(0, Arg1, numberOfNights(Arg0)); } 87 void test_case_1() { int Arr0[] = { 2, 2, 2, 4}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 4; verify_case(1, Arg1, numberOfNights(Arg0)); } 88 void test_case_2() { int Arr0[] = { 5, 2, 2, 1}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 3; verify_case(2, Arg1, numberOfNights(Arg0)); } 89 void test_case_3() { int Arr0[] = { 1, 2, 3, 4, 5, 6}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 6; verify_case(3, Arg1, numberOfNights(Arg0)); } 90 void test_case_4() { int Arr0[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 4; verify_case(4, Arg1, numberOfNights(Arg0)); } 91 92 // END CUT HERE 93 94 }; 95 96 // BEGIN CUT HERE 97 int main() 98 { 99 // freopen( "a.out" , "w" , stdout ); 100 OlympicCandles ___test;101 ___test.run_test(-1);102 return 0;103 }104 // END CUT HERE

View Code

DIV1 500pt

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

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

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

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

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

tag:greedy, tree

1 // BEGIN CUT HERE  2 /*  3  * Author:  plum rain  4  * score :  5  */  6 /*  7   8  */  9 // END CUT HERE 10 #line 11 "CandyGame.cpp" 11 #include 
      
        12 #include 
       
         13 #include 
        
          14 #include 
         
           15 #include 
          
            16 #include 
           
             17 #include 
            
              18 #include 
             
               19 #include 
              
                20 #include 
               
                 21 #include 
                
                  22 #include 
                 
                   23 #include 
                  
                    24 #include 
                   
                     25 #include 
                    
                      26 #include 
                     
                       27 #include 
                      
                        28 #include 
                       
                         29 #include 
                        
                          30 #include 
                         
                           31 #include 
                           32 #include 
                           
                             33 #include 
                            
                              34 35 using namespace std; 36 37 #define clr0(x) memset(x, 0, sizeof(x)) 38 #define clr1(x) memset(x, -1, sizeof(x)) 39 #define pb push_back 40 #define sz(v) ((int)(v).size()) 41 #define all(t) t.begin(),t.end() 42 #define zero(x) (((x)>0?(x):-(x))

vi; 49 typedef vector

vs; 50 typedef vector

vd; 51 typedef pair

pii; 52 typedef long long int64; 53 54 const double eps = 1e-8; 55 const double PI = atan(1.0)*4; 56 const int inf = 2139062143 / 2; 57 const int maxx = 2000000000; 58 59 class CandyGame 60 { 61 public: 62 vs g; 63 int64 ans; 64 vi son[100]; 65 int64 an[100]; 66 int len[100]; 67 bool v[100]; 68 69 void dfs (int tar) 70 { 71 len[tar] = 0; v[tar] = 1; 72 for (int i = 0; i < sz(g); ++ i) 73 if (g[i][tar] == 'Y' && !v[i]){ 74 son[tar].pb (i); 75 dfs (i); 76 len[tar] = max(len[tar], len[i]); 77 } 78 ++ len[tar]; 79 } 80 81 void gao(int tar, int64 num) 82 { 83 bool ok = 0; 84 an[tar] = num > maxx ? -1 : num; 85 for (int i = 0; i < sz(son[tar]); ++ i){ 86 if (ok || len[son[tar][i]]+1 != len[tar]) 87 gao (son[tar][i], 1); 88 else 89 ok = 1, gao (son[tar][i], 2*num>1 ? 2*num : 1); 90 91 if (an[tar] != -1){ 92 if(an[son[tar][i]] == -1) an[tar] = -1; 93 else an[tar] += an[son[tar][i]]; 94 95 if (an[tar] > maxx) an[tar] = -1; 96 } 97 } 98 } 99 100 int maximumCandy(vector

G, int tar){101 g = G;102 clr0 (v);103 for (int i = 0; i < sz(g); ++ i) son[i].clear();104 dfs (tar);105 for (int i = 0; i < sz(g); ++ i) if (!v[i]) return -1;106 if (sz(g) == 2) return 2;107 if (sz(g) == 1) return 0;108 gao(tar, 0);109 return an[tar];110 }111 112 // BEGIN CUT HERE113 public:114 void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }115 //void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_1();}116 private:117 template

string print_array(const vector

&V) { ostringstream os; os << "{ "; for (typename vector

::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }118 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; } }119 void test_case_0() { string Arr0[] = { "NYN", "YNY", "NYN"}; vector

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

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 2; int Arg2 = 3; verify_case(1, Arg2, maximumCandy(Arg0, Arg1)); }121 void test_case_2() { string Arr0[] = { "NYYY", "YNNN", "YNNN", "YNNN"}; vector

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

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 1; int Arg2 = 4; verify_case(3, Arg2, maximumCandy(Arg0, Arg1)); }123 void test_case_4() { string Arr0[] = { "NYNNNYN",124 "YNYNYNN",125 "NYNYNNN",126 "NNYNNNN",127 "NYNNNNN",128 "YNNNNNY",129 "NNNNNYN"}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 11; verify_case(4, Arg2, maximumCandy(Arg0, Arg1)); }130 void test_case_5() { string Arr0[] = { "NYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",131 "YNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",132 "NYNYNNNNNNNNNNNNNNNNNNNNNNNNNNNN",133 "NNYNYNNNNNNNNNNNNNNNNNNNNNNNNNNN",134 "NNNYNYNNNNNNNNNNNNNNNNNNNNNNNNNN",135 "NNNNYNYNNNNNNNNNNNNNNNNNNNNNNNNN",136 "NNNNNYNYNNNNNNNNNNNNNNNNNNNNNNNN",137 "NNNNNNYNYNNNNNNNNNNNNNNNNNNNNNNN",138 "NNNNNNNYNYNNNNNNNNNNNNNNNNNNNNNN",139 "NNNNNNNNYNYNNNNNNNNNNNNNNNNNNNNN",140 "NNNNNNNNNYNYNNNNNNNNNNNNNNNNNNNN",141 "NNNNNNNNNNYNYNNNNNNNNNNNNNNNNNNN",142 "NNNNNNNNNNNYNYNNNNNNNNNNNNNNNNNN",143 "NNNNNNNNNNNNYNYNNNNNNNNNNNNNNNNN",144 "NNNNNNNNNNNNNYNYNNNNNNNNNNNNNNNN",145 "NNNNNNNNNNNNNNYNYNNNNNNNNNNNNNNN",146 "NNNNNNNNNNNNNNNYNYNNNNNNNNNNNNNN",147 "NNNNNNNNNNNNNNNNYNYNNNNNNNNNNNNN",148 "NNNNNNNNNNNNNNNNNYNYNNNNNNNNNNNN",149 "NNNNNNNNNNNNNNNNNNYNYNNNNNNNNNNN",150 "NNNNNNNNNNNNNNNNNNNYNYNNNNNNNNNN",151 "NNNNNNNNNNNNNNNNNNNNYNYNNNNNNNNN",152 "NNNNNNNNNNNNNNNNNNNNNYNYNNNNNNNN",153 "NNNNNNNNNNNNNNNNNNNNNNYNYNNNNNNN",154 "NNNNNNNNNNNNNNNNNNNNNNNYNYNNNNNN",155 "NNNNNNNNNNNNNNNNNNNNNNNNYNYNNNNN",156 "NNNNNNNNNNNNNNNNNNNNNNNNNYNYNNNN",157 "NNNNNNNNNNNNNNNNNNNNNNNNNNYNYNNN",158 "NNNNNNNNNNNNNNNNNNNNNNNNNNNYNYNN",159 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNYNYN",160 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNY",161 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYN"}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = -1; verify_case(5, Arg2, maximumCandy(Arg0, Arg1)); }162 163 // END CUT HERE164 165 };166 167 // BEGIN CUT HERE168 int main()169 {170 //freopen( "a.out" , "w" , stdout ); 171 CandyGame ___test;172 ___test.run_test(-1);173 return 0;174 }175 // END CUT HERE

View Code

转载于:https://www.cnblogs.com/plumrain/p/srm_408.html