Codeforces Round 1024 (Div.2)

比赛链接：CF1024

A. Dinner Time

只有当 $n$ 是 $p$ 的倍数而且 $\frac{n\cdot q}{p}\ne m$ 时输出 NO，其余情况均满足条件。

时间复杂度：$O(1)$。

#include <bits/stdc++.h>
using namespace std;const int N = 105;
int n, m, p, q, a[N], sum[N];void solve() {cin >> n >> m >> p >> q;if (n % p == 0 && n / p * q != m) cout << "NO\n";else cout << "YES\n";
}int main() {ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);int T;cin >> T;while (T--) solve();return 0;
}

B. The Picky Cat

• 首先，$a_1$ 是否进行操作变成 $-a_1$ 并不影响最后答案是否存在。
• 所以，可以先把 $a_1$ 先变成整数，然后找是否至少有 $\lceil \frac{n}{2}\rceil$ 个 $a_i(1\le i\le n)$ 大于等于 $a_1$ 即可。
• 如果有超过 $\lceil \frac{n}{2}\rceil$ 个 $a_i(1\le i\le n)$ 大于等于 $a_1$，将其中一部分设为负数即可。

时间复杂度：$O(n)$。

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
int n, a[N];void solve() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i], a[i] = abs(a[i]);int tot = 1;for (int i = 2; i <= n; i++)tot += (a[1] <= a[i]);if (tot >= (n + 1) / 2) cout <<"YES\n";else cout << "NO\n";
}int main() {ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);int T;cin >> T;while (T--) solve();return 0;
}

C. Mex in the Grid

构造题。

• 可以发现只要不包含 $0$ 的子数组的 $MEX$ 都是 $0$，因此，为了让 $0$ 这个数尽可能多地在子数组中出现我们要把 $0$ 放在 $a_{\frac{n}{2},\frac{n}{2}}$。
• 为了最大化 $MEX$ 的和，我们要一层一层的往外放数字，因为这样能让所有以 $0$ 为中心的大小为 $i\cdot i$ 的子数组的 $MEX$ 的和最大。
• 在每一层放数字的时候，我们可以按照逆时针的顺序放置，这样在以 $0$ 为中心的正方形子数组中，能让有一些只包含某一块区域的子数组的 $MEX$ 更大。

时间复杂度：$O(n^2)$。

#include <bits/stdc++.h>
using namespace std;constexpr int N = 505;
int n, a[N][N], cnt = 0;
constexpr int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 };void solve() {cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) a[i][j] = 0;cnt = 1;int step = 1, d = 0;int x = (n + 1) / 2, y = (n + 1) / 2;while (cnt < n * n) {for (int i = 1; i <= step; i++) {x += dx[d], y += dy[d];a[x][y] = cnt++;}d = (d + 1) % 4;if (d == 0 || d == 2) step++;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) cout << a[i][j] << " ";cout << "\n";}
}int main() {ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);int T;cin >> T;while (T--) solve();return 0;
}

D. Quartet Swapping

法一：奇偶性

• 根据操作的性质，位于奇数位的数字只能交换到奇数位，位于偶数位的数字只能交换到偶数位。
• 最小的子序列一定是所有奇偶位置上的数字都分别从小到大排列。
• 但由于操作的最小长度是 $4$，只有 $[1,n-3]$ 里面的数字能够保证满足这个性质，最后 $3$ 位数字可能无法满足这个条件。
• 进一步观察交换操作可以得知，最后 $3$ 位数字，能否满足第二个条件，与奇偶位置上所有数字的逆序对的奇偶是否相同有关。如果两者逆序对数量的奇偶相同，那么最后 $3$ 位也能满足第二个条件；否则，无法满足条件。

时间复杂度：$O(n\log n)$。

#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;
int n, a, ans[N], t[N];void add(int x, int k) {while (x <= n) {t[x] += k;x += (x & (-x));}
}int query(int x) {int res = 0;while (x) {res += t[x];x -= (x & (-x));}return res;
}void solve() {cin >> n;vector<int> odd, even;for (int i = 1; i <= n; i++) {cin >> a;if (i & 1) odd.push_back(a);else even.push_back(a);}for (int i = 0; i <= n; i++) t[i] = 0;int num = 0;for (int i = odd.size() - 1; i >= 0; i--) {num += query(odd[i]);add(odd[i], 1);}for (int i = 0; i <= n; i++) t[i] = 0;for (int i = even.size() - 1; i >= 0; i--) {num -= query(even[i]);add(even[i], 1);}sort(odd.begin(), odd.end()), sort(even.begin(), even.end());for (int i = 0; i < (int)odd.size(); i++) ans[2 * i + 1] = odd[i];for (int i = 0; i < (int)even.size(); i++) ans[2 * i + 2] = even[i];if (num & 1) swap(ans[n - 2], ans[n]);for (int i = 1; i <= n; i++) cout << ans[i] << " "; cout << "\n";
}int main() {ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);int T;cin >> T;while (T--) solve();return 0;
}

法二：贪心

• 进行题目中的操作的本质是为了将后面较小的数字依次往前移，操作结果等价于 ($i$, $i+1)$, ($j$, $j+1$) 位置上的数字分别对应交换。
• 利用 $set$ 分别维护后面奇偶位置上的数字，从前往后分别将后面对应奇偶位置上最小的数字往前移动到当前位置即可。

时间复杂度：$O(n\log n)$。

#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;
int n, a[N], vis[N];void op(int x, int y) {swap(a[x], a[y]), swap(a[x + 1], a[y + 1]);vis[a[x]] = x, vis[a[y]] = y;vis[a[x + 1]] = x + 1, vis[a[y + 1]] = y + 1;
}void solve() {cin >> n;set<int> odd, even;for (int i = 1; i <= n; i++) {cin >> a[i], vis[a[i]] = i;if (i & 1) odd.insert(a[i]);else even.insert(a[i]);}for (int i = 1; i <= n - 3; i++) {if (i & 1) {int num = *odd.begin();odd.erase(odd.begin());if (vis[num] == n) op(n - 3, n - 1);op(i, vis[num]);} else {int num = *even.begin();even.erase(even.begin());if (vis[num] == n) op(n - 3, n - 1);op(i, vis[num]);}}for (int i = 1; i <= n; i++) cout << a[i] << " ";cout << "\n";
}int main() {ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);int T;cin >> T;while (T--) solve();return 0;
}