Skip to content

2026 S1

AtCoder Beginner Contest #447

E. Divide Graph

這題是練習題，基本上就是找將圖化為兩個連通塊的最小成本。

原本想先學一下 Tajan 演算法利用縮點將圖轉成一個樹，後來發現如果要將連通塊切開要使用其他演算法後就回來重新思考這題。

後來想到當每條邊連起來，連通塊會漸漸地變少，直到某一條邊加入後會只剩兩個連通塊。由這個思路出發，把邊按照 cost 由大至小排序，按順序遍歷每條邊並且使用 DSU 將兩邊的節點連通，直到剩下兩個連通塊。

  • 這題要注意的地方是，由大至小遍歷每條邊有可能在獲得兩個連通塊後，比較小的邊仍然有機會在其中一個連通塊沒有被遍歷，所以計算成本需要走訪完所有邊。
void solve() {
    int N, M;
    cin >> N >> M;
    ll tot = 0;
    vector<Edge> edges(M + 1);
    for(int i = 1; i <= M; ++i) {
        auto &e = edges[i];
        cin >> e.u >> e.v;
        e.u--;
        e.v--;
        e.w = i;
    }
    UnionFind UF(N);
    ranges::reverse(edges);
    ll ans = 0;
    for(auto &e: edges) {
        auto &[u, v, w] = e;
        if(!UF.is_same(u, v)) {
            if(UF.cc > 2) {
                UF.merge(u, v);
            } else {
                ans = (ans + qpow(2, w)) % MOD;
            }
        }
    }
    cout<<ans<<endl;
}

AtCoder Beginner Contest #448

D - Integer-duplicated Path

比賽的時候寫錯題沒寫到這題先寫 E，結果 E 卡到結束。這題就是簡單的 DFS

E - Simple Division

這題一開始聯想到快速冪，修改快速冪的寫法得到計算連續 k 個 digit 的方法

ll MOD = 10007;
ll qappend(ll x, int n, ll mod) {
    ll res = 0;
    ll pow10 = 10;
    for (; n > 0; n /= 2) {
        if (n % 2) {
            res = (res * pow10 + x) % mod;
        }
        x = (x * pow10 + x) % mod;
        pow10 = pow10 * pow10 % mod;
    }
    return res;
}
但是最後在 \(\frac{N}{M} \mod{P}\) 的時候卡住。

由 ref 得到

\[N = (MP)Q + r\]

用 qappend 計算出 N ，計算過程的模數為 \(M \times P\)，最後兩邊同除 M 就是結果:

\[\frac{N}{M} = PQ + \frac{r}{M}\]
for(int i = 0; i < K; ++i) {
    cin >> c >> l;
    N *= qpow(10, l, MOD * M);
    N += qcal(c, l, MOD * M);
    N %= (MOD * M);
}
cout<< (N / M) << endl;

F - Authentic Traveling Salesman Problem

  • 莫隊
struct Point {
    int x, y;
    int id;
};

void solve() {
    int n;
    cin >> n;
    vector<Point> points(n);
    for(int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
        points[i].id = i + 1;
    }
    ranges::sort(points, {}, [](const auto &p) { return p.x; });
    int b = int(sqrt(n));
    while(1LL * b * b < n) b++;
    int m = (n - 1 + b) / b;
    vector<int> order;
    for(int i = 0; i < m; ++i) {
        int l = b * i;
        int r = min(n, b * (i + 1)) - 1;
        sort(points.begin() + l, points.begin() + r + 1, [](const auto &a, const auto &b) { return a.y < b.y; });
        if(i & 1) reverse(points.begin() + l, points.begin() + r + 1);
        for(int j = l; j <= r; ++j) order.push_back(points[j].id);
    }
    int idx = 0;
    while(order[idx] != 1) idx++;
    for(int j = 0; j < n; ++j) {
        cout<<order[(idx++)% n]<<" ";
    }
    cout<<endl;
}

AtCoder Beginner Contest #449

D - Make Target 2

