Codeforces Global Round 9 A ~ D 题解

A - Sign Flipping

题面

题意简述：

给定长为 \(n\)（\(n\) 是奇数）的整数数组 \(a\)，你可以进行任意次操作，每次选择一个 \(a_i\) 并将它变成 \(-a_i\)。你需要让最终的数组满足以下条件：

• 至少有 \(\frac{n-1}{2}\) 个相邻数的差值 \(\le 0\)。
• 至少有 \(\frac{n-1}{2}\) 个相邻数的差值 \(\ge 0\)。

输出任意一个满足条件的最终数组。如果有多个解，输出任意一个，可以证明，解总是存在的。

多组测试数据。

\(\texttt{Data Range:} 1\le t\le 500, 3\le n\le 99, -10^9\le a_i\le 10^9\)。

简单构造。

一正一负即可。

const int N = 103;

int n, a[N];

int main()
{
    int T = gi();
    while (T--)
    {
    	n = gi();
    	for (int i = 1; i <= n; i+=1) a[i] = gi();
    	for (int i = 1; i <= n; i+=1)
    	{
    		if (i & 1) printf("%d ", -abs(a[i]));
    		else cout << abs(a[i]) << ' ';
    	}
    	puts("");
    }
    return 0;
}

B - Neighbor Grid

题面

题意简述：

给你一个 \(n\) 行 \(m\) 列的矩阵，要求你让这个矩阵是“完美”的。

“完美”的定义如下：

若当前的格子里是一个正整数 \(k\)，那么与这个网格相邻（有公共边）的 \(k\) 个格子也必须有一个正整数。

若当前的格子里是 0 ，那么不受上述的限制。

你可以对任意的一个格子加上 1 ，次数不受限制。

如果可以做到“完美”，请输出 YES 之后，将修改过的矩阵输出。

否则只输出一行 NO 。

多组测试数据。

\(\texttt{Data Range:}1\le t\le 5000, 2\le n,m\le 300,n\times m\le 10^5,0\le a_{i,j}\le 10^9\)。

简单构造。

每个角上的数为 \(2\)，每个边上的数为 \(3\)，中间的数为 \(4\)，无解判断一下即可。

const int N = 303;

int n, a[N][N];

int main()
{
    int T = gi();
    while (T--)
    {
    	n = gi(), m = gi();
    	for (int i = 1; i <= n; i+=1)
    		for (int j = 1; j <= m; j+=1)
    			a[i][j] = gi();
    	bool ok = true;
    	if (a[1][m] > 2 || a[n][1] > 2 || a[n][m] > 2 || a[1][1] > 2)
    	{
    		puts("NO");
    		continue;
    	}
    	for (int i = 2; i < m; i+=1)
    	{
    		if (a[1][i] > 3 || a[n][i] > 3) ok = false;
    	}
    	for (int i = 2; i < n; i+=1)
    		if (a[i][1] > 3 || a[i][m] > 3) ok = false;
    	for (int i = 2; i < n; i+=1)
    		for (int j = 2; j < m; j+=1)
    			if (a[i][j] > 4) ok = false;
    	if (!ok) puts("NO");
    	else 
    	{
    		puts("YES");
    		a[1][m] = a[n][1] = a[n][m] = a[1][1] = 2;
    		for (int i = 2; i < m; i+=1)
    			a[1][i] = 3, a[n][i] = 3;
			for (int i = 2; i < n; i+=1)
				a[i][1] = 3, a[i][m] = 3;
			for (int i = 2; i < n; i+=1)
				for (int j = 2; j < m; j+=1)
					a[i][j] = 4;
			for (int i = 1; i <= n; i+=1)
			{
				for (int j = 1; j <= m; j+=1)
					cout << a[i][j] << ' ';
				puts("");
			}
    	}
    }
    return 0;
}

C - Element Extermination

题面

题意简述：

给定一个 \(1\) 到 \(n\) 的排列 \(a\)。在一次操作中，你可以选择一个满足 \(a_i 的下标 \(i(1 \leq i，删除 \(a_i\) 或 \(a_{i+1}\)。

你需要求出是否可能通过若干次操作使得 \(a\) 只剩下一个元素。

多组测试数据。

\(\texttt{Data Range:}1\le t\le 2\times 10^4,2\le n\le 3\times 10^5,\sum n\le 3\times 10^5,1\le a_i\le n\)。

结论是 \(a_1 < a_n\) 就有解，否则无解。

证明留给读者作为练习。

const int N = 300003;

int n, m;
int a[N];

int main()
{
    int T = gi();
    while (T--)
    {
    	n = gi();
    	for (int i = 1; i <= n; i+=1) a[i] = gi();
    	if (a[1] < a[n]) puts("YES");
    	else puts("NO");
    }
    return 0;
}

D - Replace by MEX

题面

题意简述：

给一个序列 \(a\)，每次操作可以选定一个位置 \(p\)，令 \(a_p=\) 这个序列的 \(\text{MEX}\)。你需要进行若干次操作，使得这个序列单调不降。操作次数不能超过 \(2\times n\)。

多组测试数据。

\(\texttt{Data Range:}1\le t\le 200,n \leq 1000,a_i \in [0,n]\)。

考虑把原序列变成 \(0,1,\dots,n-1\)。

每一次求出序列的 \(\text{MEX}\)，如果 \(\text{MEX}=n\)，那么找到一个没有匹配上的数将它替换；否则将 \(a_{\text{MEX}+1}\) 替换成 \(\text{MEX}\)。

const int N = 1003;

int n, m, a[N], ton[N];

inline bool check()
{
	for (int i = 1; i < n; i+=1) 
    	if (a[i] > a[i + 1])
    		return false;
    return true;
}

inline int MEX()
{
	for (int i = 0; i <= n; i+=1)
		if (!ton[i]) return i;
}

int main()
{
    int T = gi();
    while (T--)
    {
    	n = gi();
    	for (int i = 1; i <= n; i+=1) a[i] = gi();
    	if (check()) {puts("0\n"); continue;}
    	vector  ans;
    	while (1)
    	{
    		if (check()) break;
    		for (int i = 0; i <= n; i+=1) ton[i] = 0;
    		for (int i = 1; i <= n; i+=1)
    			++ton[a[i]];
    		int now = MEX();
    		if (now == n)
    		{
    			for (int i = 1; i <= n; i+=1)
    				if (a[i] != i - 1)
    				{
    					a[i] = now;
    					ans.push_back(i);
    					break;
    				}
    		}
    		else 
    		{
    			a[now + 1] = now;
    			ans.push_back(now + 1);
    		}
    	}
    	cout << ans.size() << endl;
    	for (auto x : ans) cout << x << ' ';
    	puts("");
    }
    return 0;
}