Codeforce Round #550 div3题解

今天药忘吃喽~ 2022-01-21 02:03 192阅读 0赞

# B.Parity Alternated Deletions #

## 1.题目 ##

[B][]

## 2.解答 ##

在n个数中是有偶数也有奇数的，在读取的时候我们要首先记录下偶数的个数n,奇数的个数m，如果|m-n|<=1，那么此时的数组剩下的元素为0.这一点不再说明，那么我们只需要考虑两者之差大于1的情况，这时剩下的数一定属于个数多的那一个数组。并且剩下的元素的个数为|m-n|-1，所以我们只需要将个数多的数组按照从小到大的顺序进行排序，即可.

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=2007;
    int num[maxn];
    int odd[maxn];
    int even[maxn];
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	int c_o=0;
    	int c_e=0;
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&num[i]);
    		if(num[i]%2==0)
    		{
    			odd[c_o]=num[i];
    			c_o++;
    		}
    		else
    		{
    			even[c_e]=num[i];
    			c_e++;
    		}
    	}
    	sort(odd,odd+c_o);
    	sort(even,even+c_e);
    	if(abs(c_o-c_e)==1||c_e-c_o==0)
    	{
    		printf("0\n");
    	}
    	else
    	{
    		int sum=0;
    		if(c_o==0)
    		{
    			for(int i=0;i<c_e-1;i++)
    			{
    				sum+=even[i];
    			}
    		}
    		else if(c_e==0)
    		{
    			for(int i=0;i<c_o-1;i++)
    			{
    				sum+=odd[i];
    			}
    		}
    		else
    		{
    			int s=c_e-c_o;
    			if(s>0)
    			{
    				for(int i=0;i<s-1;i++)
    				{
    					sum+=even[i];
    				}
    			}
    			else
    			{
    				s=-s;
    				for(int i=0;i<s-1;i++)
    				{
    					sum=sum+odd[i];
    				}
    			}
    		}
    		printf("%d\n",sum);
    	}
    	return 0;
    }

# c.Two Shuffled Sequences #

## 1.题目 ##

[C][]

## 2.解答 ##

当数组中某个元素出现三次及三次以上的时候，这个时候一定是No。如果某个元素出现了两次，我们可以将这个元素放置在单减数组中，只出现一次就将元素放在单加数组中。最后再把两个数组都进行排序即可

#include <bits/stdc++.h>
    using namespace std;
    int n;
    const int maxn=2*1e5+7;
    int num[maxn];
    int visit[maxn]={0};
    int de[maxn];
    int ri[maxn];
    bool cmp(int x,int y)
    {
    	return x>y;
    }
    int main()
    {
    	scanf("%d",&n);
    	bool flag=false;
    	int c_d=0;
    	int c_i=0;
    	for(int i=0;i<n;i++)
    	{
    		scanf("%d",&num[i]);
    		visit[num[i]]++;
    		if(visit[num[i]]>2)
    		{
    			flag=true;
    		}
    		else if(visit[num[i]]==2)
    		{
    			de[c_d]=num[i];
    			c_d++;
    		}
    		else
    		{
    			ri[c_i]=num[i];
    			c_i++;
    		}
    	}
    	if(flag)
    	{
    		printf("NO\n");
    	}
    	else
    	{
    		sort(ri,ri+c_i,cmp);
    		sort(de,de+c_d);
    		printf("Yes\n");
    		printf("%d\n",c_d);
    		for(int i=0;i<c_d-1;i++)
    		{
    			printf("%d ",de[i]);
    		}
    		if(c_d>=1)
    		printf("%d",de[c_d-1]);
    		puts("");
    		printf("%d\n",c_i);
    		for(int i=0;i<c_i-1;i++)
    		{
    			printf("%d ",ri[i]);
    		}
    		printf("%d",ri[c_i-1]);
    	}
    	return 0;
    }

# D.Equalize Them All #

## 1.题目 ##

[D][]

## 2.解答 ##

