比賽鏈接：CF1024

A. Dinner Time

只有當 $n$ 是 $p$ 的倍數而且 $\frac{n?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$ 先變成整數，然后找是否至少有 $?\frac{n}{2}?$ 個 $a_i(1\le i\le n)$ 大于等于 $a_1$ 即可。
• 如果有超過 $?\frac{n}{2}?$ 個 $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?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;
}