# AA 競程 2024 TOI 模擬賽測試場解析

## A. 加法問題

兩個 long long 相加範圍會超過 long long，直接相加輸出會 overflow。所以有些人的直覺是此題可能需要實作大數加法才能通過。

不過啊，GNU 編譯器有提供一個對競程來說非常作弊的資料型態 **__in128** 可以用，但是沒辦法直接用 cin、cout 輸入輸出，所以必須自己實作 __128 的輸出。

### 參考程式碼：

#include<iostream>
#include<string>
using namespace std;
int main() {
    long long x, y;
    cin >> x >> y;
    __int128 ans = (__int128)x + y;
    if(ans == 0) {
        cout << "0\n";
    } else {
        if(ans < 0) {
            cout << "-";
            ans = -ans;
        }
        string s;
        while(ans) {
            s = to_string((int)(ans % 10)) + s;
            ans /= 10;
        }
        cout << s << '\n';
    }
}

## B. 攝氏度轉華氏度

這題乍看之下很簡單，會讓人以為只要輸出 `C*9/5+32` 就行了但實際上這是錯的，這是因為 C++ 的除法並不是向下取整，而是向零取整！也就是說，當運算結果是正的時候，是向下取整，但是在運算結果是負的時候，是向上取整。但這題無論是在正的時候或是負的時候，運算都是要使用向下取整。

這裡提供兩種可能的解決方法有兩種：

1. 用枚舉答案的方式避開除法。

由於輸入的數字範圍不大，所以只要從答案可能的最小值開始向上枚舉，找到最大的滿足 $x \le C \times \frac{9}{5} + 32$ 的 $x$ 值就是答案了。

這樣做的好處就是當我們要判斷一個 $x$ 是否滿足以上的不等式，可以左式右式同乘以 $5$，變為 $5 \times x \le 9 \times C + 160$，除法運算就消失了，問題的解決源頭就消失了！

此做法可使用二分搜優化時間複雜度。

2. 讓除法的結果恆為正

由於癥結點在 C 是負數的時候整數除法非我們預期結果，那就想辦法讓除法運算的結果是非負就好啦，所以，我們先把 C 加上 100，再去乘以 $\frac{9}{5}$，最後再減去 $180$ 即可，也就是說，使用 `(C+100)*9/5+32-180` 即可在 C++ 算出正確答案。

### 參考程式碼

* 方法 1

#include<iostream>
using namespace std;
void solve() {
    int C;
    cin >> C;
    for(int ans = -1000;; ans++) {
        if(ans * 5 > C * 9 + 160) {
            cout << ans - 1 << '\n';
            return;
        }
    }
}
int main() {
    int T;
    cin >> T;
    while(T--) {
        solve();
    }
}

* 方法 2

#include<iostream>
using namespace std;
void solve() {
    int C;
    cin >> C;
    cout << (C + 100) * 9 / 5 + 32 - 180 << '\n';
}
int main() {
    int T;
    cin >> T;
    while(T--) {
        solve();
    }
}

## C. 比大小

此題應該是有各式各樣的寫法，這裡提供一個老師覺得最好寫，絕對不會錯的方法：

用 __int128 儲存數字，然後通分比較分子大小 : )

但相信很多人都是這樣寫但卻錯了，這是因為分母可能有負的，所以通分的結果可能和大家想的不一樣。

這裡提供一個可能解決方法：若 $b \times d$ 是負數，就先把 $a$ 和 $b$ 乘以 $-1$，在比較 $a \times d$ 與 $b \times c$ 的大小即可。

### 參考程式碼

#include<iostream>
using namespace std;
void solve() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    if(b * d < 0) {
        a = -a;
        b = -b;
    }
    if((__int128) a * d < (__int128) b * c) {
        cout << "<\n";
    } else if((__int128) a * d > (__int128) b * c) {
        cout << ">\n";
    } else {
        cout << "=\n";
    }
}
int main() {
    int T;
    cin >> T;
    while(T--) {
        solve();
    }
}

## D. 平分巧克力 2

此題是很經典的二分搜題，和 Codeforces EDU 裡的習題：[B. Ropes](https://codeforces.com/edu/course/2/lesson/6/2/practice/contest/283932/problem/B) 幾乎一模一樣，不會的人請好好去學習一下二分搜...網路上有很多教學影片。這題和 Codeforce 那題只差在此題輸入的數字的範圍比較大，要求的精度也比較高，如果使用 ``while(low + 1e-9 < hi)`` 這樣的二分搜寫法，且使用 low 和 hi 使用精度比 double 還低的資料型態的話，在此題會超時。所以建議的寫法有以下 2 種：

1. 不只要判斷 low 和 hi 的絕對值是否小於 1e-9，還得再判斷 low 和 hi 的相對誤差是否小於 1e-9

2. 直接固定二分搜縮小範圍的次數，例如縮小 100 次就相當足夠了。

用 long double 雖然可以通過這題，但無法保證哪天是否會不小心遇到連 long double 也處理不了經度的題目。

### 參考程式碼

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long double LD;
const int SIZE = 500000;
int a[SIZE];
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    LD low = 0, hi = *max_element(a, a + n);
    for(int round = 0; round < 100; round++) {
        long long num = 0;
        LD mm = (low + hi) * 0.5;
        for(int i = 0; i < n; i++) {
            num += (long long)floor(a[i] / mm);
        }
        if(num >= m) { low = mm; }
        else { hi = mm; }
    }
    cout << (low + hi) * 0.5 << '\n';
}

