牛客月赛57

Fly

A.最大面积

思路：
取宽的最小值*长的最小值即可。

代码:

#include 
using namespace std;
typedef long long ll;
int a,b,c,d;

int main(){
	scanf("%d%d%d%d",&a,&b,&c,&d);
	ll ans=1ll*min(a,c)*min(b,d);
	printf("%lld\n",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

B.种树

题意：
一横排方块，每次选择一个有树的块开始走，只能选择一个方向并且沿着此方向走下去，问种满树至少需要多少天。

思路：
（1）当每个块都有树时，0天。
（2）当边界有树时，只需要从这个地方出发走完即可，只需1天。
（3）边界都没有树，那就是2天。

代码：

#include 
using namespace std;
int main(){
	int n;
	string s;
	cin>>n;
	cin>>s;
	if(s.find('0')==string::npos) printf("0");
	else if(s[0]=='1'||s[n-1]=='1') printf("1");
	else printf("2");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

C.奇怪的电梯

题意：
给出出发的楼层a和要到达的楼层b，进入电梯后相邻k层的楼层都是不能按的，问最后a能否到达b。

思路：
首先ab一定可以到达。
其次，当n<=k时，只有ab可以到达。
当n>k时，此时1一定能到达n，因此可以将1和n作为中转楼层。
那么a必须满足abs(a-1)>k或者abs(a-n)>k，
b必须满足abs(b-1)>k或者abs(b-n)>k。

代码：

#include 
using namespace std;
typedef long long ll;
ll n,k,a,b;
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%lld%lld%lld%lld",&n,&k,&a,&b);
		if(a==b){
			puts("YES");
		} 
	    else if(n<=k) puts("NO");
	    else if((((abs(a-1))>k)||((abs(a-n))>k))&&((abs(b-1))>k||(abs(b-n)>k))){
	    	puts("YES");
		}
		else puts("NO");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

D.最大gcd

题意：
给出一个数字序列a，求出这个序列中出现过的最大的gcd。

思路：
最容易想到的就是从小到大枚举因子，如果这个因子出现了>=2次，就更新ans。
初始先设置ans=1,因为1肯定是一个gcd。
再记录下每个数字a[i]出现的次数，
再在1~N范围内从小到大枚举因子i，并且枚举从i ~ N的i的倍数，累计出现的次数，
如果出现了>=2次，ans=max(ans,i);

代码：

#include 
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int n,a[N],num[N];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),num[a[i]]++;
	int ans=1;
	for(int i=1;i<N;i++){//从小到大枚举因数 
		int sum=0;//累计此因子出现的次数 
		for(int j=i;j<N;j+=i){//从>=i并且后面为i的倍数中找 
			sum+=num[j];
		}
		//如果此因子出现了>=2次，ans=max(ans,i) 
		if(sum>=2) ans=max(ans,i);
	}
	printf("%d\n",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21