Codeforces Round#493 (Div. 2)

比赛传送门

​

A. Balloons

暴搜即可

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=15;
int sum,n,a[maxn],ans[maxn],suc;
void dfs(int stp,int s){
	if (suc) return;
	if (stp>n){
		if (s!=0&&sum-s!=0&&s!=sum-s){
			suc=1;
			printf("%d\n",ans[0]);
			for (int i=1;i<=ans[0];i++) printf("%d ",ans[i]);
		}
		return;
	}
	dfs(stp+1,s);
	ans[++ans[0]]=stp;
	dfs(stp+1,s+a[stp]);
	ans[0]--;
}
int main(){
	scanf("%d",&n); if (n==1) return puts("-1"),0;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];
	dfs(1,0);
	if (!suc) puts("-1");
	return 0;
}

B. Cutting

记录奇数和偶数出现的次数，显然只有相等时才可以切割

然后贪心取代价小的切割即可

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=105,maxv=105;
int n,N,V,a[maxn],w[maxn],f[maxn];
inline int Abs(int x) {return x>0?x:-x;}
int main(){
	scanf("%d%d",&n,&V);
	int s=0;
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if (i!=1&&s==0) w[++N]=Abs(a[i]-a[i-1]);
		if (a[i]&1) s++;else s--;
	}
	sort(w+1,w+1+N);
	int ans=0;
	for (int i=1;i<=N;i++)
	 if (w[i]<=V) V-=w[i],ans++;
	printf("%d",ans);
	return 0;
}

C. Convert to Ones

设连续0的段数为\(cnt\)，则用\(cnt-1\)次操作就可以把所有0放到一起

答案为\(\max \{ cnt\cdot y,(cnt-1)x+y \}\)

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

char s[300005];
int main(){
	int n,x,y;ll cnt=0;
	scanf("%d%d%d%s",&n,&x,&y,s+1);
	s[0]='1';
	for (int i=1;i<=n;i++) cnt+=(s[i-1]=='1'&&s[i]=='0');
	if (cnt==0) return puts("0"),0;
	printf("%lld",min(cnt*y,(cnt-1)*x+y));
	return 0;
}

D. Roman Digits

看这里

E. Sky Full of Stars

看这里