比赛链接:https://codeforces.ml/contest/1691

夜深人静写博客~  

c题做不出来555~

A题:大意是给出一个n的数组,求删除一些数后,使得每两个数相加的和为偶数。求最少删除量。

剩下的数都需要是一致的奇偶性,所以删除奇数数量和偶数数量最小的那一个。

code:

#include<bits/stdc++.h>
using namespace std;
const int maxt = 1e5+10;
int a[maxt];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(a,0,sizeof a);
		int n,ji=0,ou=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]%2)
			{
				ji++;
			}else
				ou++;
		}
		printf("%d\n",ji>ou?ou:ji);
	}
}

 

B题:大意是给出n个学生的鞋子鞋码,以非递减次序排。他们需要洗鞋,洗的鞋需要是不是自己的且鞋码大于等于自己的。求一个满足的序列,没有则-1.

把每个段数都记录起来,如果存在某个鞋码只有一双鞋则不满足条件。然后再段内交题输出 n 1~ (n-1)

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int nn = 1e5+10;
int a[nn];
vector<int>ve;
void solve()
{
	ve.clear();
	memset(a,0,sizeof a);
	int n;
	cin>>n;
	bool flag = true;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]!=a[i-1])
		{
			ve.push_back(i);
			if(cnt==1) flag = false;
			else cnt = 1;
		}
		else cnt++;
	}// 1 1 2 2 2 3 3
	if(a[n]!=a[n-1]||n==1) flag = false;
	if(flag){
		ve.push_back(n+1);
		for(int i=0;i<ve.size()-1;i++)
		{
			cout<<ve[i+1]-1<<' ';
			for(int j=ve[i];j<ve[i+1]-1;j++)
				cout<<j<<' ';	
		}
		cout<<endl;
	}
	else cout<<"-1"<<endl;
}
int main()
{
//	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

 

C题:大意是给出一个长度为n的01序列,你可以拥有k次交换相邻两个元素的计划。f(x)定义为每相邻两个元素的十进制相加的sum,求最小数量的f(x)

要想使得最小值,那么我们需要尽可能的消除10或1,最靠左一定消1靠右消10。

我们可以很容易的计算出当前的sum,然后尽可能的先去消除10再去消除1

code:

#include<bits/stdc++.h>
using namespace std;

main(){
	int t;
	cin >> t;
	for(int _ = 0; _ < t; _++){
		int n, k; string s; 
		cin >> n >> k >> s;
		int l = -1, r = -1, ans = 0;
		for(int i = 0; i < n; i++){
			if(s[i] == '1'){
				r = i;
				ans += 11;
				if(l == -1)l = i;
			}
		}
		if(r != -1 && n-1-r <= k){
			k -= n-1-r;
			ans -= 10;
			if(l == r)l = k+1;
		}
		if(l != -1 && l <= k){
			k -= l;
			ans -= 1;
		}
		cout << ans << '\n';
	}
}