比赛链接:https://codeforc.es/contest/1712

这次比赛做了ABC,A题有些失误,大概十二分钟才AC,中途WA了一次。

B题做的很快6分钟一次过

C题WA了三次,改完一个bug后,手贱多加了一条语句,导致后面WA了两次。

A题:大意是给出一个长度为N的数组,给出数字k。求前k项的和最小。每次可以交换任意 i j 元素。元素互不相同为1-n的排列

很简单,排一下序,然后查看原序列和 排序后的序列,前k项有多少元素不存在。

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
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;
}
bool sign[110];
void solve()
{
	memset(sign,false,sizeof sign);
	int n,k,x;
	cin>>n>>k;
	vector<int> a;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		a.push_back(x);
	}
	vector<int> b = a;
	sort(b.begin(),b.end());
	for(int i=0;i<k;i++)
	{
		sign[a[i]] = true;
	}
	int sum = 0;
	for(int i=0;i<k;i++)
	{
		if(sign[b[i]]==false) sum++;
	}
	cout<<sum<<endl;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}


 

B题:大意是给出一个n,构造一个序列 for 1-n,使得LCM(i,a[i])最小公倍数的和最大。

很简单的构造题,对于偶数,互换相邻两个数,对于奇数,除了1之外其他互换。

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
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;
}
void solve()
{
	int n;
	cin>>n;
	if(n%2==0)
	{
		int kt = 1;
		for(int i=1;i<=n;i++)
		{
			cout<<i+kt<<' ';
			kt*=-1;
		}
		cout<<endl;
	}else{
		cout<<1<<' ';
		int kt = 1;
		for(int i=2;i<=n;i++)
		{
			cout<<i+kt<<' ';
			kt*=-1;
		}
		cout<<endl;
	}
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}


 

C题:给出一个序列,通过操作使得这个序列为非递减序列。
可以的操作:对于一个数x,使得所有等于x的a[i] i for 1-n  变为 0 。

方法:模拟一遍,每次遇到不符合的数对,更新其之前的所有数使其为0,作为标记更新后序。直到当前标记之前的全部为标记过的。寻找标记从后往前。

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
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;
bool sign[nn];
vector<int>ve;
set<int> se;
void solve()
{
	ve.clear(); se.clear();
	memset(sign,false,sizeof sign);
	int n,x;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		ve.push_back(x);
	}
	int cur = -1;
	while(1)
	{
		for(int i=ve.size()-1;i>=1;i--)
		{
			if(ve[i]<ve[i-1]||sign[ve[i-1]]==true) 
			{
				cur = i-1;
			//	sign[ve[i-1]] = true; 
				break;
			}
		}
		bool flag = true;
		for(int i=0;i<=cur;i++)
		{
			if(sign[ve[i]]==false)
				flag = false;
			sign[ve[i]] = true;
		}
		if(flag) break;
	}
	if(sign[ve[n-1]]==true) cur = n-1;
	for(int i=0;i<=cur;i++)
		se.insert(ve[i]);
	cout<<se.size()<<endl;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}