這題一開始想用掃描線由 \([L, R]\) 計算每個位置可以有多少的合法點。但是一直卡在一些 edge case。 賽後發現錯誤是在 \([D, U]\) 都小於 0 的時候沒有把取絕對值後的 D 跟 U 做交換導致計算邏輯有問題。

基本的計算方式為 \(cal(h, x)\) 為在 \([0, h]\) 區間且當前為 \(x\) 有多少合法點。對於 \([D, U]\) 在 \(x\) 有合法點:

\[cnt(U, x) - cnt(D - 1, x)\]
void solve() {
    ll l, r, d, u;
    cin >> l >> r >> d >> u;
    ll ans = 0;
    auto cal = [&](ll h, ll x) -> ll {
        if(h == 0) return (x % 2 == 0);
        if(x >= h) return (x % 2 == 0) * (h + 1);
        ll res = 0;
        res += (x % 2 == 0) * (x + 1);
        res += (h - (x + 1) + (h % 2 == 0) + ((x + 1) % 2 == 0)) / 2;
        return res;
    };
    for(ll x = l; x <= r; ++x) {
        ll X = abs(x);
        ll lo = abs(d);
        ll hi = abs(u);
        /*********************/
        if(lo > hi) swap(lo, hi);
        /*********************/
        if(d * u < 0) {
            ans += cal(lo, X);
            ans += cal(hi, X);
            ans -= cal(0, X);
        } else if(d * u > 0) {
            ans += cal(hi, X) - cal(lo - 1, X);
        } else {
            if(lo) ans += cal(lo, X);
            if(hi) ans += cal(hi, X);
            if((lo == 0 && hi == 0)) ans += cal(0, X);
        }
    }
    cout<<ans<<endl;
}
  • 官解

分別討論 \(|x| > |y|\) 和 \(|x| \le |y|\) 的情況:

photo

由圖可以發現我們要找的點分別是這兩個區域內的頂點，因此分別使用兩條掃描線，掃過兩個區域就可以快速計算。

  • \(|x| > |y|\)

圖中藍色區域，遍歷 \(L \le x \le R\) 時，知道 \(D \le y \le U\)，因為 \(|x| > |y|\) ，所以，\(-|x| < y < |x|\)，結合兩個不等式可以得到:

\[max(D, -|x| + 1) \le y \le min(U, |x| - 1)\]
// |x| > |y|
for (int x = l; x <= r; x++) {
    if (x % 2 == 0) {
        int D = max(d, -abs(x) + 1);
        int U = min(u, abs(x) - 1);
        int C = U - D + 1;
        ans += max(C, 0);
    }
}
  • \(|x| \le |y|\)

與上面同理，只不過差一個等號，因此不等式只會有一些改變:

\[max(L, -|x|) \le x \le min(R, |a|)\]
// |x| <= |y|
for (int y = d; y <= u; y++) {
    if (y % 2 == 0) {
        int L = max(l, -abs(y));
        int R = min(r, abs(y));
        int C = R - L + 1;
        ans += max(C, 0);
    }
}

AtCoder Beginner Contest #450

C - Puddles

這題一開始寫了一個 dfs 找連通塊，結果因為這樣被 rej，最後改成 bfs 就過了，花了很長時間在除錯，以後有 dfs 和 bfs 兩種寫法盡量寫 bfs。

  • DSU 的寫法

  • 分別用 row 跟 col 方向做 union

  • 用 set 去重，然後把邊界點的 parent 挑出來跟前面的計算
void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> board(n);
    readv(n, board[i]);

    UnionFind uf(n * m);
    auto idx = [&](int i, int j) -> int {
        return i * m + j;
    };
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m - 1; ++j) {
            if(board[i][j] == '.' && board[i][j + 1] == '.') 
                uf.merge(idx(i, j), idx(i, j + 1));
        }
    }
    for(int i = 0; i < n - 1; ++i) {
        for(int j = 0; j < m; ++j) {
            if(board[i][j] == '.' && board[i + 1][j] == '.') 
                uf.merge(idx(i, j), idx(i + 1, j));
        }
    }
    set<int> s1, s2;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(board[i][j] == '.') {
                s1.insert(uf.find(idx(i, j)));
                if(i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                    s2.insert(uf.find(idx(i, j)));
                }
            }
        }
    }
    cout<<s1.size() - s2.size() << endl;
}

