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