DIV1 250pt
题意：每个员工可以有几个直系上司，也可以有几个直系下属。没有直系下属的人工资为1，有直系下属的人工资为所有直系下属工资之和。求所有人工资之和。人数 <= 50。
解法：直接dfs一遍求出所有人工资就好。(官方题解说该问题满足拓补序，用dfs做拓补序再求)
tag:dfs
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "CorporationSalary.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 = / ; vi pat[];
bool son[];
int64 an[]; void dfs (int x)
{
int64 &ret = an[x];
if (ret) return; int n = sz(pat[x]);
if (!n){
an[x] = ; return;
} for (int i = ; i < n; ++ i){
dfs (pat[x][i]);
ret += an[pat[x][i]];
}
} class CorporationSalary
{
public:
long long totalSalary(vector <string> v){
clr0 (an); clr0 (son);
int n = sz(v);
for (int i = ; i < n; ++ i)
pat[i].clear(); for (int i = ; i < n; ++ i)
for (int j = ; j < n; ++ j)
if (v[i][j] == 'Y')
pat[i].pb (j), son[j] = ; for (int i = ; i < n; ++ i)
if (!son[i]) dfs (i);
int64 ans = ;
for (int i = ; i < n; ++ i)
ans += an[i];
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 long long &Expected, const long long &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[] = {"N"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); long long Arg1 = 1LL; verify_case(, Arg1, totalSalary(Arg0)); }
void test_case_1() { string Arr0[] = {"NNYN",
"NNYN",
"NNNN",
"NYYN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); long long Arg1 = 5LL; verify_case(, Arg1, totalSalary(Arg0)); }
void test_case_2() { string Arr0[] = {"NNNNNN",
"YNYNNY",
"YNNNNY",
"NNNNNN",
"YNYNNN",
"YNNYNN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); long long Arg1 = 17LL; verify_case(, Arg1, totalSalary(Arg0)); }
void test_case_3() { string Arr0[] = {"NYNNYN",
"NNNNNN",
"NNNNNN",
"NNYNNN",
"NNNNNN",
"NNNYYN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); long long Arg1 = 8LL; verify_case(, Arg1, totalSalary(Arg0)); }
void test_case_4() { string Arr0[] = {"NNNN",
"NNNN",
"NNNN",
"NNNN"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); long long Arg1 = 4LL; verify_case(, Arg1, totalSalary(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
CorporationSalary ___test;
___test.run_test(-);
return ;
}
// END CUT HERE
DIV1 500pt
题意：平面上有很多点，A和B轮流将点染色，A将点染为红色，B将点染为蓝色。染完所有颜色后最终的score为所有两端颜色不一样的边的长度和(一端为红色，一端为蓝色)。B想使score尽量小，A想使score尽量大，两人都采用最优策略，A先手，问最终score的为多少。点数 <= 12。
解法：这道题最关键的是注意到两点：1、最终score之和染色结果有关，和染色顺序有关；2、在忽略染色顺序的情况下，每个点只有三种状态，无色，红色，蓝色。O(12^3)的复杂度完全能接受。也就是说，只需要dfs加记忆化就好。
tag：dfs, memorization
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "PointsGame.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 = / ; int n;
bool flag[];
vi an, px, py;
map<vi, double> mp; double gao(int x)
{
//out (x);
//for (int i = 0; i < n; ++ i)
//tst(i), out (an[i]);
if (mp.count(an)) return mp[an]; if(x == n){
double ret = ;
for (int i = ; i < n; ++ i) if (an[i] == )
for (int j = ; j < n; ++ j) if (an[j] == )
ret += sqrt((px[i]-px[j])*(px[i]-px[j]) + (py[i]-py[j])*(py[i]-py[j]) + 0.0);
mp[an] = ret;
return ret;
} double ret = x & ? inf : ;
for (int i = ; i < n; ++ i) if (!an[i]){
an[i] = (x & ) + ;
double tmp = gao(x + );
//out (tmp);
if (x & ) ret = min(tmp, ret);
else ret = max(tmp, ret);
an[i] = ;
}
mp[an] = ret;
return ret;
} class PointsGame
{
public:
double gameValue(vector <int> PX, vector <int> PY){
px = PX; py = PY;
n = sz(px);
for (int i = ; i < n; ++ i) an.pb ();
clr0 (flag); mp.clear();
return gao();
} // 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(); }
//void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0();}
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 double &Expected, const double &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 Arr1[] = {,}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); double Arg2 = 1.0; verify_case(, Arg2, gameValue(Arg0, Arg1)); }
void test_case_1() { int Arr0[] = {,,,}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {,,,}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); double Arg2 = 12.198039027185569; verify_case(, Arg2, gameValue(Arg0, Arg1)); }
void test_case_2() { int Arr0[] = {,,,}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {,,,}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); double Arg2 = 12.0; verify_case(, Arg2, gameValue(Arg0, Arg1)); }
void test_case_3() { int Arr0[] = {,,,}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arr1[] = {,,,}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); double Arg2 = 6.0; verify_case(, Arg2, gameValue(Arg0, Arg1)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
PointsGame ___test;
___test.run_test(-);
return ;
}
// END CUT HERE