Codeforces Round 1024 (Div. 2)

Problem - A - Codeforces

思维题：

如果n不能整除p，就会多出一部分，这个部分可以作为调和者，使整个数组符合要求。

如果n能整除p，没有调和空间，只有看n/p*q==m

来看代码：

#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n, m, p, q;
		cin >> n >> m >> p >> q;
		if (n % p == 0&&n/p*q!=m)
		{
			cout << "NO" << endl;
		}
		else
		{
			cout << "YES" << endl;
		}


	}

}

Problem - B - Codeforces

题目大意：

数组的第一个数可以通过对数组任意数乘-1从而成为大小为n的数组 第n/2大的数吗？

解法：

为了方便处理，把数都先变为正数，第一个数赋值给man后，对数组arr进行从小大到大排序

查看man在排序后位置在哪？

1.在中位数之前，解法简单：不断让比man大的数乘-1变得比man小，就能让man到中位数的位置。

2.在中位数之后，此时无论把比man大的数*-1还是比man小的数*-1都不行，怎么办？

只有对所有数*-1，看看man倒着数是不是在中位数的位置

来看代码：

#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		vector<int>arr(n);
		for (int i = 0; i < n; i++)
		{
			cin >> arr[i];
			arr[i] = abs(arr[i]);
		}
		//一步登天
		int man = arr[0];
		int exp = (n + 1) / 2;
		exp -= 1;
		int flag = 0;
		sort(arr.begin(), arr.end());
		int now = 0;
		for (int i = 0; i < n; i++)
		{
			if (arr[i] == man)
			{
				now = i;
				break;
			}
		}
		if (now <= exp||n-1-now==exp)
		{
			flag = 1;
		}
		else
		{
			flag = 0;
		}

		if (flag)
		{
			cout << "YES" << "\n";
		}
		else
		{
			cout << "NO" << "\n";
		}
	}

}

Problem - C - Codeforces

一道构造题目，怎么排，才能把子网格相加的mex得到最大呢？

因为有mex机制在，大的数在内部起不到作用，所以
大的数在外围，小的数在内部。最小的数0放在最中间，这样能保证最多的mex能包括到它。

解法：

从大到小，从外向内 蛇形放数

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> constructGrid(int n)
{
    vector<vector<int>>grid(n, vector<int>(n, -1));
    int current = n * n - 1;
    int x = 0;
    int y = n - 1;
    int dir = 0;
    vector<int>dx = { 0,1,0,-1};
    vector<int>dy = { -1,0,1,0 };
                    //左 下 右 上
    int next_x;
    int next_y;
    for (int i = 0; i < n * n - 1; i++)
    {
        grid[x][y] = current--;
        next_x = x + dx[dir];
        next_y = y + dy[dir];

        if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= n || grid[next_x][next_y] != -1)
        {
            dir = (dir + 1) % 4;
            next_x = x + dx[dir];
            next_y = y + dy[dir];
        }
        x = next_x;
        y = next_y;
    }
    grid[n / 2][n / 2] = 0; // 中心位置填0
    return grid;
}

int main() {


    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        auto grid = constructGrid(n);
        for (const auto& row : grid) {
            for (int num : row) {
                cout << num << " ";
            }
            cout << endl;
        }
    }
    
    return 0;
}