【Atcoder】Atcoder Beginner Contest 143_IOS

【Atcoder】Atcoder Beginner Contest 143

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

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

思路：求max $(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(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)$

代码：

#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