Codeforces Round #809 (Div. 2)

2022/7/22 23:30:36

编程Tag： div int include sT AI cin Codeforces 809

本文主要是介绍Codeforces Round #809 (Div. 2)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Problem - A - Codeforces

给了t个询问，n个数Ai，又给了一个数为m,原来字符串为一连串的B,有两个操作第一个操作使第Ai个变为A,第二个操作使（M+1-Ai)变为A,使其字典序最小，肯定是比一下看那个在前面，记录一下即可。

1
4 5
1 1 3 1

注意的使我们要判断一下是否有重复操作进行了操作1以后，再次遇到这个数时进行操作二，先进行2时再进行1。

查看代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char a[60];
bool st[60];
int b[60];
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n,m;
        cin >> n>>m;
        for(int i=1;i<=m;i++) 
        {
        	a[i]='B';
        	st[i]=false;
		}
        for(int i=1;i<=n;i++) 
        {
        	cin >> b[i];
		}
        for (int i = 1; i <= n; i ++ )
        {
            if(b[i]<=m+1-b[i]&&!st[b[i]]) 
            {
                a[b[i]]='A';
                st[b[i]]=true;
            }
            else if(b[i]>m+1-b[i]&&!st[m+1-b[i]])
            {
                 a[m+1-b[i]]='A';
                 st[m+1-b[i]]=true;
            }else if(st[b[i]])
            {
                a[m+1-b[i]]='A';
            }else if(st[m+1-b[i]])
            {
                a[b[i]]='A';
            }
        }
        for (int i = 1; i<=m; i++ )
        cout << a[i];
        cout << endl;
    }
    return 0;
}

Problem - B - Codeforces

这题真的是道好题，给了n个数Ai，每个数代表了一个颜色，当前Ai只能放在前一个的左右两边或者上边，判断一下每种颜色能达到的最大高度。首先是数据转图形。

7
1 2 3 1 2 3 1
    
input:
3 2 2 0 0 0 0

可以发现只要中间差两个数就可以形成高塔，很好wa了。再讨论离得更远些。

相离偶数个就可以，但是我们碰到了极端情况也就是最优解的选取，怎样判断最优解，这里给一个小证明即从头开始取即是最优解。

6
4 2 2 2 4 4

查看代码：

#include<iostream>
using namespace std;
const int N=1e5+10;
struct
{
	int x;
	int y;
}e[N];
bool st[N];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			int z;
			cin>>z;
			if(!st[z])
			{
				e[z].x=i;
				e[z].y++;
				st[z]=1;
			}else if((i+1-e[z].x)%2==0)
			{
				e[z].x=i;
				e[z].y++; 
			}
		}
		for(int i=1;i<=n;i++)
		cout<<e[i].y<<' ';
		cout<<endl;
		for(int i=1;i<=n;i++)
		{
			 st[i]=0; 
			 e[i].y=0;
		}
	}
	return 0;
 }

Problem - C - Codeforces

给了n个数Ai，代表每个位置柱子的初始高度，可以进行操作使柱子的高度加一使其cool(Ai-1<Ai&&Ai+1<Ai)既是山峰，求每个样例最多山峰的最小操作数。

3
2 1 2
6
3 1 4 5 5 2
8
4 2 1 3 5 3 6 1

首先我们应该判断每个样例有几个山峰

这篇关于Codeforces Round #809 (Div. 2)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Codeforces Round #809 (Div. 2)

Problem - C - Codeforces

相关编程文章