欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

【Atcoder】Atcoder Beginner Contest 143

程序员文章站 2022-07-08 10:12:41
VP,AC3题,T4没有使用long long所以wa了一个点。????比赛链接:https://atcoder.jp/contests/abc143。我的Chrome打开atcoder巨慢无比,换成Edge就好了。T1:A - Curtain题意:A是窗户宽,B是窗帘宽,假设长度足够情况下,求未被窗帘遮住的区域宽度。思路:求max (0,A−2∗B)(0,A - 2 * B)(0,A−2∗B)代码:#include using namespace std;...

总结:VP,AC3题,T4没有使用long long所以wa了一个点。:-(比赛链接:https://atcoder.jp/contests/abc143。我的Chrome打开atcoder巨慢无比,换成Edge就好了。偶也不知道为什么?

T1:A - Curtain

题意:A是窗户宽,B是窗帘宽,假设长度足够情况下,求未被窗帘遮住的区域宽度。

思路:求max (0A2B)(0,A - 2 * B)

代码:

#include <iostream>
using namespace std;
int a,b; 
int main(){
	cin>>a>>b;
	if(a-2*b<=0) cout<<0;
	else cout<<a-2*b;
	return 0;
}

T2:B - TAKOYAKI FESTIVAL 2019

题意:从N个物品中任意选2个,求出乘积和

思路:注意不要重选

时间复杂度:O(N2)O(N^2)

代码:

#include <iostream>
using namespace std;
const int N=60;

int n;
int a[N];
int sum;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	for(int i=1;i<=n-1;i++)
		for(int j=i+1;j<=n;j++){
			sum+=a[i]*a[j];	
		}
		
	cout<<sum;
	return 0;
}

T3:C - Slimes

题意:给一个长度为n的字符串s,求其中相邻不重复的字符串块的个数。

思路:遍历字符串,如果和前一个相同则忽略,否则个数+1

时间复杂度:O(n)O(n)

代码:

#include <iostream>
using namespace std;
int n;
string s;
int cnt=1;
int main(){
	cin>>n>>s;
	
	for(int i=1;i<n;i++)
	{
		if(s[i]==s[i-1])
			continue;
		cnt++;
	}
	
	cout<<cnt;
	return 0;
}

T4:D - Triangles

题意:n个数,求选出3个数可组一个三角形的方案个数。已知a、b、c构成三角形条件是a<b+c,b<a+c,c<a+b。

思路:n范围是2000,那么朴素地枚举三个数肯定是超时的。所以可以先排序,然后枚举a和b两个边,根据规则c的最小值是abs(a-b),最大值是a+b,用二分法求出在这个范围内的数的个数,排除掉不是a和b的方案,即可。如果没有这个范围的数则为0。最后累加ans(注意ans要开long long,我第一次没开就WA了一个点)以后像这种只WA一个点的就要考虑一下是不是精度不够了!

还有一点,会重复计算方案数,所以最后要除以3。

代码:

#include <iostream>
#include <algorithm>
typedef long long LL;
using namespace std;
const int N=2010;
int a[N];
int n;
LL ans;

int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	
	sort(a,a+n);
	
	for(int i=0;i<n-1;i++)
		for(int j=i+1;j<n;j++){
			int x=a[i];
			int y=a[j];
			
			int minv=abs(x-y), maxv=x+y;
			int min_idx, max_idx;

			int l=0,r=n-1;
			while(l<r){
				int mid=l+r>>1;
				if(a[mid]>minv) r=mid;
				else l=mid+1;
			}
			min_idx=l;
			
			l=0,r=n-1;
			while(l<r){
				int mid=l+r+1>>1;
				if(a[mid]<maxv) l=mid;
				else r=mid-1;
			}
			max_idx=l;
			
			int k;
			if(max_idx<=min_idx || a[max_idx]>=maxv || a[min_idx]<=minv) k=0;
			else{
				k=max_idx-min_idx+1;
				if(i>=min_idx && i<=max_idx) k--;
				if(j>=min_idx && j<=max_idx) k--;
			}
			
			ans+=(LL)k;
		}
		
	cout<<ans/3;
	return 0;
}

本文地址:https://blog.csdn.net/m0_49846828/article/details/107882451

相关标签: Atcoder