div1 250pt:
题意：用RGB三种颜色的球摆N层的三角形，要求相邻的不同色，给出RGB的数量，问最多能摆几个
解法：三种颜色的数量要么是全一样，要么是两个一样，另外一个比他们多一个，于是可以分类讨论：对于数量全一样的，直接算;对于另外的，我们可以先不考虑多出来的那一个，也是正常放，然后看最后剩下的位置能不能放完所有多出来的那一个，这个可以二分。
// BEGIN CUT HERE // END CUT HERE
#line 5 "FoxPaintingBalls.cpp"
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cassert>
#include<iostream>
#include<string>
#include<sstream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
class FoxPaintingBalls
{
public:
long long theMax(long long R, long long G, long long B, int N){
//$CARETPOSITION$
if(N == )return R+G+B;
ll total = 1LL*N*(N + ) / ;
ll least = total / ;
ll maxn = min(min(R,G),B) / least;
if(total % == )return maxn;
ll answer = ,left = ,right = maxn;
while(left <= right){
// cout << "L: "<<l<<" R: "<<r<<endl;
ll mid = (left + right) >> ;
ll r = R - mid * least,g = G - mid * least,b = B - mid * least;
if((r + g + b) >= mid){
answer = mid;
left = mid + ;
}else{
right = mid - ;
}
}
return answer; } // 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(); if ((Case == -) || (Case == )) test_case_6(); }
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() { long long Arg0 = 2LL; long long Arg1 = 2LL; long long Arg2 = 2LL; int Arg3 = ; long long Arg4 = 1LL; verify_case(, Arg4, theMax(Arg0, Arg1, Arg2, Arg3)); }
void test_case_1() { long long Arg0 = 1LL; long long Arg1 = 2LL; long long Arg2 = 3LL; int Arg3 = ; long long Arg4 = 0LL; verify_case(, Arg4, theMax(Arg0, Arg1, Arg2, Arg3)); }
void test_case_2() { long long Arg0 = 8LL; long long Arg1 = 6LL; long long Arg2 = 6LL; int Arg3 = ; long long Arg4 = 2LL; verify_case(, Arg4, theMax(Arg0, Arg1, Arg2, Arg3)); }
void test_case_3() { long long Arg0 = 7LL; long long Arg1 = 6LL; long long Arg2 = 7LL; int Arg3 = ; long long Arg4 = 2LL; verify_case(, Arg4, theMax(Arg0, Arg1, Arg2, Arg3)); }
void test_case_4() { long long Arg0 = 100LL; long long Arg1 = 100LL; long long Arg2 = 100LL; int Arg3 = ; long long Arg4 = 30LL; verify_case(, Arg4, theMax(Arg0, Arg1, Arg2, Arg3)); }
void test_case_5() { long long Arg0 = 19330428391852493LL; long long Arg1 = 48815737582834113LL; long long Arg2 = 11451481019198930LL; int Arg3 = ; long long Arg4 = 5750952686LL; verify_case(, Arg4, theMax(Arg0, Arg1, Arg2, Arg3)); }
void test_case_6() { long long Arg0 = 1LL; long long Arg1 = 1LL; long long Arg2 = 1LL; int Arg3 = ; long long Arg4 = 3LL; verify_case(, Arg4, theMax(Arg0, Arg1, Arg2, Arg3)); } // END CUT HERE };
// BEGIN CUT HERE
int main(){
FoxPaintingBalls ___test;
___test.run_test(-);
return ;
}
// END CUT HERE
250pt
div 500pt:
题意：N*N的格子里有两种颜色的花，L,P给出一个maxDiff，要求找出来两个不相交的矩形，使得他们两个中L,P的数量之差<=maxDiff，并且数量最多
解法：枚举分割线，然后预处理，L[i][j]表示i条线左侧差为j的最大数量，其余同理，最后枚举算一下。
// BEGIN CUT HERE // END CUT HERE
#line 5 "FoxAndFlowerShopDivOne.cpp"
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cassert>
#include<iostream>
#include<string>
#include<sstream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = ;
inline void checkmax(int &a,int b){
if(a == - || a < b)a = b;
}
int L[N][N*N*],R[N][N*N*],U[N][N*N*],D[N][N*N*];
class FoxAndFlowerShopDivOne
{
public:
int theMaxFlowers(vector <string> flowers, int maxDiff){
//$CARETPOSITION$
memset(L,-,sizeof(L));
memset(R,-,sizeof(R));
memset(U,-,sizeof(U));
memset(D,-,sizeof(D));
int n=flowers.size(),m=flowers[].size();
for(int top=;top<n;top++){
for(int bottom=top;bottom<n;bottom++){
for(int left=;left<m;left++){
for(int right=left;right<m;right++){
int total = ,d = ;
for(int i=top;i<=bottom;i++){
for(int j=left;j<=right;j++){
total += flowers[i][j]!='.';
d += flowers[i][j]=='L';
d -= flowers[i][j]=='P';
}
}
for(int i=right+;i<m;i++)
checkmax(L[i][d+n*m],total);
for(int i=left;i>=;i--)
checkmax(R[i][d+n*m],total);
for(int i=bottom+;i<n;i++)
checkmax(U[i][d+n*m],total);
for(int i=top;i>=;i--)
checkmax(D[i][d+n*m],total);
}
}
}
}
int answer = -;
for(int i=;i<n;i++){
for(int j=;j<=n*m*;j++){
for(int k=;k<=n*m*;k++){
if(abs(j+k-n*m*)<=maxDiff && U[i][j]!=- && D[i][k] !=-)
checkmax(answer,U[i][j]+D[i][k]);
}
}
}
for(int i=;i<m;i++){
for(int j=;j<=n*m*;j++){
for(int k=;k<n*m*;k++){
if(abs(j+k-n*m*)<=maxDiff && L[i][j] != - && R[i][k] != -)
checkmax(answer,L[i][j]+R[i][k]);
}
}
}
return answer;
} // 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(); }
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[] = {"LLL",
"PPP",
"LLL"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, theMaxFlowers(Arg0, Arg1)); }
void test_case_1() { string Arr0[] = {"LLL",
"PPP",
"LLL"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, theMaxFlowers(Arg0, Arg1)); }
void test_case_2() { string Arr0[] = {"...",
"...",
"..."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, theMaxFlowers(Arg0, Arg1)); }
void test_case_3() { string Arr0[] = {"LLPL.LPP",
"PLPPPPLL",
"L.P.PLLL",
"LPL.PP.L",
".LLL.P.L",
"PPLP..PL"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, theMaxFlowers(Arg0, Arg1)); }
void test_case_4() { string Arr0[] = {"LLLLLLLLLL",
"LLLLLLLLLL",
"LLLLLLLLLL",
"LLLLLLLLLL",
"LLLLLLLLLL"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = -; verify_case(, Arg2, theMaxFlowers(Arg0, Arg1)); }
void test_case_5() { string Arr0[] = {"LLLP..LLP.PLL.LL..LP",
"L.PL.L.LLLL.LPLLPLP.",
"PLL.LL.LLL..PL...L..",
".LPPP.PPPLLLLPLP..PP",
"LP.P.PPL.L...P.L.LLL",
"L..LPLPP.PP...PPPL..",
"PP.PLLL.LL...LP..LP.",
"PL...P.PPPL..PLP.L..",
"P.PPPLPLP.LL.L.LLLPL",
"PLLPLLP.LLL.P..P.LPL",
"..LLLPLPPPLP.P.LP.LL",
"..LP..L..LLPPP.LL.LP",
"LPLL.PLLPPLP...LL..P",
"LL.....PLL.PLL.P....",
"LLL...LPPPPL.PL...PP",
".PLPLLLLP.LPP...L...",
"LL...L.LL.LLLPLPPPP.",
"PLPLLLL..LP.LLPLLLL.",
"PP.PLL..L..LLLPPL..P",
".LLPL.P.PP.P.L.PLPLL"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; int Arg2 = ; verify_case(, Arg2, theMaxFlowers(Arg0, Arg1)); } // END CUT HERE };
// BEGIN CUT HERE
int main(){
FoxAndFlowerShopDivOne ___test;
___test.run_test(-);
return ;
}
// END CUT HERE
500pt