tc srm623 div2

tc srm623 div2"/>

tc srm623 div2

A.CatchTheBeatEasy

题意：已知某时刻会掉下来的东西，问能不能全部接住

思路：水模拟

Code：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define maxn 1010
struct node{int x,y;
}p[110];
bool cmp(node a,node b){return a.y<=b.y;
}
class CatchTheBeatEasy{
public:string ableToCatchAll(vector<int>x,vector<int>y){p[0].x=0;p[0].y=0;for(int i=0;i<x.size();i++) {p[i+1].x=x[i];p[i+1].y=y[i];}sort(p,p+1+x.size(),cmp);bool ok=true;for(int i=1;i<=x.size();i++){if(abs(p[i].x-p[i-1].x)>p[i].y-p[i-1].y)ok=false;}if(ok) return "Able to catch";else return "Not able to catch";};
};

题意：一只老鼠逃到一个圆盘上，已知猫和老鼠的速度，猫在T时刻进入圆盘，问能否追上

思路：老鼠初始的时候最多跑到PI*R的地方，然后时间很好想就是delta(s)/delta(v)

Code:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define pi acos(-1.0)
class CatAndRat{
public:double getTime(int R, int T, int Vrat, int Vcat){if(Vrat>=Vcat && R!=0) return -1.0;double tmp=T*Vrat;if(tmp>=pi*R) tmp=pi*R;return tmp/(Vcat-Vrat);}
};

题意：在一个row*col的果园里，找到一个面积最大的块，使得这个块里全是苹果或梨子或者空，可以移动苹果和梨子到空的地方

思路：先预处理出某一个子块中苹果梨子和空的个数，然后暴力子块的起点终点就行

Code：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define pi acos(-1.0)
#define maxn 60
int pear[maxn][maxn];
int apple[maxn][maxn];
int dot[maxn][maxn];
class ApplesAndPears{
public:int get_pear(int i,int j,int x,int y){if(i==0 && j==0) return pear[x][y];else if(i==0) return pear[x][y]-pear[x][j-1];else if(j==0) return pear[x][y]-pear[i-1][y];return pear[x][y]-pear[i-1][y]-pear[x][j-1]+pear[i-1][j-1];}int get_apple(int i,int j,int x,int y){if(i==0 && j==0) return apple[x][y];else if(i==0) return apple[x][y]-apple[x][j-1];else if(j==0) return apple[x][y]-apple[i-1][y];return apple[x][y]-apple[i-1][y]-apple[x][j-1]+apple[i-1][j-1];}int get_dot(int i,int j,int x,int y){if(i==0 && j==0) return dot[x][y];else if(i==0) return dot[x][y]-dot[x][j-1];else if(j==0) return dot[x][y]-dot[i-1][y];return dot[x][y]-dot[i-1][y]-dot[x][j-1]+dot[i-1][j-1];}int getArea(vector <string> board, int K){int row=board.size();if(row==0) return 0;int col=board[0].size();memset(pear,0,sizeof(pear));memset(apple,0,sizeof(apple));memset(dot,0,sizeof(dot));for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(board[i][j]=='P') pear[i][j]=1;else if(board[i][j]=='A') apple[i][j]=1;else dot[i][j]=1;}}for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(j==0) ;else{pear[i][j]+=pear[i][j-1];apple[i][j]+=apple[i][j-1];dot[i][j]+=dot[i][j-1];}}}for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(i==0) ;else{pear[i][j]+=pear[i-1][j];apple[i][j]+=apple[i-1][j];dot[i][j]+=dot[i-1][j];}}}int ans=1;for(int i=0;i<row;i++){for(int j=0;j<col;j++){for(int x=0;i+x<row;x++){for(int y=0;j+y<col;y++){int p=get_pear(i,j,i+x,j+y);int a=get_apple(i,j,i+x,j+y);int d=get_dot(i,j,i+x,j+y);int other_dot=get_dot(0,0,row-1,col-1)-d;int other_apple=get_apple(0,0,row-1,col-1)-a;int other_pear=get_pear(0,0,row-1,col-1)-p;if(other_dot){if(other_dot>=p+a && p+a<=K) ans=max(ans,(x+1)*(y+1));}if(other_dot||d){if((x+1)*(y+1)-a<=other_apple) {int t=(x+1)*(y+1)-a-p;t+=2*p;if(t<=K) ans=max(ans,(x+1)*(y+1));}if((x+1)*(y+1)-p<=other_pear) {int t=(x+1)*(y+1)-a-p;t+=2*a;if(t<=K) ans=max(ans,(x+1)*(y+1));}}int total=(x+1)*(y+1);if(d==0){if(p==total||a==total)ans=max(ans,total);}if(d==total)ans=max(ans,total);}}}}return ans;}
};