USACO 2025 Open Contest AA 競程 dreamoon 老師的參考做法

• USACO 2025 Open Contest AA 競程 dreamoon 老師的參考做法
  • Bronze
    • Problem 1. Hoof Paper Scissors Minus One
    • Problem 2. More Cow Photos
    • Problem 3: It's Mooin' Time III
  • Silver
    • Problem 1: Sequence Construction
    • Problem 2: Compatible Pair
    • Problem 3: Ski Slope
  • Gold
    • Problem 1: Moo Decomposition
    • Problem 2: Election Queries
    • Problem 3: OohMoo Milk

Bronze

Problem 1. Hoof Paper Scissors Minus One

題目敘述

在遊戲 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}=\mathtt{\text{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++ 的程式語法來寫就是：

(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)$

參考程式碼

#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

題目敘述

今天牛群特別頑皮！ Farmer John（FJ）只想拍下排成一行的牛，但牠們總在快要拍照時移動。
具體來說，FJ 有

$N$ 隻牛 (

$1\le N\le {10}^5$)，每隻牛都有一個介於

$1$ 到

$N$ 的整數高度。FJ 希望拍出一張牛的排列照片，要求牛的高度從左到右必須滿足以下三個條件：

1. 山形排列：牛的高度必須先不降後不升。也就是說，存在一個位置
   $i$ 使得
   $h_1\le h_2\le \cdots \le h_i\ge h_{i+1}\ge \cdots \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\mathrm{\_}h$，那麼對於所有

$i=1\sim ma{x}_h-1$，只要身高

$i$ 的牛出現兩隻以上，我們就一定可以選其中兩隻出現在照片中，所以答案就是：

$$\sum _{i=1}^{max\mathrm{\_}h-1}2\times [cnt[i]\ge 2]$$

其中

$cnt[i]$ 代表身高為

$i$ 的牛有幾隻，

$[]$ 為 艾佛森括號

參考程式碼

#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

題目敘述

Elsie 正試圖向 Bessie 描述她最喜愛的 USACO 競賽，但 Bessie 卻無法理解 Elsie 為何如此喜歡這個比賽。Elsie 說：「而且到了 mooin' time！誰想要來個 mooin'? 拜託，我只想參加 USACO。」

Bessie 仍然不懂，所以她將 Elsie 的描述記錄成一個長度為

$N$ (

$3\le N\le {10}^5$) 的字串，字串由小寫英文字母組成，記作

$s_1{s}_2\dots s_N$。Elsie 定義一個由三個字元組成的字串

$t$ 為 moo，當且僅當

$t_2=t_3$ 且

$t_2\ne t_1$。

一個三元組

$(i,j,k)$ 若滿足

$i<j<k$ 且字串

$s_i{s}_j{s}_k$ 構成一個 moo，則稱該三元組有效。對於一個有效三元組，FJ 會進行以下操作以計算其值：

• FJ 將字串
  $s$ 在索引
  $j$ 處旋轉
  $90$ 度。
• 該三元組的值為三角形
  $\mathrm{\Delta }ijk$ 面積的兩倍。

換句話說，三元組的值為

$(j-i)(k-j)$。

Bessie 向你提出

$Q$ (

$1\le Q\le 3\cdot {10}^4$) 個查詢。在每個查詢中，她給出兩個整數

$l$ 與

$r$ (

$1\le l\le r\le N$, 且

$r-l+1\ge 3$)，要求你求出所有滿足

$l\le i$ 且

$k\le r$ 的有效三元組

$(i,j,k)$ 中，其值的最大值。如果不存在任何有效三元組，請輸出

$-1$。

注意： 此題中涉及到的整數數值可能非常大，因此在程式中可能需要使用 64 位整數型態（例如 C/C++ 中的 "long long"）。

輸入格式

• 第一行包含兩個整數
  $N$ 與
  $Q$。
• 接下來一行包含字串
  $s_1{s}_2\dots s_N$。
• 接下來
  $Q$ 行，每行包含兩個整數
  $l$ 與
  $r$，表示一次查詢。

輸出格式

對每個查詢，輸出一行答案，即該查詢中最大有效三元組的值；若不存在有效三元組，輸出

$-1$。

參考做法

此題的參考做法用到了 AA 競程 Level 1「簡易貪心」、「數列相關函式」單元以及 「Level 1 公開課」中的知識點。

首先對於每個詢問我們要枚舉三元組的第二第三個元素是哪個字元，只有

$26$ 種可能，每種可能各自算出最佳解後，再取最大的那個就是答案了。

接下來我們假設第二第三個元素對應的字母是

$c$。

首先我們可以用貪心的概念來縮小我們要考慮的三元組的數量，最後可發現對於每個

$c$，其實我們至多只要考慮

$2$ 個三元組，解説如下：

• 在知道在確定第二第三個字母是
  $c$ 的情況，第一個字母一定是選區間
  $[l,r]$ 中最左邊的不是
  $c$ 的字母最好(假設此位置為
  $first\mathrm{\_}pos$)，最後一個字母則是選區間中最右邊的
  $c$(假設次位置為
  $last\mathrm{\_}pos$)。而第二個字母一定是選越靠近
  $mid=(first\mathrm{\_}pos+last\mathrm{\_}pos)/2$ 的位置越好，最靠近
  $mid$ 的候補為只有兩個：
  $\ge mid$ 的最左邊位置以及
  $<mid$ 的最右邊位置。

而

$first\mathrm{\_}pos$ 的位置可讀入字串後，就先預處理

$nextDiff$ 陣列，

$nextDiff[pos]$ 代表位置

$pos$ 右邊第一個和

$s[pos]$ 不一樣的字母位置，

$nextDiff$ 陣列求法請參考範例程式碼。

如此一來，對於如果

$s[l]$ 不是

$c$，那麼

$first\mathrm{\_}pos$ 就是

$l$，否則

$first\mathrm{\_}pos$ 就是

$nextDiff[l]$。

而

$last\mathrm{\_}pos$ 的求法可是先把所有字元

$c$ 的位置放入一個 vector 裡，然後使用

$upper\mathrm{\_}bound$ 來求。

最後，靠近

$mid$ 的位置也可使用

$lower\mathrm{\_}bound$ 函式來求出，於是此題的時間複雜度分析如下：

• 預處理
  $nextDiff$ 陣列的時間為
  $O(N)$
• 回答每個詢問的時間為
  $O(\mathrm{字}\mathrm{母}\mathrm{集}\mathrm{大}\mathrm{小}\times \log N)$
• 總時間複雜度為
  $O(N+\mathrm{字}\mathrm{母}\mathrm{集}\mathrm{大}\mathrm{小}\times \log N)$

參考程式碼

#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

題目敘述

給你兩個正整數

$M,K$ (

$1\le M\le {10}^9,1\le K\le 31$)，請構造一個非負整數數列

$a_1,a_2,\dots ,a_N$ 滿足以下條件：

1. $1\le N\le 100$
2. $\sum _{i=1}^N{a}_i=M$
3. $popcount(a_1)xorpopcount(a_2)xor\dots xorpopcount(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)+\dots +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$ 即可。

參考程式碼

// 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

題目敘述

有非常多隻牛，每個牛都有一個數字代表他的 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 的概念實作。

參考程式碼

#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

題目敘述

Bessie 與她的朋友們準備去滑雪旅行。這座山上有

$N$ 個「中繼點」（waypoints），分別標記為

$1,2,\dots ,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^{2}M)$ 的做法如下：

每個朋友的答案各自計算，再枚舉所有中繼點 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(NlogN)$ (此時間複雜度的計算是把

$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$ 值就是該詢問的答案。

參考程式碼

#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

簡要題意

輸入給你三個正整數

$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' 還沒決定要放在哪個子序列，所以我們就有

$(\genfrac{}{}{0ex}{}{cnt}{K})$ 種選擇方式，可直接把此值乘上答案後，在把

$cnt$ 的值減少

$K$ 即可。時間複雜度為

$O(N)$。

參考程式碼

#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

簡要題意

給你一個長度為

$N$ 的數列，

$a_1,a_2,\dots ,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 \underset{i=1\sim N}{max}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\mathrm{\_}SIZE$ 個一組，並用集合

$exist\mathrm{\_}number[j]$ 儲存第

$j$ 組中非公的

$S_i$ 的索引值。

每個詢問都變動到的

$S_i$ 至多只會出現在

$4$ 組裡，再用

$O(GROUP\mathrm{\_}SIZE)$ 的時間暴力更新這幾組的

$exist\mathrm{\_}number[i]$，更新完後，在用

$O(N/GROUP\mathrm{\_}SIZE+\sqrt{N})$ 的時間把所有集合

$exist\mathrm{\_}number[i]$ 裡的索引值按照小到大搜集起來即可。

細節請直接參考程式碼。

參考程式碼

#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

簡要題意

有一個長度為

$N$ 的數列

$m_1,m_2,\dots ,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$)。
2. 遊戲共會進行
   $D$ 輪。
3. 每一輪開始時，首先 Bessie 會把數列
   $m$ 的其中
   $A$ 個數增加
   $1$，接著 Elsie 會把其中
   $B$ 個大於
   $0$ 的數減
   $1$。
4. 遊戲最終分數的計算方式為
   $\sum _{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 的題解，其實和這題 Codeforces 題是樣的東西)，那我們就去二分搜這個

$x$ 值即可，也就是說，要找到最大的

$x$，使得

$\sum _{i=1}^{A}max(0,min(x-m[i],D))\le D\cdot (A-B)$，二分搜求出

$x$ 值之後，就不難得到數列

$m$ 的最終長相，然後就可以算出最終得分。

參考程式碼

#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();
}