A
簡單題，每次找兩個最短的配對，取兩者 \(\min\)。實現上，對 \(a\) 從小到大排序，\(1 \to n\) 遍歷 \(i\)，每次將 \(a_i\) 累計入答案並對 \(i\) 迭代 \(+ 2\)。
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n; n = n * 2;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
std::sort(a.begin() + 1, a.end());
i64 ans = 0;
for (int i = 1; i <= n; i += 2) {
ans += a[i];
}
std::cout << ans << "\n";
return 0;
}B
數學解，以樣例為例，第一次走 \(x\)，你會發現接下來走的就是 \(n - x, x, n - 2x, n - 2x \dots\)，丟到幾何上，路徑之和就是 \((n - x) + x - \gcd(n, x) = n - gcd(n, x)\)，記得乘上 \(3\)。
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
i64 n, x;
std::cin >> n >> x;
std::cout << 3 * (n - std::__gcd(n, x)) << "\n";
return 0;
}C
比較好想的 C 了。肯定是要避免大量的 corner case，也就是不要嘗試算直徑出來之後去刪直徑。從確定直徑這件事入手，對目標長度 \(k\)
- \(k\) 為奇數，枚舉中心邊的兩個節點向下 DFS，距離中心邊兩端節點 \(\gt \frac{n - 1}{2}\)
- \(k\) 為偶數，更簡單了，枚舉中心點 \(u\) 向下 DFS，距離中心點 \(\gt \frac{n}{2}\)
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 2007;
constexpr int M = 4007;
constexpr int inf = 1e9;
int ecnt, head[N];
struct edge {
int to, nxt;
} e[M];
void addedge(int u, int v, int w = 1) {
e[++ecnt].nxt = head[u]; head[u] = ecnt; e[ecnt].to = v;
}
int n, d, ans;
int dfs(int u, int from, int dep, int lim) {
int ret = 0;
for (int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].to;
if (v != from)
ret += dfs(v, u, dep + 1, lim);
}
return (ret + (dep > lim ? 1 : 0));
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
memset(head, -1, sizeof(head));
std::cin >> n >> d;
for (int i = 1, x, y; i < n; i++) {
std::cin >> x >> y;
addedge(x, y);
addedge(y, x);
}
ans = inf;
if (d & 1) {
for (int i = 1; i <= n; i++) {
for (int j = head[i]; ~j; j = e[j].nxt) {
int v = e[j].to;
if (i < v)
ans = std::min(ans, dfs(i, v, 0, (d - 1) / 2) + dfs(v, i, 0, (d - 1) / 2));
}
}
} else {
for (int i = 1; i <= n; i++) {
ans = std::min(ans, dfs(i, 0, 0, d / 2));
}
}
std::cout << ans << "\n";
return 0;
}D
好的構造。
題意依託。形式化題意如下，定義兩個數列 \(a, b\)
- \(a_i, b_i \geq 0\)，且 \(\sum a = \sum b = n\)
- 當一個長度為 \(k\) 的序列被 \(a, b\)
現在只知道 \(a\) 是另一個長度為 \(m\) 的序列 \(A\) 的排列，需要找到一對新的數列 \(a, b\) 使得上述性質仍然成立。比如題目給的樣例 1，按 \(a\) 分塊則 \([1, 1]\) 迴文，\([2, 3]\) 迴文，也就是説對於序列 \(c\) 有 \(c_1 = c_1, c_2 = c_3\)，再看 \(b\)，\([1, 3]\) 迴文，此時又有 \(c_1 = c_3\)，綜合得到 \(c_1 = c_2 = c_3\)
發現每個長度為 \(l\) 的迴文塊都會產生 \(\lfloor \frac{l}{2} \rfloor\) 條作限制的邊，對於 \(n\) 個點，至少需要 \(n - 1\) 條邊才能聯通。對於奇數塊，如果一個塊的長度為奇數則相比偶數塊少連了一條邊，因為中間位置呈現一個自環，令 \(k_a, k_b\) 分別表示 \(a, b\) 中奇數塊的個數，總邊數為：\(\frac{n - k_a}{2} + \frac{n - k_b}{2} = n - \frac{k_a + k_b}{2}\)。同時要滿足 \(n - \frac{k_a + k_b}{2} \geq n - 1\) 即 \(k_a + k_b \leq 2\)。無解情況顯然，當 \(a\) 中的奇數塊數量超過 \(2\)。
考慮怎麼在兩個迴文塊之間溝通？一個波特的思路是，我們在每個塊伸出來一條邊連向下一個塊，這個比較抽象，可以自己用草稿紙手玩一下 \(l = 5, l = 6\)
構造方法是容易的，將 \(a\) 中的塊奇偶分類排序，兩個奇數丟頭部，偶數在中間連起來。對於目標 \(b\)，構造 \(a_1 + 1, a_2, a_3, \dots a_{n - 1}\) 出來，如果 \(a\) 的結尾奇數塊 \(\gt 1\)，就在結尾丟一個 \(a_n - 1\)，這樣構造出來的 \(b\) 奇數塊還會盡可能少，理想情況下為 \(0\)。
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(m + 1);
int cot = 0;
for (int i = 1; i <= m; i++) {
std::cin >> a[i];
cot += a[i] & 1;
}
if (cot > 2) { std::cout << "Impossible\n"; return; }
if (m == 1) {
if (a[1] == 1) {
std::cout << "1\n1\n1\n";
} else {
std::cout << a[1] << "\n";
std::cout << "2\n";
std::cout << 1 << " " << a[1] - 1 << "\n";
}
return;
}
std::sort(a.begin() + 1, a.end(), [](int x, int y) { return (x & 1) > (y & 1); });
std::cout << a[1] << " ";
for (int i = 3; i <= m; i++) {
std::cout << a[i] << " ";
}
std::cout << a[2] << "\n";
std::vector<int> b;
b.reserve(m);
b.push_back(a[1] + 1);
for (int i = 3; i <= m; i++) {
b.push_back(a[i]);
}
if (a[2] > 1) {
b.push_back(a[2] - 1);
}
std::cout << b.size() << "\n";
for (auto i : b) {
std::cout << i << " ";
}
std::cout << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
solve();
return 0;
}E
好的計數。轉化一下題意為求：
\[\sum_{i = 1}^{n} \sum_{j = i + 1}^{n} \binom{a_i + b_i + a_j + b_j}{a_i + a_j} \]
這個式子的意義為將對應兩包裝中的肉和菜視為完全相同的若干個位置，然後欽定 \(a_i + a_j\) 的位置為肉，剩餘的自動視為菜的方案數當然也可以欽定為 \(b_i + b_j\)
引入一個重要的推論：
\(\binom{x + y}{x}\) 的幾何意義為 \((0, 0) \to (x, y)\)
證明略去，很有用而且很有名的關於楊輝三角與組合數意義的對應。
由此可以設計一個原點到 \((a_i + b_i, a_j + b_j)\) 的方案數的 DP，但是你注意到仍然是 \(O(n^2)\) 的，和裸着做沒有區別。怎麼去掉 \(i, j\)
將整個座標平移 \((a_i, b_i)\)，相當於 \((0, 0) \to (-a_i, b_i), (a_i + a_j, b_i + b_j) \to (a_j, b_j)\)。由於矩形的長寬不變，路徑數不變，所以對答案是沒有影響的。令 \(f(x, y)\) 表示從任意起點 \((-a_i, -b_i)\) 走到 \((x, y)\) 的方案數，我們有初始狀態 \(f(-a_i, -b_i) = 1\)，轉移顯然：
\[f(x, y) = f(x - 1, y) + f(x, y - 1) \]
再來去重。從所有 \(f(i, j)\) 中，減去 \(i = j\) 的情況 \(\binom{2a_i + 2b_i}{2a_i}\)，剩下的就是 \(i \neq j\)
\[\frac{(\sum_{j = 1}^{n} f(a_i, b_i)) - (\sum_{i = 1}^{n} \binom{2a_i + 2b_i}{2a_i})}{2} \]
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 200010;
constexpr int M = 2000;
constexpr int D = 2010;
constexpr int P = 1e9 + 7;
constexpr int I = 500000004;
int n;
int a[N], b[N];
i64 fac[4 * M + 10], inv[4 * M + 10];
i64 dp[2 * D + 10][2 * D + 10];
i64 expow(i64 a, i64 b) {
i64 res = 1;
for (; b; b >>= 1) {
if (b & 1) res = res * a % P;
a = a * a % P;
}
return res;
}
void init() {
int maxn = 4 * M;
fac[0] = 1;
for (int i = 1; i <= maxn; i++) {
fac[i] = fac[i - 1] * i % P;
}
inv[maxn] = expow(fac[maxn], P - 2);
for (int i = maxn - 1; i >= 0; i--) {
inv[i] = inv[i + 1] * (i + 1) % P;
}
}
i64 C(int n, int m) {
if (m < 0 || m > n) return 0;
return fac[n] * inv[m] % P * inv[n - m] % P;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
init();
std::cin >> n;
for (int i = 1; i <= n; i++) {
std::cin >> a[i] >> b[i];
dp[D - a[i]][D - b[i]]++;
}
for (int i = 1; i <= 2 * D; i++) {
for (int j = 1; j <= 2 * D; j++) {
dp[i][j] = (dp[i][j] + dp[i-1][j] + dp[i][j-1]) % P;
}
}
i64 ans = 0;
for (int i = 1; i <= n; i++) {
ans = (ans + dp[D + a[i]][D + b[i]]) % P;
ans = (ans - C(2 * a[i] + 2 * b[i], 2 * a[i]) + P) % P;
}
ans = ans * I % P;
std::cout << ans << "\n";
return 0;
}F
好的腦電波。
對於某個排列 \(p\)
定義新排列 \(p'\) 滿足 \(p'_{p_i} = i\)，通過這樣的轉換得到原題中的 \(j - i \geq k, |p_i - p_j| = 1\) 變成了可以交換的兩個元素 \(p'_x, p'_{x + 1}\) 當且僅當 \(|p'_x - p'_{x + 1}| \geq k\)，此時“一段距離”在這裏變成了鄰項交換。
一個 key observation 是，在 \(p'\) 中大小相差 \(\lt k\)
考慮分治，對 \(p'\) 作歸併排序，合併左右序列時，要決定的是取左半部分的第一個元素還是右半部分的第一個元素，計算左半部分後綴最小值 \(m_i\)，如果 \(m_{l} \geq p'_{r} + k\)，取右半部分的元素，否則取左半部分的。由於 \(m_l\) 表示左半部分剩餘所有元素的最小值，如果這個元素的最小值都大於等於 \(a_r + k\)，意味着右半部分的當前元素比左半部分所有剩餘元素都小至少 \(k\)，顯然這些元素都可以放到左半部分元素之前不產生矛盾，通過這樣確保儘可能將較小的元素提前得到更小的字典序。
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 5e5 + 7;
int n, k;
int a[N], p[N], b[N], mn[N];
void merge(int l, int r) {
if (l == r)
return;
int mid = (l + r) >> 1;
merge(l, mid); merge(mid + 1, r);
int mnv = n;
for (int i = mid; i >= l; i--) {
mnv = std::min(mnv, a[i]);
mn[i] = mnv;
}
int cnt = l, p1 = l, p2 = mid + 1;
while (p1 <= mid && p2 <= r) {
if (mn[p1] >= a[p2] + k)
b[cnt++] = a[p2++];
else
b[cnt++] = a[p1++];
}
while (p1 <= mid)
b[cnt++] = a[p1++];
while (p2 <= r)
b[cnt++] = a[p2++];
for (int i = l; i <= r; i++)
a[i] = b[i];
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> k;
for (int i = 1, x; i <= n; i++) {
std::cin >> x;
a[x] = i;
}
merge(1, n);
for (int i = 1; i <= n; i++) {
p[a[i]] = i;
}
for (int i = 1; i <= n; i++) {
std::cout << p[i] << "\n";
}
return 0;
}