D - Minimize Range

觀察到對於元素 \(x\) 若是加上 n 倍的 K，最後都可以構造出模 K 後介於 \([1, K - 1]\) 的值。因此我們的目標是在 \(0, 1, 2, 3, .. , K - 1\) 中找到可以包含所有元素的最小範圍。

把產生的元素排序去重後把陣列乘 2 用定滑窗找最小範圍。

E - Fibonacci String

這題很快想到分治的做法，但是在比賽中沒有實作出來。

這題是詢問區間 \([l, r]\) 中有多少字母 \(x\)，一個常用的作法是使用前綴和的思想計算 \(cal(r) - cal(l - 1)\)。

這題最後實作的時候卡在一個邊界條件，對於每個初始字串 X or Y 有可能詢問的區間會比初始字串還要小，所以計算的時候要特別判斷初始區間的部分。

AtCoder Beginner Contest #451

C - Understory

這題有兩種操作:

(1) 加一個元素進集合當中

(2) 將 \(\le h\) 的元素移除

一開始原本想用 Fenwick Tree + 前綴和之類的方式，但是會發現如果做 (2),(1),(2) 這種操作可能會有問題。

ex:

... 1 3 2 7 1 3 2 5

這種例子在第二次 (2) 的時候沒辦法正確計算當前 \(\le 5\) 的元素有多少個。

接著觀察到每個元素進出集合只會有一次，因此考慮直接使用模擬的方式。

D - Concat Power of 2

這題的關鍵在題目給的提示 $ 819264512 \approx 0.8×10^9$，可以知道好數 $ \le 10^9$ 的數量不多，可能只有 \(10^6\) 左右，因此使用暴力產生所有好數。

這題的關鍵是注意到 k 位數的二進制數最多只會有 4 個。

ex:
1, 2, 4, 8
16, 32, 64
128, 256, 512
1024, 2048, 4096, 8192
16384, 32768, 65536
...

令 \(X_k\) 為所有恰好有 \(k\) 位數的好整數集合，並令 \(P_k\) 為所有恰好有 \(k\) 位數的 2 的冪次集合。為了方便起見，令 \(X_0 = \{0\}\)。那麼對於所有 \(k \ge 1\)：

\[X_k = \bigcup_{i=1}^{k} \{x \cdot 10^i + p \mid x \in X_{k-i}, p \in P_i \}\]

設 \(S_k = |X_1| + |X_2| + ... + |X_k|\)

由上面可以知道 \(P_i \le \lceil \log_2{10}\rceil = 4\)，可以知道:

\[ \begin{array}{ll} S_k - S_{k-1} &= |X_k| \\ &= |\bigcup_{i=1}^{k} \{x \cdot 10^i + p \mid x \in X_{k-i}, p \in P_i \}| \\ &\le \sum_{i=1}^{k} |\{x \cdot 10^i + p \mid x \in X_{k-i}, p \in P_i \}| \\ &= \sum_{i=1}^{k} |X_{k - i}| \cdot |P_i| \\ &\le 4(|X_{k - 1}| + .. + |X_1| + |X_0|) = 4(S_{k - 1} + 1) \end{array} \]

解不等式得：

\[ \begin{array}{ll} S_k - S_{k-1} &\le 4(S_{k - 1} + 1) \\ S_k &\le 5S_{k - 1} + 4 \\ S_k + 1 &\le 5(S_{k - 1} + 1) \le 5^2(S_{k-2} + 1) \le ..\le 5^k(S_0 + 1) = 5^k \end{array} \]

可以知道 k = 9 時我們會有不超過 \(S_9 = 5^9 - 1 = 1953124\) 個好整數。