## E. 孤獨的吉姆

### 子題 $1$

偶數的情況比較容易猜到，不妨假設 $a_1, a_2, \ldots, a_n$ 已經由小到大排好序，只要輸出

$a_{\frac{n}{2}+1}, a_1,a_{\frac{n}{2}+2}, a_2,a_{\frac{n}{2}+3}, a_3,\ldots,a_n,a_{n/2}$

也就是說，當 $i$ 是偶數時，第 $i$ 個位置輸出 $a_{\frac{i}{2}}$，否則，第 $i$ 個位置輸出 $a_{\frac{i+1+n}{2}}$

之所以會想到要這樣構造，是因為我們會想要讓在重新排列後的相鄰兩個數字，在原來排序好的數列裡距離最近的那兩個盡可能遠，而這樣構造就能使得此重新排列裡相鄰兩個數字在排序好的數列裡編號差至少都達到 $\frac{n}{2}$。

至於證明可使用鴿籠原理：考慮 $a_i$ 至 $a_{i+\frac{n}{2}}$ 這 $\frac{n}{2}+1$ 個數，在重新排列後，一定得有兩個數是相鄰的我們可以把 $n$ 個位置分成 $\frac{n}{2}$ 組如下：

$1,1,2,2,3,3,\ldots,\frac{n}{2},\frac{n}{2}$(數字為組別的編號)

那麼$\frac{n}{2} + 1$ 個數去放在這 $n$ 個位置中，無論怎麼放，至少有兩個數會在一其中一組，而這兩個數的差的絕對值一定小於等於 $a_{i+\frac{n}{2}} - a_i$。

也就是說，我們證明了無論怎麼排列，相鄰的兩個數的差的絕對值的最小值一定小於等於
$$
\min_{i=1}^{\frac{n}{2}}(a_{i+\frac{n}{2}}-a_i)
$$

而上面那個構造方法剛剛好就是上述等號成立的情況。

### 子題 $2$

### 先說結論

已 $n = 7$ 為例，一樣不妨假設 $a_1, a_2, \ldots, a_n$ 已經排序好，最佳解一定在以下 $4$ 種情形之中：

1. $a_1, a_5, a_2, a_6, a_3, a_7, a_4$
2. $a_2, a_6, a_3, a_7, a_4, a_1, a_5$
3. $a_3, a_7, a_4, a_1, a_5, a_2, a_6$
4. $a_4, a_1, a_5, a_2, a_6, a_3, a_7$

有沒有發現什麼呢？

另 $k=\frac{n-1}{2}$

第一個種情形公式化來說的話會是：

$a_1, a_{k}, a_2, a_{k+1}, \ldots, a_i, a_{k+i-1}, \ldots, a_{k-1}, a_n, a_{k}$

而之後沒種情形都是把上一種情形的前 $2$ 個數移到最後一個位置。

用圖像化來思考的話，我們可以把第一個數列圍成一個圈圈，你就會發現所有相鄰兩個數恰好是所有 $(a_i, a_{i+k})$ 和 $(a_i, a_{i+k+1})$ 的組合，而候補答案的 $k+1$ 種情形正好是選某個位置 $i$，把圈圈從 $a_i$ 和 $a_{i+k}$ 之間斷開。

### 怎麼思考到這樣的做法呢？

偶數情況是比較容易想到及證明的，於是我們可能會這樣想：奇數的作法會不會也和偶數的情形類似呢？

在複習一次偶數的情況：對於每個 $1 \le i \le \frac{n}{2}$，不管怎麼排列都一定存在某相鄰兩個數之差的絕對值 $\le a_{\frac{n}{2}+i}-a_i$，所以當 $n$ 是奇數時，乍想之下會覺得答案可能是：

$$
\min_{i=1}^{k+1}(a_{k+i}-a_i)
$$

但稍微構造下就會發現，有辦法構造出更好的答案！

這是因為偶數的情況的證明形式是：

對於所有合法的 $i$，在 $a_i \sim a_{k+i}$ 這樣 $k+1$ 個連續的數構成的集合中，無論怎麼排列都至少會有兩個數在數列裡是相鄰的。

但在奇數的情況，其實允許至多一個 $i$ 滿足該集合在某個排列中可以兩兩不相鄰，當這種情況發生時，該集合的 $k+1$ 個數一定佔據了數列中所有奇數的位置，因此，其他的連續 $k+1$ 個數構成的集合，就一定存在兩個數在此排列中相鄰的。

所以答案一定不會超過 $a_{k+1}-a_1, a_{k+2}-a_2, \ldots, a_n - a_{k+1}$ 之中第二小的數，並且可由先前所提到的方法構造出來。