Codeforces Round #519 by Botan Investments（A，B，C）

A：水题。题目大意就是找到最小的k使得n*k-sum>sum

代码：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn=1e2+9;
int a[maxn];
int main(){
	int i,j,k,n;
	cin>>n;
	int mi=-1;
	int sum=0;
	for(i=0;i<n;i++){
		cin>>a[i];
		sum+=a[i];
		if(a[i]>mi)mi=a[i];
	}
	if(n*mi-sum>sum){
		cout<<mi<<endl;
		return 0;
	}
	while(n*mi-sum<=sum){
		mi++;
	}
	cout<<mi<<endl;
}

B题：暴力枚举。题目大意给你一串a序列，要求你找出不同长度的x序列

代码：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn=1e5+9;
int a[maxn],p[maxn];
int main(){
	int i,j,k,n;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>a[i];
	}
	a[0]=0;
	for(i=1;i<=n;i++){
		p[i]=a[i]-a[i-1];
	}
	int ans[maxn],num=0;
	for(i=1;i<=n;i++){
		int u=i,flag=0;;
		for(j=1;j<=n-u;j++){
			if(p[i+j]==p[j])continue;
			else flag=1;
		}
		if(flag==0){
			ans[num++]=u;
		}
	}
	cout<<num<<endl;
	for(i=0;i<num;i++){
		if(i!=num-1)
		cout<<ans[i]<<' ';
		else cout<<ans[i]<<endl;
	}
}

其实就是另开一个数组p来储存a[i]-a[i-1]的值，然后就是找了个序列合法的周期的个数。刚开始想的时候想复杂了，wa了一发，其实就是枚举周期长度，暴力查找看这个周期合不合法就行了。

C题：比赛中没做出来。。。。可恶啊，还是太菜了，后来仔细一想，其实这题有点类似与山脉吧，在山顶和山底选择翻转。

代码：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn=1e5+9;
int ans[maxn];
int main(){
	int i;
	string s;
	cin>>s;
	int len=s.size();
	int flag=0;
	for(i=1;i<len;i++){
		if(s[i]<s[i-1]){
			ans[i-1]=1;
			if(s[i+1]==s[i]){
				flag=1;
			}
			else if(s[i+1]!=s[i]){
				ans[i]=1;
			}
		}
		if((s[i+1]>s[i]&&flag)||(i==len-1&&flag)){
			ans[i]=1;
			flag=0;
		}	
	}
	for(i=0;i<len;i++){
		if(i!=len-1){
			cout<<ans[i]<<' ';
		}
		else cout<<ans[i]<<endl;
	}
}

D：待续