Codeforces Global Round 9（A~D题解）

暑假要好好训练了
昨日补题（虽然好像只补了简单题，但是思维真的生涩 啊）
题目链接：Global Round 9

A. Sign Flipping

思路：可以理解为翻牌子一样，有正反两种情况，不用考虑初始状态，直接暴力将牌子安排成正反交错即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 110;
int a[maxn],b[maxn],d[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	int n,t,m;
	cin >> t;
	while(t--)
    {
        cin >> n;
        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
            if(i % 2 == 0 && a[i] < 0) a[i] = -a[i];
            else if(i % 2 !=0 && a[i] > 0) a[i] = -a[i];
        }
        for(int i =0 ; i < n; i++) cout << a[i] << " " ;
        cout << endl;
    }
}

B. Neighbor Grid

思路：除了边角超过3/4，其他都可以成立。直接按填满的情况模拟即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 310;
int a[maxn][maxn],d[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	int n,t,m,tol,f = 1;
	cin >> t;
	while(t--)
    {
    	f = 1;
        cin >> n >> m;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
        	{
        		cin >> a[i][j];
        		if(i == 0 && (j == 0 || j == m-1))
                {
                    if(a[i][j] > 2)f = 0;
                    else a[i][j] = 2;
                }
                else if(i == n - 1 && (j == 0 || j == m - 1))
                {
                    if(a[i][j] > 2) f = 0;
                    else a[i][j] = 2;
                }
                else if(i == 0 || i == n - 1 || j == 0 || j == m - 1)
                {
                    if(a[i][j] > 3) f = 0;
                    else a[i][j] = 3;
                }
                else
                {
                    if(a[i][j] > 4) f = 0;
                    else a[i][j] = 4;
				}
			}
		}
        if(f == 0) cout << "NO\n";
        else
        {
            cout << "YES\n";
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < m; j++)
                {
                    cout << a[i][j] << " ";
                }
                cout << endl;
            }
        }     
    }
}

C. Element Extermination

思路：想了很久最后发现是签到题。题目规则是可以在数组中选取相邻的，即ai与ai+1，如果ai<ai+1，则可以消去二者中较小的。
如果a1比an大，那么无论怎样消到最后无法通过消去最右边的数字，所以其成立条件必然有a1<an。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 310;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	int t,a,b,c,n;
	cin >> t;
	while(t--)
    {
        cin >> n;
        for(int i = 0; i < n; i++)
		{
			cin >> a;
			if(i == 0) b = a;	
			if(i == n - 1) c = a;
		} 
        if(b < c) cout << "YES\n";
        else cout << "NO\n";
    }
}

D. Replace by MEX

思路：形成从0~n-1的数组。
分为两种情况探讨，一种数组元素在0~n-1中缺失；另一种是没有缺失元素但是顺序不对。
如果是第一种，那就把缺失的第x个元素替换掉a[x]上的数字；
如果是第二种，那就让n替换掉最小的不在自己位置上的元素。
mex函数用判断最小的缺失元素，check函数用来确认是否满足题目要求以及返回最小的不在其位置上的元素。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1010;
const int N = 1e6 +10;
int a[maxn],b[maxn],n,c[N];

int mex()
{
	memset(b,0,sizeof(b));
	for(int i = 0; i < n; i++)
	{
		b[a[i]]++;
	}
	for(int i = 0; i <= n; i++)
	{
		if(b[i] == 0) return i;
	}
}

int check()
{
	for(int i = 0; i < n; i++)
	{
		if(a[i] != i) return i;
	}
	return -1;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	int t,m;
	cin >> t;
	while(t--)
    {
    	int f = 0, mi = 2000;
    	memset(c,0,sizeof(c));
    	int tol = 0;
        cin >> n;
        for(int i = 0; i < n; i++)
		{
			cin >> a[i];
			if(mi > a[i])
			{
				mi = a[i];
				f = i;
			}
		} 
		while(1)
		{
			m = mex();
			if(check() == -1) break;
			if(m == n) 
			{
				f = check();
				a[f] = n;
				c[tol] = f;
				tol++; 
				continue;
			}
			if(a[m] != m)
			{
				a[m] = m;
				c[tol] = m;
				tol++; 
			}
		}
        cout << tol << endl;
		for(int i = 0; i < tol; i++) cout << c[i] + 1 <<" ";
		cout << endl;
    }
}

本文地址：https://blog.csdn.net/LucyHolmes/article/details/107172170