# 交大 GPE 程式檢定 2025.09.17 題目+題解

## 前言

考前原本想去 [GPE網站](http://gpe3.acm-icpc.tw/?ref=blog.setsal.dev) 刷些考古題，結果發現網站掛了，也不知道什麼時候會修好，於是就有了這篇文的誕生，希望能幫助到一些人~

## 題目們

### Problem A

已知 $f(n+1) = a \cdot f(n) + b$，且 $f(1) = 1$。
給定整數 $a, b, m$，共有 $m$ 筆詢問，每筆詢問給定 $x$，求 $f(x) \bmod (10^9+7)$。
<span style="color:red">$額外條件:(a-1) \mid b$</span> (也就是 $b$ 可以被 $(a-1)$ 整除)

**數值範圍：**
$1 \leq a \leq 10^9$
$-10^9 \leq b \leq 10^9$
$1 \leq m \leq 2 \times 10^5$
$1 \leq x \leq 10^{18}$

<details> <summary>解法</summary>

由於 $x$ 最大到 $10^{18}$，因此不能直接計算函式的每一項。那該怎麼辦呢？

在解線性遞迴的時候有一個常用的技巧，對於一個遞迴式：

$f(n) = a \cdot f(n-1) + b$

我們可以嘗試找到一個常數 $c$ 來「平移」遞迴：

$f(n) + c = a \cdot (f(n-1) + c)$

這題的 $c = \frac{b}{a-1}$ (可以自己推推看)，這也就是題目會給額外條件的原因。

這時，令 $g(n) = f(n) + c$，新的式子就變成了：

$g(n) = a \cdot g(n-1)$

也就是說：

$g(n) = a^{n-1} \cdot g(1)$

用快速冪就能在 $O(logn)$ 的時間內算出第 $g(n)$ 項，再回推得到 $f(n)$。注意 $b$ 有可能是負數，要好好的處理負數取模的部分。

</details>

### Problem B

給一張 $10*10$ 的迷宮圖，"S" 是起點，"G" 是終點，"." 是空地，"#" 是牆壁。請找出一條從 $S$ 走到 $G$ 的路徑，並用 "+" 在地圖上標記路徑後輸出，如果沒有解則輸出 "No solution"。

<details> <summary>解法</summary>

~~dfs裸題~~。

開一個 vector 紀錄走過的路徑，當 dfs 到一個點時就將點 push 進 vector 中，離開時就 pop_back (此時 pop 掉的一定是當前的點)。當走到終點時再把 vector 中的點都改成 "+" 然後輸出就好了。

</details>

### Problem C

已知 $f(n) = n \cdot \left( 0.3 \cdot \sqrt{max(\frac{V_{\text{total}}}{n} - V_0, 0)} \right)$。給定整數 $V_{total}, V_0$，你可以選擇一個整數 $n$，使得 $f(n)$ 最大化，並且**如果有兩個以上的 $n$ 可以造成最大值，則輸出 $0$**。

**數值範圍：**
$1 \leq V_{total} \leq 60000$
$1 \leq V_0 \leq 600$
(感謝 柏霖 補充)

<details> <summary>解法</summary>

可以直接枚舉 $n$ 並計算對應的 $f(n)$，比較麻煩的是當有多個最大值時要輸出 $0$，並且這題似乎會卡浮點數精度，我自己用 double 只過兩個測資，後來改用 eps 判斷才 AC。

</details>

### Problem D

原本的題敘又臭又長還很難理解，但簡單來說就是給定一個長度為 $n$ 的整數陣列 $a$，以及一個整數 $m$
，請將陣列分成**不超過 $m$ 段**，使得分段後的**總和最大的那段盡可能小**。

比如說 $a = [1, 2, 3, 4, 5]$，$m = 3$，最佳解是將數列分成 $[1, 2, 3], [4], [5]$ 這三段，如此總和最大的是第一段，總和是 $1+2+3 = 6$，這會是所有分法中最小的。

**數值範圍：**
$1 \leq n \leq 10^3$
$1 \leq a_i \leq 10^3$ (有點忘了)
$1 \leq m \leq 10^6$

<details> <summary>解法</summary>

考慮對答案二分搜，再用貪心的方法判斷能不能用在 $m$ 段內分完。

複雜度: $O(nlog\sum a_i)$

</details>

### Problem E

某個國家有 $5, 10, 20, 50, 100, 200$ 面值的六種鈔票，給定 $a_1$ ~ $a_6$ 分別代表各種鈔票你擁有的數量，現在你要買一個價值為 $k$ 的東西，請找出一種方法使得你付的鈔票數+找錢的鈔票數最小化。保證鈔票的數量足夠付出 $k$ 元。

**數值範圍：**
$k \leq 500$

<details> <summary>解法</summary>

假設付出 $x$ 元，可以貪心計算最少需要付出多少張鈔票 & 對方最少需要找你多少張鈔票，兩個加在一起就是付出 $x$ 元最小需要交換的鈔票數，只要枚舉 $x$ = $k$ ~ $10000$ (或其他足夠大的數) 算出來最小的就是答案了。

</details>

### Problem F

給定多筆測資。每筆測資包含一個字串 $s$。將字串視作一個環狀結構，請問將字串從哪個位置切斷，能使得切斷後的字串字典序最小？

**數值範圍：**
$1 \leq |s| \leq 10^4$

<details> <summary>解法</summary>

直接暴力做，求出每個斷點形成的字串，再找出字典序最小的就好了。

複雜度: $O(|s|^2)$ 每筆測資

(題目沒有說有多少筆測資，看到放在最後一題還以為是什麼深奧字串演算法，結果暴力做就過了==。)

</details>

## 後記

考完後本來想用隨身碟把程式碼帶走 (有先問過助教)，結果系統直接把隨身碟的訪問權限關了QQ。

然後題目敘述真的有夠長，考到一半以為自己在考英文閱讀測驗 (X。