当前位置：首页 > news >正文

Codeforces Round 1024 (Div. 2)

news 2025/6/5 12:21:18

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; // 中心位置填0return 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;
}