CF-646 Div2

Odd Selection 模拟

题意

给你一串数字，问你能不能挑x个数字，使和为奇数。

思路

• 不能的情况有：
• 这串数字里面奇数数量为0
• 所有数字都要选->所有奇数都要选，而且有偶数个奇数
• 所有都是奇数->所有奇数都要选，而且有偶数个奇数 //易忘

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN];
int main(){
	int T,n,x;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&x);
		int tot = 0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			if(a[i]&1)	tot++;
		}
		if(!(tot&1)&&n==x) printf("No\n");
		else if(!tot) printf("No\n");
		else if(tot==n&&!(x&1)) printf("No\n");
		else printf("Yes\n");
	}
	return 0;
}

Odd Selection 暴力 前缀和

题意

给你一个只有0和1的字符串，问你怎么样才能让字符串不含有字串‘010‘和‘101‘

思路

• 也就是变为‘111000‘, ‘000111‘, ‘00000‘, ‘11111‘这几种情况，全为一种数字，或者数字都在一边
• 全0，全1
• 可以用前缀和记录 前面有多少个1, a[i]=a[i-1]+1，或者a[i]=a[i-1]
• 然后计算以i为分界：即i前面全是1后面全是0，或者i前面全是0后面全是1的情况

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
char s[MAXN];
int a[MAXN]; 
int len;
int main()
{
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%s",&s);
		len = strlen(s);
		int ans=len;
		int totx=0,toty=0;
		memset(a,0,sizeof(0));
		for(int i=0;i<len;i++){
			if(s[i]==‘1‘){
				a[i+1] = a[i]+1;
				totx++;
			}
			else{
				toty++;
				a[i+1]=a[i]; 
			} 
		}
		ans = min(totx,toty);
		for(int i=1;i<=len;i++){
			ans = min(ans,i-a[i]+totx-a[i]); //111000
			ans = min(ans,a[i]+(toty-(i-a[i])));//000111
		}
		printf("%d\n",ans);
	}
	return 0;
}

CF-646 Div2

原文：https://www.cnblogs.com/xuwanwei/p/13036431.html