第一题:
题意:给一个包含‘F’和'.'的矩阵,'F'代表花,'.'代表空地,给你一个r,c,表示第r行第c列的那个点不可选,问题包含最多'F'的矩阵中有多少'F'。
题解:枚举以r,c划分的九个子矩阵,求最大和即可。
代码:
#include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; class FoxAndFlowerShopDivTwo { public: int theMaxFlowers(vector <string> flowers, int r, int c) { int a[8]; memset(a,0,sizeof(a)); int y=flowers[0].size(),summ=0; for(int i=0;i<flowers.size();++i) for(int j=0;j<y;++j) if(flowers[i][j]=='F') { if(i<r&&j<c) a[0]++; else if(i<r&&j==c) a[1]++; else if(i<r&&j>c) a[2]++; else if(i==r&&j<c) a[3]++; else if(i==r&&j>c) a[4]++; else if(i>r&&j<c) a[5]++; else if(i>r&&j==c) a[6]++; else if(i>r&&j>c) a[7]++; } summ=max(summ,a[0]+a[1]+a[2]); summ=max(summ,a[2]+a[4]+a[7]); summ=max(summ,a[0]+a[3]+a[5]); summ=max(summ,a[5]+a[6]+a[7]); return summ; } };
第二题:
题意:一个由球堆叠成的正三角(边长为n),现在要用3种颜色(红,蓝,绿)的球组成这的三角形(边长为n),其中要求相邻的两个球不能是同一种颜色,而且每种颜色的球有数量上限,问最多可以组成多少个这样的正三角。
题解:可以发现n%3==1的时候组成一个符合要求的三角形要求三种颜色的球的数量分别为(n+1)*n/6,(n+1)*n/6,(n+1)*n/6+1,n%3!=1的时候组成一个符合要求的三角形要求三种颜色的球的数量都为(n+1)*n/6。按情况分别处理即可。
代码:
#include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; class FoxPaintingBalls { public: long long theMax(long long R, long long G, long long B, int N) { long long summ=((N+1)*N)/2; long long cnt=summ/3; if(R+G+B<summ) return 0; if(N==1) return R+G+B; if(R==0||B==0||G==0) return 0; if(N%3!=1) return min(R/cnt,min(G/cnt,B/cnt)); long long a[3]; a[0]=R;a[1]=B;a[2]=G; long long countx=(a[0]/(cnt*3+1)); a[0]-=(countx*(cnt*3+1)); a[1]-=(countx*(cnt*3+1)); a[2]-=(countx*(cnt*3+1)); countx*=3; sort(a,a+3); long long count=min(a[0]/cnt,a[2]/(cnt+1)); a[0]-=(count*cnt); a[1]-=(count*cnt); a[2]-=(count*(cnt+1)); sort(a,a+3); return countx+count+min(a[0]/cnt,a[2]/(cnt+1)); } };
第三题: