# USACO 2025 Open Contest AA 競程 dreamoon 老師的參考做法
[TOC]
## Bronze
### [Problem 1. Hoof Paper Scissors Minus One](https://usaco.org/index.php?page=viewproblem&cpid=1503)
#### 題目敘述
在遊戲 Hoof Paper Scissors 中，Bessie 與 Elsie 各自從 $N$ 個不同的手勢(蹄式)中選一個（編號為 $1$ 到 $N$），並根據一張規則表，不同手勢間比賽時會有兩種結果：
* 一方勝出、另一方失敗
* 平手
而在 Hoof Paper Scissors Minus One 中，兩隻牛各自同時出示兩個手勢（左蹄一個、右蹄一個）。各自手勢都被對方看見後，他們再從自己的兩個手勢中選一個作為正式比賽所出的手勢，最後依照規則表決定勝負。
給定 Elsie 在每場比賽中預計要出的手勢組合（共 $M$ 場比賽），Bessie 想知道自己有多少種手勢組合可以保證一定能贏過 Elsie。這裡「手勢組合」指的是一個有序對 $(L, R)$，其中 $L$ 為左蹄的手勢，$R$ 為右蹄的手勢。
#### 輸入格式
第一行包含兩個空格分隔的整數：
* $N$：象徵總數 ($1 \le N \le 3000$)
* $M$：比賽場數 ($1 \le M \le 3000$)
接下來 $N$ 行：
* 第 $i$ 行包含 $i$ 個字元：$a_{i,1}a_{i,2}\dots a_{i,i}$，每個字元皆為以下三者之一：
* D：象徵 $i$ 與象徵 $j$ 平手
* W：象徵 $i$ 勝過象徵 $j$
* L：象徵 $i$ 輸給象徵 $j$
* 保證 $a_{i,i} = \texttt{D}$。
接下來 $M$ 行：
* 每行包含兩個空格分隔的整數 $s_1$ 與 $s_2$，表示 Elsie 本場比賽出的象徵組合。
#### 輸出格式
輸出 $M$ 行，每行包含一個整數代表在第 $i$ 場比賽 Bessie 有幾種手勢組合可以保證一定贏過 Elsie。
#### 測資額外限制
測資 2~6：$N, M \le 100$
測資 7~12：無額外限制
#### 參考做法
> 此題用到了 AA 競程 Level 1 的「競程數學」中的知識點。
假設 Bessie 出的左蹄和右蹄手勢編號分別為 $a$ 和 $b$，那麼 Bessie 一定能贏的情況就是 $a$ 同時贏過 $s_1$ 和 $s_2$ 或 $b$ 同時贏過 $s_1$ 和 $s_2$，用 C++ 的程式語法來寫就是：
```cpp
(s[a][s1] == 'W' && s[a][s2] == 'W') || (s[b][s1] == 'W' && s[b][s2] == 'W')
```
暴力枚舉 $a$ 和 $b$ 即可通過前 6 筆測資。
若要通過所有測資就要用點數學方法來計算 Bessie 一定能贏的組合數量。
首先，我們還是要先暴力計算有多少手勢是能同時贏過 $s_1$ 和 $s_2$ 的，令此數量為 $cnt$。
接著 Bessie 能贏的數量其實就是「全部可能的手勢組合數量」減去「不能贏的組合數量」
「全部的組合數量」可用乘法原理算出是 $N \times N$，而不能贏的組合數量就是 $a$ 和 $b$ 都不是那 $cnt$ 個能贏的手勢的組合，也能利用乘法原理算出此數樣為 $(N - cnt) \times (N - cnt)$，所以答案就是 $N \times N - (N - cnt) \times (N - cnt)$
#### 參考程式碼
```cpp=
#include <iostream>
#include <vector>
#define SZ(X) (int)(X).size()
using namespace std;
const int SIZE = 5000;
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int N, M;
cin >> N >> M;
vector<vector<char>> c(N + 1, vector<char>(N + 1));
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) {
cin >> c[i][j];
if (c[i][j] == 'D') {
c[j][i] = 'D';
} else if (c[i][j] == 'W') {
c[j][i] = 'L';
} else {
c[j][i] = 'W';
}
}
}
while (M--) {
int x, y;
cin >> x >> y;
int cnt = 0;
for (int i = 0; i < N; i++) {
if (c[i][x] == 'W' && c[i][y] == 'W') cnt++;
}
cout << N * N - (N - cnt) * (N - cnt) << '\n';
}
}
```
### [Problem 2. More Cow Photos](https://usaco.org/index.php?page=viewproblem&cpid=1504)
#### 題目敘述
今天牛群特別頑皮！ Farmer John（FJ）只想拍下排成一行的牛，但牠們總在快要拍照時移動。
具體來說，FJ 有 $N$ 隻牛 ($1 \le N \le 10^5$)，每隻牛都有一個介於 $1$ 到 $N$ 的整數高度。FJ 希望拍出一張牛的排列照片，要求牛的高度從左到右必須滿足以下三個條件：
1. **山形排列**：牛的高度必須先不降後不升。也就是說，存在一個位置 $i$ 使得 $h_1 \le h_2 \le \dots \le h_i \ge h_{i+1} \ge \dots \ge h_K.$
2. **相鄰不等**：相鄰的兩頭牛高度必須不同，即對所有 $1 \le i < K$ 有 $h_i \ne h_{i+1}$。
3. **對稱**：照片必須左右對稱。也就是說，若 $i+j=K+1$，則必須有 $h_i = h_j$。
FJ 可以移除部分牛，並重新排列剩下的牛。請求出 FJ 能夠在照片中包含的牛的最大數量，使得上述條件均被滿足。
#### 輸入格式
輸入包含多個測試案例。
- 第一行包含一個整數 $T$ ($1 \le T \le 10^5$)，表示測試案例數量。
- 接下來每個測試案例格式如下：
- 第一行：一個整數 $N$，表示牛的數量。
- 第二行：$N$ 個整數，分別表示每頭牛的高度，均介於 $1$ 到 $N$ 之間。
保證所有測試案例中 $N$ 的總和不超過 $10^6$。
#### 輸出格式
輸出 $T$ 行，每一行輸出一個整數，表示對應測試案例中 FJ 能在照片中包含的牛的最大數量。
#### 測試資料額外限制
- 測資 2-3：$T \le 100$, $N \le 7$
- 測資 4-5：$T \le 10^4$，所有牛的高度均不超過 $10$
- 測資 6-11：無額外限制
#### 參考做法
> 此題的參考做法用到了 AA 競程 Level 0 競程入門班的「用陣列紀錄資訊」單元以及 Level 1 的「簡易貪心」單元中的知識點。
先最高的牛的高度，以及用陣列把每個高度的牛各有幾隻算出來。
由於牛的排列必須是「山形排列」，且相鄰的兩隻牛又不能一樣，那把牛的身高列出來可能會是如下：
> 1 2 4 7 9 7 4 2 1
可發現除了最大的數字外，其他數字都是恰出現兩次。
既然我們要找的是最長的排列，那麼我們讓身高最大的牛站在正中央一定能找到解，令身高最大的牛高度為 $max\_h$，那麼對於所有 $i = 1 \sim max_h - 1$，只要身高 $i$ 的牛出現兩隻以上，我們就一定可以選其中兩隻出現在照片中，所以答案就是：
$$
\sum\limits_{i=1}^{max\_h-1} 2 \times [cnt[i] \ge 2]
$$
其中 $cnt[i]$ 代表身高為 $i$ 的牛有幾隻，$[\ ]$ 為 [艾佛森括號](https://zh.wikipedia.org/zh-tw/%E8%89%BE%E4%BD%9B%E6%A3%AE%E6%8B%AC%E8%99%9F)
#### 參考程式碼
```cpp=
#include <iostream>
#include <vector>
#define SZ(X) (int)(X).size()
using namespace std;
void solve() {
int N;
cin >> N;
vector<int> cnt(N + 1);
int max_h = 0;
for (int i = 1; i <= N; i++) {
int x;
cin >> x;
if (max_h < x) max_h = x;
cnt[x]++;
}
int ans = 1;
for (int i = 1; i < max_h; i++) {
if (cnt[i] >= 2) ans += 2;
}
cout << ans << '\n';
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int t;
cin >> t;
while (t--) solve();
}
```
### [Problem 3: It's Mooin' Time III](https://usaco.org/index.php?page=viewproblem&cpid=1505)
#### 題目敘述
Elsie 正試圖向 Bessie 描述她最喜愛的 USACO 競賽，但 Bessie 卻無法理解 Elsie 為何如此喜歡這個比賽。Elsie 說：「而且到了 mooin' time！誰想要來個 mooin'? 拜託，我只想參加 USACO。」
Bessie 仍然不懂，所以她將 Elsie 的描述記錄成一個長度為 $N$ ($3 \leq N \leq 10^5$) 的字串，字串由小寫英文字母組成，記作 $s_1 s_2 \ldots s_N$。Elsie 定義一個由三個字元組成的字串 $t$ 為 moo，當且僅當 $t_2 = t_3$ 且 $t_2 \neq t_1$。
一個三元組 $(i,j,k)$ 若滿足 $i < j < k$ 且字串 $s_i s_j s_k$ 構成一個 moo，則稱該三元組有效。對於一個有效三元組，FJ 會進行以下操作以計算其值：
- FJ 將字串 $s$ 在索引 $j$ 處旋轉 $90$ 度。
- 該三元組的值為三角形 $\Delta ijk$ 面積的兩倍。
換句話說，三元組的值為 $(j-i)(k-j)$。
Bessie 向你提出 $Q$ ($1 \leq Q \leq 3 \cdot 10^4$) 個查詢。在每個查詢中，她給出兩個整數 $l$ 與 $r$ ($1 \leq l \leq r \leq N$, 且 $r-l+1 \geq 3$)，要求你求出所有滿足 $l \leq i$ 且 $k \leq r$ 的有效三元組 $(i,j,k)$ 中，其值的最大值。如果不存在任何有效三元組，請輸出 $-1$。
<strong>注意：</strong> 此題中涉及到的整數數值可能非常大，因此在程式中可能需要使用 64 位整數型態（例如 C/C++ 中的 "long long"）。
#### 輸入格式
- 第一行包含兩個整數 $N$ 與 $Q$。
- 接下來一行包含字串 $s_1 s_2 \ldots s_N$。
- 接下來 $Q$ 行，每行包含兩個整數 $l$ 與 $r$，表示一次查詢。
#### 輸出格式
對每個查詢，輸出一行答案，即該查詢中最大有效三元組的值；若不存在有效三元組，輸出 $-1$。
#### 參考做法
> 此題的參考做法用到了 AA 競程 Level 1「簡易貪心」、「數列相關函式」單元以及 「Level 1 公開課」中的知識點。
首先對於每個詢問我們要枚舉三元組的第二第三個元素是哪個字元，只有 $26$ 種可能，每種可能各自算出最佳解後，再取最大的那個就是答案了。
接下來我們假設第二第三個元素對應的字母是 $c$。
首先我們可以用貪心的概念來縮小我們要考慮的三元組的數量，最後可發現對於每個 $c$，其實我們至多只要考慮 $2$ 個三元組，解説如下：
* 在知道在確定第二第三個字母是 $c$ 的情況，第一個字母一定是選區間 $[l, r]$ 中最左邊的不是 $c$ 的字母最好(假設此位置為 $first\_pos$)，最後一個字母則是選區間中最右邊的 $c$(假設次位置為 $last\_pos$)。而第二個字母一定是選越靠近 $mid = (first\_pos + last\_pos)/2$ 的位置越好，最靠近 $mid$ 的候補為只有兩個： $\ge mid$ 的最左邊位置以及 $< mid$ 的最右邊位置。
而 $first\_pos$ 的位置可讀入字串後，就先預處理 $nextDiff$ 陣列，$nextDiff[pos]$ 代表位置 $pos$ 右邊第一個和 $s[pos]$ 不一樣的字母位置，$nextDiff$ 陣列求法請參考範例程式碼。
如此一來，對於如果 $s[l]$ 不是 $c$，那麼 $first\_pos$ 就是 $l$，否則 $first\_pos$ 就是 $nextDiff[l]$。
而 $last\_pos$ 的求法可是先把所有字元 $c$ 的位置放入一個 vector 裡，然後使用 $upper\_bound$ 來求。
最後，靠近 $mid$ 的位置也可使用 $lower\_bound$ 函式來求出，於是此題的時間複雜度分析如下：
* 預處理 $nextDiff$ 陣列的時間為 $O(N)$
* 回答每個詢問的時間為 $O(字母集大小 \times \log{N})$
* 總時間複雜度為 $O(N + 字母集大小 \times \log{N})$
#### 參考程式碼
```cpp=
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define SZ(X) (X).size()
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
string s;
cin >> s; // 原始字串讀入時為 0-indexed，但我們後續用 1-indexed 處理
s = " " + s + " ";
// 預處理：計算 nextDiff 陣列 (1-indexed)
vector<int> nextDiff(N + 2, N + 1); // 設定 INF 為 N+1
nextDiff[N] = N + 1; // 最後一個位置無後續不同字元
for (int i = N; i >= 1; i--) {
if (s[i] != s[i + 1]) nextDiff[i] = i + 1;
else nextDiff[i] = nextDiff[i + 1];
}
// 對每個字母建立出現位置陣列（1-indexed）
vector<vector<int>> pos(26);
for (int i = 1; i <= N; i++) {
char c = s[i];
pos[c - 'a'].push_back(i);
}
// 處理每個查詢
while (Q--) {
int l, r;
cin >> l >> r;
ll ans = -1;
// 枚舉每個字母作為三元組第二和第三個位置的值的情況，分別求最佳解
for (char c = 0; c < 26; c++) {
// 先求出當第二第三個字元是 c 時， [l, r] 間可作為第一個字元的位置的最左邊的位置
int first_pos = l;
if (s[l] == c + 'a') {
first_pos = nextDiff[l];
}
// 如果第一個字母可能的最左邊位置都大於 r - 2，一定無解
if (first_pos > r - 2) continue;
auto &vec = pos[c];
// 利用 upper_bound 求出該三元組第三個元素在 [l, r] 可出現的最右邊的位置，若有解選最右邊的位置一定是最佳解
auto itR = upper_bound(vec.begin(), vec.end(), r);
if (itR == vec.begin()) continue;
itR--;
if (*itR <= first_pos) continue;
int last_pos = *itR; // last_pos 為最 [l, r] 內最右邊可能是 c 的位置
int mid = (first_pos + last_pos) / 2; // 最佳解只出現在三元組第二個元素 >= mid 的最小位置或 < mid 的最大位置
int mid_index = lower_bound(vec.begin(), vec.end(), mid) - vec.begin();
for (int j = max(0, mid_index - 1); j <= mid_index && j < SZ(vec); j++) {
if (vec[j] > first_pos && vec[j] < last_pos) {
ans = max(ans, (vec[j] - first_pos) * 1LL * (last_pos - vec[j]));
}
}
}
cout << ans << "\n";
}
return 0;
}
```
## Silver
### [Problem 1: Sequence Construction](https://usaco.org/index.php?page=viewproblem&cpid=1506)
#### 題目敘述
給你兩個正整數 $M, K$ ($1 \le M \le 10^9, 1 \le K \le 31$)，請構造一個非負整數數列 $a_1, a_2, \ldots, a_N$ 滿足以下條件：
1. $1 \le N \le 100$
2. $\sum\limits_{i=1}^N a_i = M$
3. $popcount(a_1)\ xor\ popcount(a_2)\ xor\ \ldots\ xor\ popcount(a_N) = K$ ($popcount(x)$ 指的是 $x$ 寫成二進制後，有幾個位數是 $1$, $xor$ 則是按位元互斥或)
#### 參考做法
> 此題的參考做法免強算是用到了 AA 競程 Level 1「簡易貪心」吧...
這種莫名其妙的構造題，感覺就是用來防 chatGPT 用的 XD
題目只有兩個參數 $M$ 和 $K$，不妨先固定其中一個參數，想想看另一個參數在什麼時候會有解，尤其時去思考看看有解時該參數的極小極大值會是什麼
例如我們可以固定 $K$，思考看看對於同一個 $K$ 值，$M$ 最小能多小。
由於 $K$ 是所有 $a_i$ 位元 $1$ 的數量 xor 起來的結果，那也就是說，如果 $K$ 二進制最高位是 $h$，那麼無論如何都至少要有一個 $a_i$ 含有的 位元 $1$ 的數量是 $2^h$ 以上了。
這樣想下去大概能發現 $M$ 最小的情況會發生在 所有的 $popcount(a_i)$ 都是 $2$ 的冪次方，且 $popcount(a_1)\ +\ popcount(a_2)\ +\ \ldots\ +\ popcount(a_N) = K$ 的時候，於是我們就能夠貪心地算出給定 $K$ 時，$M$ 的可能最小值，令此值為 $f(K)$。
接著分 $4$ 種情況討論。
1. 當 $M \le f(K)$，無解。
2. 當 $M \ge f(K)$，且 $M - f(K)$ 是偶數時，我們就只要先把輸入為 ``f(K) K`` 的解構造出來，最後數列 $a$ 再加上兩個 $(M - f(k))/2$ 就是答案了。
3. 當 $M \ge f(K)$，且 $M - f(K) = 1$ 時，又有兩種情況：
1. 若輸入為 ``f(K) K`` 的解有某個 $a_i = 1$，那把此 $a_i$ 改成 $2$，此 $a_i$ 的位元 $1$ 數量不會改變，但 $a_i$ 的總和增加 $1$ 了，所以也會是現在的輸入的解。
2. 若輸入為 ``f(K) K`` 的解不存在任何一個 $a_i = 1$，那麼就無解，因為要讓題目要求的第三個條件不變的情況，並要把 $a_i$ 的總和變大，增加的量不可能只有 $1$。
4. 當 $M \ge f(K)$，且 $M - f(K)$ 是 $\ge 3$ 的奇數時，首先先把輸入為 ``f(K) K`` 的解構造出來，然後發現 $a$ 再增加 $1, 2$ 這兩個數字後，題目要求的第三個條件的 xor 結果也不會改變，但 $a_i$ 的數字和增加了 $3$，接著，若要再讓 $a_i$ 的總和增加某個 $d$($d$ 是偶數)，就只要把數列 $a$ 的再加入 $2$ 個 $d/2$ 即可。
#### 參考程式碼
```cpp=
// 16 min
#include <iostream>
#include <vector>
#define SZ(X) (int)(X).size()
using namespace std;
void solve() {
int M, K;
cin >> M >> K;
vector<int> a;
int sum = 0;
for (int i = 0; i < 5; i++) {
if ((K >> i) & 1) {
a.push_back((1 << (1 << i)) - 1);
sum += a.back();
}
}
if (sum > M) {
cout << "-1\n";
return;
}
if ((M - sum) % 2 == 0) {
a.push_back((M - sum) / 2);
a.push_back((M - sum) / 2);
} else {
if (M - sum == 1) {
if (a[0] == 1) a[0]++;
else {
cout << "-1\n";
return;
}
} else {
int d = M - sum - 3;
a.push_back(2);
a.push_back(1);
a.push_back(d / 2);
a.push_back(d / 2);
}
}
cout << SZ(a) << '\n';
for (int i = 0; i < SZ(a); i++) {
cout << a[i] << (i + 1 < SZ(a) ? ' ' : '\n');
}
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int t;
cin >> t;
while (t--) solve();
}
```
### [Problem 2: Compatible Pair](https://usaco.org/index.php?page=viewproblem&cpid=1507)
#### 題目敘述
有非常多隻牛，每個牛都有一個數字代表他的 ID，但有可能有一些牛共用同個 ID。給你正整數 $N$，代表共有 $N$ 種不同的 ID，第 $i$ 種 ID 對應的數字是 $d_i$，並且有 $n_i$ 隻牛的 ID 是 $d_i$ ($1 \le n_i \le 10^9, 0 \le d_i \le 10^9$)。
給你兩個數字 $A, B$ ($0 \le A \le B \le 2 \times 10^9$)，兩隻牛若他們的 ID 加起來為 $A$ 或 $B$ 的話，這兩隻牛就可以湊成一對，每隻牛至多只能和其他一隻牛湊成一對，請問所有牛至多可湊成幾對？
#### 參考做法
> 此題的參考做法用到了 AA 競程 Level 1「簡易貪心」和「關聯容器」單元裡的知識點
可把每個 ID 都視為圖論上的點，若兩個相異的 ID 可以配對就連一條邊，若一個 ID 自己和自己能配對，就把該點視為「特殊的點」。可發現此圖的每個點度數至多只有 $2$，且不會有環，也就是說此圖是由很多條鏈(整個連通塊本身就是一條路徑(path) 的子圖)構成。
每條鏈之間是互相不影響的，所以可分開考慮，算出各條鏈的答案再加總起來即可。
對於一條鏈，至少會有一個度數為 $1$ 的端點不是「特殊的點」，可發現優先把此點對應的 ID 的牛和他們唯一能配對 ID 的牛配對一定不會比較差，配完後，就可把此點移除，接下來一直做一樣的事，直到最後只剩下特殊的點，再把特殊的點對答案的貢獻算上即可。
存在各式各樣的實作方式，範例程式碼用 dfs 的概念實作。
#### 參考程式碼
```cpp=
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define SZ(X) (int)(X).size()
using namespace std;
map<int, int> cnt; // cnt[x] 紀錄 ID 為 x 的牛還有幾隻尚未被配對到
map<int, int> vis; // 紀錄一個點是否已被拜訪過
set<int> special_p; // speicial_p 紀錄那些可以和相同 ID 的牛配對的 ID
map<int, vector<int>> e; // 若 ID 為 x 的牛可以和 ID 為 y 的牛配對，那麼 e[x] 裡會含有 y
long long ans;
void dfs(int x) {
for (int y : e[x]) {
if (vis[y]) continue;
vis[y] = 1;
int mi = min(cnt[x], cnt[y]);
cnt[x] -= mi;
cnt[y] -= mi;
ans += mi;
dfs(y);
}
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int N, A, B;
cin >> N >> A >> B;
for (int i = 0; i < N; i++) {
int n, d;
cin >> n >> d;
cnt[d] = n;
}
for (auto [d, n] : cnt) {
for (int x : {A - d, B - d}) {
if (d == x) special_p.insert(d);
else {
auto it = cnt.find(x);
if (it != cnt.end()) {
e[d].push_back(x);
}
}
}
}
for (auto &[x, vi] : e) {
// 若發現一個點度數是 1 且尚未被拜訪過，且不是「特殊的點」，就從它開始 dfs
// 每次枚舉到一條邊，就把該邊對應到的兩個 ID 的牛能配多少就配多少
if (SZ(vi) == 1 && !vis[x] && special_p.find(x) == special_p.end()) {
dfs(x);
}
}
// 最後還要考慮相同 ID 能配的牛
for (int d : special_p) {
ans += cnt[d] / 2;
}
cout << ans << '\n';
}
```
### [Problem 3: Ski Slope](https://usaco.org/index.php?page=viewproblem&cpid=1508)
#### 題目敘述
Bessie 與她的朋友們準備去滑雪旅行。這座山上有 $N$ 個「中繼點」（waypoints），分別標記為 $1, 2, \ldots, N$，海拔依照編號遞增（其中中繼點 $1$ 在山底）。
對於每個中繼點 $i$，都有一條滑雪道從 $i$ 處開始，一直延伸到 $p_i$ ($1 \le p_i < i$) 處。每條滑雪道各自有一個「難度」（difficulty） $d_i$ 與「樂趣」（enjoyment） $e_i$，其中
- $0 \le d_i \le 10^9$
- $0 \le e_i \le 10^9$
Bessie 有 $M$ 位朋友（$1 \le M \le 10^5$），他們將依照以下方式滑雪：
- 每位朋友選擇一個起始中繼點 $i$；
- 從該中繼點開始，沿著滑雪道依序往下滑（$i \to p_i \to p_{p_i} \to \dots$），最終抵達中繼點 $1$。
對於滑過的每一條滑雪道，朋友所獲得的「樂趣」會累加；整段旅程的總樂趣即為沿途所有滑雪道的樂趣總和。
不過，每位朋友也有自己不同的「技能值」（skill） $s_j$ 與「勇氣值」（courage） $c_j$，範圍為：
- $0 \le s_j \le 10^9$
- $0 \le c_j \le 10$
第 $j$ 位朋友只能選擇路徑上難度超過 $s_j$ 的滑雪道至多只有 $c_j$ 條的路徑。
你的任務是：對於每位朋友，計算他能獲得的最大樂趣總和。
---
#### 輸入格式
1. 第一行輸入單一整數 $N$（$1 \le N \le 10^5$），表示中繼點的數量。
2. 接下來從第 2 行到第 $N$ 行（共 $N-1$ 行），每行包含三個以空格分隔的整數：
- $p_i$：第 $i$ 個中繼點有滑雪道通往中繼點 $p_i$
- $d_i$：第 $i$ 個中繼點的滑雪道的「樂趣」
- $e_i$：第 $i$ 個中繼點的滑雪道的「難度」
3. 接著讀入一行，包含單一整數 $M$（$1 \le M \le 10^5$），表示 Bessie 的朋友人數。
4. 之後的 $M$ 行中，每行包含兩個以空格分隔的整數：
- $s_i$：第 $i$ 位朋友的技能值
- $c_i$：第 $i$ 位朋友的勇氣值
#### 其他說明
- 由於本題中可能出現非常大的整數運算，建議在程式實作時使用 64 位整數型態（例如 C/C++ 中的 `long long`）以避免溢位。
#### 參考做法
> 此題的參考做法用到了 AA 競程 Level 2「深度優先搜索(DFS)」和 Level 1「關聯容器」單元裡的知識點，並假設大家已有 DFS 的 backtracking(回溯法) 的概念
首先注意到一個重點：
若第 $j$ 位朋友可以從中繼點 $i$ 出發，代表著：「該條路徑難度第 $c_j+1$ 大(從 $1$ 開始編號) 的滑雪道值小於等於 $s_i$。」
於是若不管時間複雜度，我們可以有個 $O(N^2M)$ 的做法如下：
> 每個朋友的答案各自計算，再枚舉所有中繼點 i 作為起點的情況，搜集該路徑所有滑雪道難度，求出第 c_i + 1 大的難度值，若該值 <= s_i，那麼此路徑的「樂趣」總和就能更新此位朋友的答案
接著我們來一步一步優化此做法。
**1. 利用DFS+回溯的概念優化**
上述比較暴力的做法是每個朋友都要獨立計算一次，但每次計算都要重新算一次每條路徑第 $c_j+1$ 大的困難度，況且 $c_j$ 的值其實只有 $11$ 種，若可以一剛開始就算出來，那對時間複雜度優化肯定是有幫助的。
這部分我們可使用 DFS+回溯的概念，改成從 $1$ 號中繼點當起點 DFS，並在全域維護一個 multiset，儲存 DFS 時起點到當前點路徑上所有滑雪道的難度，這樣 DFS 時每走到一個中繼點 $i$，就能求出 $1$ 好中繼點到 $i$ 號中繼點的路徑中前 $11$ 大困難度的值了。這部分總時間複雜度只要 $O(N log N)$ (此時間複雜度的計算是把 $11$ 當常數)
**2. 把資料整理成單調序列，以便利用 upper_bound 優化
接著，對於相同 $c_j$ 值，我們回溯後可以得到許多個 pair $(x, y)$，代表若第 $j$ 位朋友的技能值($s_j$) 大於等於 $x$，就可以有總和為 $y$ 的「樂趣」，若存在兩個 pair $(x1,y1)$ 和 $(x2, y2)$，若 $x2 \ge x1$ 但 $y2 < y1$ ，那麼 $(x2, y2)$ 至個 pair 就不需要考慮了，因為他不會比 $(x1, y1)$ 還好。於是我們可先把所有 pair 按照 $x$ 值排序，排完後，再把剛才說不需要考慮的那些 pair 移除，剩下的 pair 就會隨著 $x$ 的遞增，$y$ 也是遞增的。於是對於每個詢問，我們就可以使用 upper_bound 找到 $\le s_i$ 的最大的 $x$ 的 pair，此 pair 的 $y$ 值就是該詢問的答案。
#### 參考程式碼
```cpp=
#include <algorithm>
#include <array>
#include <iostream>
#include <set>
#include <vector>
#define SZ(X) (int)(X).size()
using namespace std;
using ll = long long;
const int SIZE = 1 << 17;
struct Edge {
int y, difficulty, enjoyment;
};
vector<Edge> e[SIZE];
multiset<int> difs;
vector<array<ll, 2>> pp[11];
void dfs(int x, ll len) {
auto it = difs.rbegin();
for (int i = 0; i <= 10; i++) {
if (it != difs.rend()) {
pp[i].push_back({*it, len});
it++;
} else {
pp[i].push_back({0, len});
}
}
for (int i = 0; i < SZ(e[x]); i++) {
difs.insert(e[x][i].difficulty);
dfs(e[x][i].y, len + e[x][i].enjoyment);
difs.erase(difs.find(e[x][i].difficulty));
}
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int N;
cin >> N;
for (int i = 2; i <= N; i++) {
int p, d, en;
cin >> p >> d >> en;
e[p].push_back({i, d, en});
}
dfs(1, 0);
for (int i = 0; i <= 10; i++) {
sort(pp[i].begin(), pp[i].end());
ll last_v = -1;
int it = 0;
vector<array<ll, 2>> tmp;
for (int j = 0; j < SZ(pp[i]); j++) {
if (pp[i][j][1] <= last_v) continue;
last_v = pp[i][j][1];
tmp.push_back(pp[i][j]);
}
pp[i].swap(tmp);
}
int M;
cin >> M;
while (M--) {
int s, c;
cin >> s >> c;
auto pos = upper_bound(pp[c].begin(), pp[c].end(), array<ll, 2>{s + 1LL, -1LL}) - pp[c].begin();
pos--;
if (pos < 0) cout << "0\n";
else {
cout << pp[c][pos][1] << '\n';
}
}
}
```
## Gold
### [Problem 1: Moo Decomposition](https://usaco.org/index.php?page=viewproblem&cpid=1509)
#### 簡要題意
輸入給你三個正整數 $K, N, L$ ($1 \le N, K \le 10^6, 1\le L \le 10^{18}$)，以及給你一個長度為 $N$ 且由英文大寫字母 `'M'` 和 `'O'` 組成字串 $s$，而你要處理的真正字串是由 $s$ 複製 $L$ 次接起來的字串。例如說，當 $s = $ `"MOMOOO"`，$L = 3$，那麼你要處理的真正字串是：`"MOMOOOMOMOOOMOMOOO"`。
定義 $MOO$ 字串是由一個 `'M'` 後面接上 $K$ 個 `'O'` 形成的字串。
現在請你回答以下問題：
要把 $s$ 複製 $L$ 次接起來的字串拆成很多個子序列，使得每個子序列都是長度為 $MOO$ 字串，請問有幾種拆法？(保證至少有 $1$ 種拆法) 請輸出答案除以 $10^9+7$ 的餘數。
例如，當 $K=2,N=4,L=1$ 且 $s=$ `"MOMOOO"`，就有 $3$ 種拆法：
1. 第一個子序列位置是 $1,2,4$，第二個子序列位置是 $3,5,6$
2. 第一個子序列位置是 $1,2,5$，第二個子序列位置是 $3,4,6$
3. 第一個子序列位置是 $1,2,6$，第二個子序列位置是 $3,4,5$
#### 參考做法
> 此題的參考做法用到了 AA 競程 Level 4「特殊 DP 題型」裡所介紹的組合數相關知識。
看完這道題我第一個想法是：「這道題放在金組也太簡單了吧...」
首先，由於題目保證至少有一種拆法，所以字串 $s$ 裡 `'O'` 的數量一定是 `'M'` 的 $K$ 倍，接著 $L$ 這個參數對此題難度的影響非常少，因為可發線每個子序列一定是在同一份複製出來的 $s$ 裡，所以 $s$ 複製 $L$ 次的答案其實就是只有一個 $s$ 的答案的 $L$ 次方。
最後來解說要怎麼計算當 $L = 1$ 時的答案。
我們只要從右往左枚舉字串裡的每個字元，並用一個變數 $cnt$ 紀錄目前有多少個被枚舉到的字母 `'O'` 還沒被確定是放在哪個子序列裡，而當我們枚舉到 `'O'` 時 $cnt$ 就增加 $1$；而當枚舉到 `'M'` 時，我們就決定這個 `'M'` 後面要接哪些字母 `'O'`，因為還有 $cnt$ 個字母 `'O'` 還沒決定要放在哪個子序列，所以我們就有 $cnt \choose K$ 種選擇方式，可直接把此值乘上答案後，在把 $cnt$ 的值減少 $K$ 即可。時間複雜度為 $O(N)$。
#### 參考程式碼
```cpp=
#include <algorithm>
#include <iostream>
#include <vector>
#define SZ(X) (int)(X).size()
using namespace std;
const int MOD = (int)1e9 + 7;
const int SIZE = 1'000'001;
long long mypow(long long x, long long y, int mod = MOD) {
x %= mod;
long long res = 1 % mod;
while (y) {
if (y & 1) res = res * x % mod;
y >>= 1;
x = x * x % mod;
}
return res;
}
long long fac[SIZE];
void pre() {
fac[0] = 1;
for (int i = 1; i < SIZE; i++) fac[i] = fac[i - 1] * i % MOD;
}
long long C(long long x, long long y) {
if (y < 0 || y > x) return 0;
return fac[x] * mypow(fac[y] * fac[x - y], MOD - 2) % MOD;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
pre();
int K, N;
long long L;
cin >> K >> N >> L;
string s;
cin >> s;
long long ans = 1;
int cnt = 0;
for (int i = SZ(s) - 1; i >= 0; i--) {
if (s[i] == 'O') cnt++;
else {
ans = ans * C(cnt, K) % MOD;
cnt -= K;
}
}
cout << mypow(ans, L) << '\n';
}
```
### [Problem 2: Election Queries](https://usaco.org/index.php?page=viewproblem&cpid=1510)
#### 簡要題意
給你一個長度為 $N$ 的數列，$a_1, a_2, \ldots, a_N$，接下來有 $Q$ 次詢問，每次詢問都會給你兩個正整數 $i, x$ 代表你要把 $a_i$ 的值改為 $x$，請你回答以下問題：
請把數列 $a$ 拆成兩個非空的子序列，使得此兩子序列的眾數的差的絕對值盡可能大(如果眾數有很多個，可以任取一個)。舉例來說，數列 $1, 4, 1, 5, 4, 4, 4$
#### 參考作法
> 此題的參考做法用到了 AA 競程 Level 5「根號資料結構與演算法」單元的知識點
先提一下，我覺得出題者使用的方法極可能和我的方法不一樣，這種複雜的資料結構題通常都有好多種做法。
---
定義 $cnt[x]$ 代表數字 $x$ 在 $a$ 裡出現幾次。
先介紹 4 個觀察：
1. 若數字 $x$ 和數字 $y$ 可以成為兩個子序列的眾數，那麼
$cnt[x] + cnt[y] \ge \max\limits_{i=1\sim N}{cnt[i]}$
因為你只要把全部的 $x$ 放在第一個子序列，全部的 $y$ 放在第二個子序列，然後剩下的每個數字就好好的分配到兩個子序列，使得在第一個子序列的數量不要超過 $cnt[x]$，在第二個子序列的數量不要 $cnt[y]$ 即可。
2. $cnt[x]$ 的不同的值的數量為 $O(\sqrt{n})$，這是老梗就不解釋了。
3. 定義集合 $S_i = \{x | cnt[x]=i\}$，對於每個 $S_i$，利用貪心的概念，在計算答案時，都只要考慮 $S_i$ 中最大和最小的數字即可，綜合第 2 個觀察，每個詢問我們都只要考慮 $O(\sqrt{n})$ 個數字。
4. 如果兩個子序列裡的眾數只需要從其中 $O(\sqrt{n})$ 個數去考慮，且這些數已經根據 $cnt[x]$ 的值排序好的話，那我們很容易用雙指標一類的方法 $O(\sqrt{n})$ 算出答案。
有了第 $4$ 個觀察後，如果我們有辦法每個詢問都只花 $O(\sqrt{n})$ 的時間把這 $O(\sqrt{n})$ 個要考慮的數字找出來，那麼此題就可以用 $O(Q \sqrt{N})$ 的時間解決啦！
而要找到這些要考慮的數字，其實只要找到所有非空的 $S_i$ 的索引值即可。
至於這件事我們要用根號分塊來解決。
在程式碼裡，我們會真的使用 STL 的 set 表示觀察 3 裡的 $S_i$(程式碼裡叫做 $ids[i]$)，可以發現，每個詢問裡只會改變兩個數字的數量，也就是至多會變動到 $4$ 個 $S_i$。
有了這樣的觀察後其實就有很多種解決方式了，這裡只介紹我程式碼使用的方法：
把集合 $S_i$ 每 $GROUP\_SIZE$ 個一組，並用集合 $exist\_number[j]$ 儲存第 $j$ 組中非公的 $S_i$ 的索引值。
每個詢問都變動到的 $S_i$ 至多只會出現在 $4$ 組裡，再用 $O(GROUP\_SIZE)$ 的時間暴力更新這幾組的 $exist\_number[i]$，更新完後，在用 $O(N/GROUP\_SIZE+\sqrt{N})$ 的時間把所有集合 $exist\_number[i]$ 裡的索引值按照小到大搜集起來即可。
細節請直接參考程式碼。
#### 參考程式碼
```cpp=
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#define SZ(X) (int)(X).size()
using namespace std;
const int SIZE = 200'001;
const int GROUP_SIZE = 512;
int N;
int cnt[SIZE];
set<int> ids[SIZE]; // ids[i] 紀錄所有出現在 a 裡數量為 i 的數字
// exist_number[j][*] 紀錄 S 集合序列中第 $j$ 組裡非空集合的編號們
// exist_num[j] 是第 $j$ 組裡非空的集合數量
int exist_number[GROUP_SIZE][GROUP_SIZE];
int exist_num[GROUP_SIZE];
void add(int x) {
int id = x / GROUP_SIZE;
exist_number[id][exist_num[id]++] = x;
}
// 重新計算 $S$ 集合序列中第 seg_id 組有哪些非空集合
void recalc(int seg_id) {
exist_num[seg_id] = 0;
for (int i = seg_id * GROUP_SIZE; i < seg_id * GROUP_SIZE + GROUP_SIZE && i <= N; i++) {
if (SZ(ids[i])) add(i);
}
}
int hid[SIZE], a[SIZE];
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int Q;
cin >> N >> Q;
for (int i = 1; i <= N; i++) {
cin >> a[i];
cnt[a[i]]++;
}
for (int i = 1; i <= N; i++) {
if (cnt[i]) ids[cnt[i]].insert(i);
}
for (int i = 1; i <= N; i++) {
if (SZ(ids[i])) {
add(i);
}
}
while (Q--) {
int i, x;
cin >> i >> x;
if (a[i] != x) {
set<int> tmp;
ids[cnt[a[i]]].erase(a[i]);
if (ids[cnt[a[i]]].empty()) tmp.insert(cnt[a[i]] / GROUP_SIZE);
cnt[a[i]]--;
if (cnt[a[i]]) {
if (ids[cnt[a[i]]].empty()) tmp.insert(cnt[a[i]] / GROUP_SIZE);
ids[cnt[a[i]]].insert(a[i]);
}
if (cnt[x]) {
ids[cnt[x]].erase(x);
if (ids[cnt[x]].empty()) tmp.insert(cnt[x] / GROUP_SIZE);
}
cnt[x]++;
if (ids[cnt[x]].empty()) {
tmp.insert(cnt[x] / GROUP_SIZE);
}
ids[cnt[x]].insert(x);
a[i] = x;
for (int seg_id : tmp) {
recalc(seg_id);
}
}
// 以下這段程式碼會把所有非空的 S_i 的 i 值搜集起來放在 hid 陣列裡
int hn = 0;
for (int i = 0; i * GROUP_SIZE <= N; i++) {
for (int j = 0; j < exist_num[i]; j++) {
hid[hn++] = exist_number[i][j];
}
}
int bb = hid[hn - 1];
int j = hn - 1;
int mi = 1e9;
int ma = -1e9;
int ans = 0;
// 用雙指標計算答案
for (int i = 0; i < hn; i++) {
while (j >= 0 && hid[j] + hid[i] >= bb) {
ma = max(ma, *ids[hid[j]].rbegin());
mi = min(mi, *ids[hid[j]].begin());
j--;
}
ans = max(ans, ma - *ids[hid[i]].begin());
ans = max(ans, *ids[hid[i]].rbegin() - mi);
}
cout << ans << '\n';
}
}
```
### [Problem 3: OohMoo Milk](https://usaco.org/index.php?page=viewproblem&cpid=1511)
#### 簡要題意
有一個長度為 $N$ 的數列 $m_1, m_2, \ldots, m_N$ ($1 \le m_i \le 10^9$)，Bessie 和 Elsie 根據此數列完以下遊戲：
1. 遊戲共有三個參數 $D, A, B$ ($1 \le A < B \le N, 1 \le D \le 10^9$)。
1. 遊戲共會進行 $D$ 輪。
2. 每一輪開始時，首先 Bessie 會把數列 $m$ 的其中 $A$ 個數增加 $1$，接著 Elsie 會把其中 $B$ 個大於 $0$ 的數減 $1$。
3. 遊戲最終分數的計算方式為 $\sum\limits_{i=1}^N m_i$，Bessie 的目標是讓分數盡可能高，而 Elsie 的目標是讓分數盡可能小
假設 Bessie 和 Elsie 都採取最佳策略，請問遊戲最終分數會是多少？
#### 參考作法
> 此題的參考做法用到了 AA 競程 Level 2「二分搜常見題型」單元的知識點
首先，可用貪心的思維證明在最佳策略中， Bessie 一定是選 $m$ 中最大的 $A$ 個數增加 $1$，而 Elsie 也會是選 $m$ 中最大的 $B$ 個數減 $1$，就結論而言，每一輪操作會是數列 $m$ 中第 $B+1$ 大的數至第 $A$ 大的數都增加 $1$。
那麼除了最大的 $A$ 個數以外的數肯定是維持不變的，就先把他們忽略，最終答案再加上這些數的平方和，所以我們就直接當作數列 $m$ 長度為 $A$，每次操作則是會把數列裡最小的 $A-B$ 個數增加 $1$。
但這題困難的點在於回合數實在太多了，那該怎麼辦呢？
**(以下已經把數列 m 的長度視為 A 了)**
模擬一些 case 後可發現，由於我們一定是盡可能讓比較小的數變大，最終數列 $m$ 的長相一定是存在某個數字 $x$，原本數列 $m$ 裡小於等於 $x$ 的 $m[i]$ 都會變為 $\min(m[i] + D, x)$，或是變為 $x+1$ (一定變為這樣的證明請參考 [CF1551 B2. Wonderful Coloring - 2](https://codeforces.com/problemset/problem/1551/B2) 的題解，其實和這題 Codeforces 題是樣的東西)，那我們就去二分搜這個 $x$ 值即可，也就是說，要找到最大的 $x$，使得 $\sum_{i=1}^A max(0, min(x-m[i], D)) \le D \cdot (A-B)$，二分搜求出 $x$ 值之後，就不難得到數列 $m$ 的最終長相，然後就可以算出最終得分。
#### 參考程式碼
```cpp=
#include <algorithm>
#include <iostream>
#include <vector>
#define SZ(X) (int)(X).size()
using namespace std;
const int MOD = (int)1e9 + 7;
template <typename T>
void add(T &x, long long v) {
x = (x + v) % MOD;
if (x < 0) x += MOD;
}
void solve() {
int N, D;
cin >> N >> D;
int A, B;
cin >> A >> B;
vector<int> m(N);
for(int &x: m) cin >> x;
sort(m.begin(), m.end(), greater<>());
long long low = m[A - 1], hi = m[0] + D;
while (low <= hi) {
long long mid = (low + hi) / 2;
long long need = 0;
for (int i = 0; i < A; i++) {
need += max(0LL, min(1LL * D, mid - m[i]));
}
if (need < 1LL * D * (A - B)) low = mid + 1;
else hi = mid - 1;
}
int h = low - 1;
long long use = 0;
long long ans = 0;
for (int i = 0; i < A; i++) {
if (m[i] < h) {
int inc = min(h - m[i], D);
use += inc;
m[i] += inc;
}
}
for (int i = 0; i < N; i++) {
if (m[i] == h && use < 1LL * (A - B) * D) {
use++;
m[i]++;
}
add(ans, 1LL * m[i] * m[i]);
}
cout << ans << '\n';
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
solve();
}
```
Sign in with Wallet
Connect another wallet