如果数组中各个元素都不相同，那么我们需要进行操作的次数为n-1次。假设我们所需要所有元素变成的数不在原先的数组中，那么对于任意一个数组我们都需要n次操作。所以我们可以得到所有元素变成的数一定在原先的数组之中。所以我们这时考虑将所有元素变成数组中的众数。（即出现次数最多的数）。这是我们可以保证操作次数最小。我们假设出现次数为m，那么此时所需要的操作次数为n-m

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=2*1e5+7;
    int num[maxn];
    int ti[maxn]={0};
    int d[maxn]={0};
    struct node
    {
    	int num;
    	int l;
    	int r;
    };
    node ans[maxn];
    int main()
    {
    	int n;
    	int maxs=-1;
    	int tar;
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&num[i]);
    		ti[num[i]]++;
    		if(ti[num[i]]>maxs)
    		{
    			maxs=ti[num[i]];
    			tar=i;//记录众数的位置
    		}
    	}
    	int c=0;
    	for(int i=tar+1;i<=n;i++)//从众数开始的位置向后进行操作
    	{
    		if(num[i]>num[i-1])
    		{
    			ans[c].num=2;
    			ans[c].l=i;
    			ans[c].r=i-1;
    			c++;
    		}
    		else if(num[i]<num[i-1])
    		{
    			ans[c].num=1;
    			ans[c].l=i;
    			ans[c].r=i-1;
    			c++;
    		}
    		num[i]=num[tar];
    	}
    	for(int i=tar-1;i>=1;i--)//向前进行操作
    	{
    		if(num[i]<num[i+1])
    		{
    			ans[c].num=1;
    			ans[c].r=i+1;
    			ans[c].l=i;
    			c++;
    		}
    		else if(num[i]>num[i+1])
    		{
    			ans[c].num=2;
    			ans[c].r=i+1;
    			ans[c].l=i;
    			c++;
    		}
    		num[i]=num[tar];
    	}
    	printf("%d\n",c);
    	for(int i=0;i<c;i++)
    	{
    		printf("%d %d %d\n",ans[i].num,ans[i].l,ans[i].r);
    	}
    	return 0;
    }

# E.Median String #

## 1.题目 ##

[E][]

## 2.解答 ##

我么可以将a和b都考虑成一个二十六进制的数，然后需要做的就只是二十六进制数的加法，以及相加之后结果除以2，再输出即可

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=2*1e5+7;
    char a[maxn];
    char b[maxn];
    int c[maxn]={0};
    int n;
    void add()
    {
    	for(int i=n;i>=0;i--)
    	{
    		c[i]+=a[i]-'a'+b[i]-'a';
    		if(i)
    		{
    			c[i-1]+=c[i]/26;
    			c[i]%=26;
    		}
    	}
    }
    
    void chu()
    {
    	for(int i=0;i<=n;i++)
    	{
    		if(c[i]%2)
    		{
    			c[i+1]+=26;
    		}
    		c[i]/=2;
    	}
    }
    
    int main()
    {
    	scanf("%d",&n);
    	getchar();
    	for(int i=1;i<=n;i++)
    	{
    		a[i]=getchar();
    	}	
    	getchar();
    	for(int i=1;i<=n;i++)
    	{
    		b[i]=getchar();
    	}
    	add();
    	chu();
    	for(int i=1;i<=n;i++)
    	{
    		printf("%c",c[i]+'a');
    	}
    	return 0;
    }

# G #

## 1.题目 ##

[F][]

## 2.解答 ##

