250pt
题意：
给定二维格点图和一个在格点图中的禁止点，每个格点包含0或1，求最多有多少个1被包含在一个不包含在禁止点的矩形里。
分析：
以禁止点所在行，列为边界，枚举，共4种情况。
View Code
#include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <stack> #include <fstream> #include <iomanip> #include <bitset> #include <list> using namespace std; #define REP(i,n) for(i=0;i<(n);++i) #define FOR(i,l,h) for(i=(l);i<=(h);++i) #define FORD(i,h,l) for(i=(h);i>=(l);--i) typedef vector<int> VI; typedef vector<double> VD; typedef long long LL; class FoxAndFlowerShopDivTwo { public: int theMaxFlowers(vector <string> f, int r, int c) { int i,j,n,m,k,ret; n=(int)f.size(); m=(int)f[0].size(); k=ret=0; for(i=0;i<r;i++) for(j=0;j<m;j++) if(f[i][j]=='F') k++; if(k>ret) ret=k; k=0; for(i=r+1;i<n;i++) for(j=0;j<m;j++) if(f[i][j]=='F') k++; if(k>ret) ret=k; k=0; for(i=0;i<n;i++) for(j=0;j<c;j++) if(f[i][j]=='F') k++; if(k>ret) ret=k; k=0; for(i=0;i<n;i++) for(j=c+1;j<m;j++) if(f[i][j]=='F') k++; if(k>ret) ret=k; return ret; } };
500pt
题意：
定义一种n行三角球堆，第n行有n个球紧密排列，n-1行有n-1球堆在第n行n个球的上方的缝隙，依此类推，所以总共有(n*(n+1))/2个球。现有三种颜色给球堆着色，相邻的小球颜色不能相同。给定三种颜色的数量，求能给多少个n行三角堆完全着色。
分析：
观察易得，
n%3=2或3时，红，绿，蓝所用颜色数相同，min(R,G,B)/(n*(n+1)/6);
n%3=1时，有一种颜色比其余两种颜色多一次，可用二分搜索解决。
View Code
#include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <stack> #include <fstream> #include <iomanip> #include <bitset> #include <list> using namespace std; #define REP(i,n) for(i=0;i<(n);++i) #define FOR(i,l,h) for(i=(l);i<=(h);++i) #define FORD(i,h,l) for(i=(h);i>=(l);--i) typedef vector<int> VI; typedef vector<double> VD; typedef long long LL; class FoxPaintingBalls { public: long long theMax(long long R, long long G, long long B, int N) { LL i,j,k,m,ret=0; LL s=(LL)N*(N+1)/6; if(N==1) return R+G+B ; k=min(R,min(G,B)); if(N%3==0||N%3==2) return k/s; for(i=1,j=k/s;i<=j;) { m=(i+j)>>1; if(k>=m*s&&R+G+B-m*s*3>=m) { ret=m; i=m+1; } else j=m-1; } return ret; } };
1000pt
题意：
给定一个数组F[],n和K，满足for all i, 0<=i<K，A[i]=F[i]，otherwise，A[i]=A[i-K]-A[i-K+1]+....+(-1)^(K-1)*A[i-1]。调整F[]的排列顺序可更改A[]的值。
求使A[n]最大的F[]排列
分析：
易得，一定存在一个C[]使得A[N]=C[0]*F[0]+C[1]*F[1]...+C[K-1]*F[K-1],所以只要求出C[]，或者求出C[]的相对大小关系就可以求出解。
1，K是奇数时:
A[i]=A[i-K]-A[i-k+1].....-A[i-1]
A[i-1]=A[i-K-1]-A[i-K]...-A[i-2]
两式相加，A[i]+A[i-1]=A[i-K-1]-A[i-1],
得A[i]=A[i-K-1]，即当K是奇数时,A[n]=A[n%(K+1)],其余排列字典序最小。
2，K是偶数时:
同理可推,A[i]=A[i-K-1]-2*A[i-1]，一下子看不出来，找规律。
|
i |
C[0] |
C[1] |
C[2] |
C[3] |
... |
C[K-1] |
|
K |
-1 |
1 |
-1 |
1 |
... |
1 |
|
K+1 |
-1 |
2 |
-2 |
2 |
2 |
|
|
K+2 |
-2 |
-3 |
4 |
-4 |
-4 |
|
|
K+3 |
-4 |
6 |
-7 |
8 |
8 |
观察可得，i是奇数，奇数项全为负，单调递减，偶数全为正，单调递增，i是偶数则相反。由此可确定C[]的相对大小关系。
View Code
#include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <stack> #include <fstream> #include <iomanip> #include <bitset> #include <list> using namespace std; #define REP(i,n) for(i=0;i<(n);++i) #define FOR(i,l,h) for(i=(l);i<=(h);++i) #define FORD(i,h,l) for(i=(h);i>=(l);--i) typedef vector<int> VI; typedef vector<double> VD; typedef long long LL; class FoxPlusMinus { public: vector <int> call(vector <int> C, vector <int> a) { VI ret; int i,j,k,n=a.size(); sort(a.begin(),a.end()); for(i=0;i<n;i++) { for(j=k=0;j<n;j++) if(i!=j) { if(C[j]<C[i]||(C[j]==C[i]&&j<i)) k++; } ret.push_back(a[k]); } return ret; } vector <int> maximize(vector <int> first, int N) { int i,j,K=first.size(); VI C; for(i=0;i<K;i++) C.push_back(0); if(K&1) { if(N%(K+1)==K) { for(i=0;i<K;i++) if(i&1) C[i]=-1; else C[i]=1; } else C[N%(K+1)]=1; //printf("K&1 "); return call(C,first); } if(N<K) { C[N]=1; //printf("N<K "); return call(C,first); } if(N&1) { for(i=0;i<K;i++) if(i&1) C[i]=i+1; else C[i]=-i-1; } else { for(i=0;i<K;i++) if(i&1) C[i]=-i-1; else C[i]=i+1; } if(N<2*K) { for(i=N-K+1;i<K;i++) C[i]=-C[i-1]; } return call(C,first); } };