競賽連結請先登入 Codeforces 帳號再點擊。 附中校內賽 時間：2022-10-08（六） 14:00-17:00 OI 制，6 題 不可使用電子、紙本參考資料（cppreference 除外） 無計分板 競賽連結：Codeforces 題本

粉絲專頁：師大附中/延平中學 競技程式讀書會 活動簡介 最近幾年，資訊相關科系成為了熱門科系，也越來越多人參加 APCS 和各種資訊競賽。在高中，最主流的資訊競賽是演算法競賽，或者叫競技程式。 資訊作為一個非主科的科目，相對於數學、地科等等科目，資源少了很多，也比較難以入門。因此，附中和延平的一些有經驗的競賽選手自發舉辦了這個讀書會，旨在提供長期、完整的競賽課程，讓每個人都有機會接受良好的競賽指導，並且促進選手之間的交流，提升兩校的競賽風氣。 活動內容 讀書會的活動以上課為主，預計從 110 學年度上學期開學後開始上課，時間暫定為每週四 18:30 至 21:30，段考前一週停課。上學期會教基本的競賽知識，下學期則是較進階的技巧，且上下學期的期中、期末會各有一次模擬競賽。

時間：2021-10-03 14:00-17:00 三個小時，OI 制，賽中沒計分板 競賽連結：110 學年度 師大附中資訊學科能力競賽 上機 Mirror （請先登入 Codeforces 再點連結） 題解：https://hackmd.io/@joylintp/r1ad59CQK

因為不小心出太難了，場內沒幾個人寫得出來，所以丟出來給大家打 (?)。 共兩場，一場三個小時，OI 制，語言限 C/C++。 時間 模擬競賽 I：2021/09/20（一） 14:00-17:00 模擬競賽 II：2021/09/21（二） 14:00-17:00 比賽連結 在 Codeforces 上比，請先登入 Codeforces 再點擊以下連結。

題目 pC 這題唯一的難點是要找區間裡最小的數，其他都很簡單。 可以暴力地用能夠 RMQ 的資料結構來做，時間是 $O(n \log n)$，不過注意到這題的詢問區間肯定被上一個詢問包含，利用這個性質就可以不寫資料結構。 $O(n \log n)$ 版 把 $1$ 到 $n$ 按 $p_i$ sort，在算 $f(l,r)$ 的時候，看剛剛 sort 的那堆裡的第一個，假設它是 $p$，如果 $p$ 不在 $[l,r]$ 裡就可以把它丟了，以後也不會再用到，因為之後的詢問範圍也會在 $[l,r]$ 裡面，如果 $p$ 在 $[l,r]$ 裡，那 $p$ 就是你要的最小值位置。至於區間和用前綴和算。

以下數字範圍只列所有子題中最大的 題目敘述有修改過 第一題 題目大意 給一個有 $n$ 項的數列 $A$，由第四項起由左而右開始變更數字，變更的方式是，若 $|A_i-A_{i-1}|>5$，就把 $A_i$ 變成 $A_{i-3}$、$A_{i-2}$、$A_{i-1}$ 的中位數，至於在 $A_i$ 之前的項的值都是考慮變更後的數字，而非原始值。 給 $n$ 和 $A$，求變更後的數列。 $1 \leq n \leq 32$

說明與目錄 基本知識 複雜度分析 - 小技巧 前置處理器

# APCS 20190615 P2 機器人走棋盤 ###### tags: `APCS` ## 題目大意 有一個 $m \times n$ 的方格棋盤， （有 $m$ 個橫行（row）、$n$ 個直行（column）） 每一格上面都有一個數字， 機器人會選數字最小的格子作為起點， 接下來每一步會往上下左右數字最小的格子走， 並且它不會走重複的路，也不會走出邊界， 它會一直走到不能走為止，求它經過的所有數字的總和。 輸入第一行有兩個正整數 $m$ 和 $n$， 接下來有 $m$ 行，每行有 $n$ 個數字，表示棋盤各個格子的數字。 輸出機器人經過的所有數字的總和。 $1 \leq m, n \leq 100$ 棋盤的每個數字不超過 $100,000$ ## 解法 一開始要找數字最小的格子， 就在讀取輸入時一邊記錄最小的格子就好。 接下來有一個小技巧，機器人有四個方向可以選， 所以可以開一個二維陣列，裡面儲存往每個方向走，座標會加減多少， 如以下 code 第 5 行。 因為不能走重複的路，所以開一個二維陣列來記錄走過的格子， （記得初始化，下面用 vector 的原因是這

# APCS 20190615 P3 卡通團隊 ###### tags: `APCS` ## 題目大意 總共有 $m$ 個卡通人物，每個卡通人物以一個字母表示， 有 $n$ 個團隊，每一個團隊以一個字串表示， 當字串中含有某個英文字母時，表示這個團隊含有這個成員， （字串中可能有重複的字母，重複幾次或沒有重複都沒有差別） 若兩個團隊沒有相同的成員，且兩個團隊共有全部的 $m$ 個卡通人物， 那這兩個團隊稱為互補團隊。 給 $n$ 個團隊，求有幾隊互補團隊。 輸入第一行有兩個整數 $m$、$n$， 接下來有 $n$ 行，每行有一個字串表示一個團隊。 輸出互補團隊的對數。 $2 \leq m \leq 26$ $1 \leq n \leq 50000$ ## 說明 因為英文字母只有 26 個， 所以可以用一個數字來表示每個團隊有哪些成員： 當第一個位元（由右開始數）為 1 時，表示這個隊伍有 A 這個人， 當第二個位元為 1，表示有 B 這個人，依此類推， 舉例來說：10111₍₂₎ 的第一、二、三、五個位元是 1， 表示這個團隊有 ABCE 這四個人。