完全不会，所以去看了官方解答的题解，题解的思路也是异常的奇怪，自己也去看了好久好久。。。。具体解答就写在代码中的注释里了

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=2*1e5+7;
    int inf=99999999;
    int a[maxn];
    int p[maxn][2];
    int dp[maxn][2];
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	for(int i=0;i<n;i++)
    	{
    		scanf("%d",&a[i]);
    	}
    	for(int i=1;i<n;i++)
    	{
    		dp[i][0]=-inf;
    		dp[i][1]=inf;
    		p[i][1]=-1;
    		p[i][0]=-1;
    	}
    	dp[0][0]=inf;
    	dp[0][1]=-inf;
    	//dp[i][1]递增序列的最大值 
    	//dp[i][0]递减序列的最小值 
    	//p存储的是上一个位置处于递增序列还是单减序列 
    	//如果是1存储于递增，0存储于递减
    	//p[i][0]以及p[i][1]储存的都是前一个的状态
    	//如果是0前一个就是递增
    	//如果是1前一个就是递减
    	//p[i][k]的k表示的当前元素的位置 
    	for(int i=1;i<n;i++)
    	{
    		{
    			if(a[i]>a[i-1]&&dp[i][0]<dp[i-1][0])
    			//a[i-1]递增我们想让a[i]也递增 
    			//后一个条件本身对判断不构成影响，是为了判断不符合条件的情况 
    			//更新维护递减序列的最小值 
    			{
    				dp[i][0]=dp[i-1][0];
    				p[i][0]=0;
    			}
    			if(dp[i-1][0]>a[i]&&dp[i][1]>a[i-1])
    			//a[i-1]递增我们想让a[i]递减
    			//显然我们需要满足a[i]的值要小于递减序列的最小值
    			//只有递减序列的最小值比a[i-1]还要大的时候，才去维护最小值 
    			{
    				dp[i][1]=a[i-1];
    				//那么此时显然递增序列的最大值会变成a[i-1] 
    				p[i][1]=0;
    				//更新递增序列的最大值 
    			}
    		}
    		{
    			if(a[i]<a[i-1]&&dp[i][1]>dp[i-1][1])
    			{
    				//a[i-1]为递减想把a[i]也变为递减 
    				dp[i][1]=dp[i-1][1];
    				p[i][1]=1;
    			}
    			if(dp[i-1][1]<a[i]&&dp[i][0]<a[i-1])
    			{ 
    				//a[i]的值要大于递增序列的最大值 
    				//a[i-1]为递减想把a[i]变成递增 
    				dp[i][0]=a[i-1];
    				//此时递减序列的最小值显然为a[i-1] 
    				p[i][0]=1;
    			}
    		}
    	}
    	int pos=-1;
    	int sta[maxn]={0};
    	//如果中间任意一个点没有加入单减序列也没有加入单增序列
    	//那么后面的所有dp都无法发生改变
    	if(dp[n-1][0]!=-inf)
    	//加入递增dp[k][1]会发生改变 
    	//加入递减dp[k][0]会发生改变 
    	{
    		pos=0;
    	}
    	if(dp[n-1][1]!=inf)
    	{
    		pos=1;
    	}
    	if(pos==-1)
    	{
    		printf("NO\n");
    	}
    	else
    	{
    		printf("YES\n");
    		for(int i=n-1;i>=0;i--)
    		{
    			if(pos==0)
    			{
    				sta[i]=1;			
    			}
    			pos=p[i][pos];
    		}
    		for(int i=0;i<n;i++)
    		{
    			printf("%d ",!sta[i]);
    		}
    	}  
    	return 0;
    }

因为自己理解的也是一知半解，所以思路方面可能不是很清晰，有疑问的小伙伴可以联系一下我，一起讨论下?

# G.Two Merged Sequences #

## 1.题目 ##

[G][F]

## 2.解答 ##

完全不会，所以去看了官方解答的题解，题解的思路也是异常的奇怪，自己也去看了好久好久。。。。具体解答就写在代码中的注释里了

因为自己理解的也是一知半解，所以思路方面可能不是很清晰，有疑问的小伙伴可以联系一下我，一起讨论下?

[B]: https://codeforces.com/contest/1144/problem/B
[C]: https://codeforces.com/contest/1144/problem/C
[D]: https://codeforces.com/contest/1144/problem/D
[E]: https://codeforces.com/contest/1144/problem/E
[F]: https://codeforces.com/contest/1144/problem/G