Try   HackMD
tags: 選修

APCS(大學程式設計先修檢測)程式實作

零、評量、C++語法參考網站、相關網站

1. 評量方式

  • 上課基本練習 40%
  • 作業解題數(ZJ共通過(AC)題數) 20%
    • 本課程是為了考APCS,檢定的難度會比上課更難,不願意自主練習是沒機會到3級(約能完整解出2題)以上。
    • 作業題目選擇
      • 可從題單裏沒教過的題目選擇,或任選其它題目都可。
      • 不會的可以去參考網路上的程式碼、解法。
      • 同學也可以互相討論,而且是鼓勵的。
      • 不論如何,都要在了解解法後,不看別人的程式碼,自己親自寫一遍。
      • 不要為了分數直接貼別人的程式碼,那是無意義的行為,上機考你就會現出原形。
      • 題數登記時間:上機考當週。
      • 成績計算方式:作業不批改,以上機考檢核作業是否抄襲。
      ​​​​​​​​原始作業成績=min(題數*4,120) // 上限120
      ​​​​​​​​if(原始作業成績>=100)        // 認真的同學可以有一點失誤的空間,例如原始作業120分,上機考 80分,作業成績實得 96分。
      ​​​​​​​​    作業成績=原始作業成績*(上機考成績/100)
      ​​​​​​​​else if(上機考成績>=原始作業成績)
      ​​​​​​​​    作業成績=原始作業成績     // 老師承認你的作業是自己做的,例如原始作業 80分,上機考100分,作業成績實得 80分。
      ​​​​​​​​else if(上機考成績<原始作業成績)
      ​​​​​​​​    作業成績=上機考成績       // 老師不承認作業是你自己做的,例如原始作業 80分,上機考 30分,作業成績實得 30分。
      
  • 期中上機考 20%
    • 時間約第1、2次期中考中間。
    • 上機考時網路會切斷,無任何其它參考資料可看。
    • 每單元請至少練習一半題目,熟練基本語法。
    • 因為課程的目的是要考APCS,上機考會比較難,也會算分(資概的上機考只是基本語法檢核,不算分)。
  • 期末作業解題報告 20%
    • 上機考考差的同學請保握最後的機會。
    • 10~12題。
      • 每寫一題10分,上限120分(12題)。
      • 期中考之前的舊範圍(上學期:四、陣列之前。下學期:STL 演算法之前),最多只能放3題。
      • 其餘的必須是新範圍(上學期:五、字串之後。下學期:STL vector之後)新寫的題目,每個單元至多可放3題(不可以都寫同一單元的題目)。
    • 每題的子標題為
      (1) 單元、題號、題目、題目簡述
      (2) 解題動態、評分結果截圖
      (3) 解題思路
      (4) 程式碼
      (5) 反思(遇到的錯誤、修正的地方、更好的方法…)
      (6) 錯誤程式碼
    • 檢核方式
      • 請儘量放一開始有錯,然後修正的題目。如果你每一題都是一次AC,那你應該是骨骼清奇、萬中無一的練武奇才,應該不用怕老師的檢核吧。
      • 有交期末作業解題報告者,會請你在沒有網路的狀態下重寫一題當做檢核(題目由老師挑選),寫不出來作業直接作廢0分,所以作業請務必自思考己完成,如果你只想上網找程式複製貼上賺分數,就不用做這種白工了。
    • 可放到學習歷程檔案。

2. TOI推廣計畫-線上練習賽

  • 成績計算
    • 新手組:分數/300直接加在總成績。
    • 潛力組:分數/100直接加在總成績。
  • 上學期10、11、12月,下學期3、4、5月,最後一週。
  • 星期一08:00 ~ 星期五20:00。90分鐘。
  • 證書

3. 學習歷程檔案(修課記錄、課程學習成果)(Bonus)

5. APCS

6. APCS 實作題檢測從三級到五級(中正大學 吳邦一教授)

7. 軟體

8. 面試線上題庫


壹、TOI 線上練習賽 新手組考式範圍

一、變數與運算子

EX_1_1:a001: 哈囉

EX_1_2:d060: 還要等多久啊?

  • 3元運算子
  • 多元解法 (85-m)%60

EX_1_3:d485: 我愛偶數

  • %
  • 複合指定運算子
  • 將a,b調整成偶數(a如果是奇數+1,b如果是奇數-1),計算2個偶數間的偶數

EX_1_4:b004: 繩子上吃草的牛

  • while(cin >> D >> L)
  • const
  • acos(0)、sqrt(),需含入 cmath
  • 半長軸:L/2,半短軸:sqrt((L/2*L/2)-(D/2*D/2)),橢圓面積:pi*半長軸*半短軸
  • Q:int D,L?
  • C++小數點位數控制
    ​​​​#include <iomanip>
    
    ​​​​cout << fixed << setprecision(3);
    ​​​​// setprecision(n) 會將輸出的數值控制為 n 位數,如果加上 fixed 表示只控制小數點以下的位數。
    
  • C小數點控制printf,需含入 cstdio 標頭檔。
  • 萬能標頭檔案 #include<bits/stdc++.h>

EX_1_5:d039: 11044 - Searching for Nessy

  • 邊界可不計代表除不盡可捨棄
  • 輸入的第一行有一個整數t,代表測試筆數
int t;
cin >> t;
while(t>0)
{
    ....
    t--;
}while(t--)
{
    ....
}

1.d483: hello, world

2.a002: 簡易加法

  • +

3.a861: 1.Secure the Perimeter

  • 2h+2w(*不能省略),(h+w)*2

4.d226: 10071 - Back to High School Physics

  • v-t 圖算面積

5.d053: Big Chocolate

  • 3x4巧克力需要11刀
  • m-1+m*(n-1) (why?)

6.d489: 伏林的三角地

  • 海龍公式計算三角形面積
  • s=(a+b+c)/2
  • area=(s(sa)(sb)(sc))

7.d827: 買鉛筆

  • /、%、(( ))
  • n/12*50+(n-(n/12)*12)*5

8.d277: 矩陣對角線

  • 3元運算子、%
  • 對角線奇數可共用對角線交叉的花盆,偶數不共用

9.b681: 1. 山洞探險

  • 3元運算子
  • 向北公式為2L-1,向南為?
  • long long int

10.d127: 二、牧場面積

  • 接近正方型面積會最大
  • long long int

11.d461: 班際籃球賽

12.d096: 00913 - Joana and the Odd Numbers

  • long long int
  • 有N個奇數為第(N+1)/2列
  • 找出此列最後3個數字與第(N+1)/2列的關係

13.d051: 糟糕,我發燒了!

  • 浮點數(float、double)
  • setprecision 控制輸出數值的「位數」,需含入 iomanip 標頭檔
  • 只控制「小數點後的位數」fixed
  • 型別轉換

14.c776: 106北二1.六邊形屋瓦

  • 扣掉重覆的白色屋瓦。公式?

15.d549: 矩形中的几何

  • PA2 + PC2 = PB2 + PD2 (畢氏定理,why?)
  • sqrt(),需含入 cmath 標頭檔
  • printf小數點,需含入 cstdio 標頭檔
  • PA、PB、PC變數形態用long long int或double

二、條件判斷

EX_2_1:d065: 三人行必有我師

  • &&

EX_2_2:e283: APCS 類似題 - 小崴的特殊編碼

  • 多項選擇
  • C++ I/O加速
    ​​​​#include<bits/stdc++.h>
    ​​​​using namespace std;
    
    ​​​​int main()
    ​​​​{
    ​​​​    ios::sync_with_stdio(false);
    ​​​​    cin.tie(0);
    
    ​​​​    int a;
    ​​​​    while(cin >> a)
    ​​​​    {
    ​​​​        cout << a << '\n'; 
    ​​​​        // endl 為 << '\n' << flush;
    ​​​​        // 自行測試時中途會看不到答案
    ​​​​    }
    ​​​​}
    

EX_2_3:a004: 文文的求婚

1.d064: ㄑㄧˊ 數?

  • 比較運算子
  • ==(等於)
  • !=(不等於)

2.a012: 10055 - Hashmat the Brave Warrior

3.d058: BASIC 的 SGN 函數

  • 巢狀if
  • 比較運算子 > >= < <= == !=

4.d066: 上學去吧!

  • 巢狀if
  • 亦可將時化為分

5.a006 一元二次方程式

6.a053: Sagit's 計分程式

  • 多項選擇

7.d460: 山六九之旅

  • 多項選擇

8.a273: 小朋友下樓梯

  • 小心n或k等於0的情形

9.b186: 97七區資訊學科1(改編)

  • 取餅乾/10,蛋糕/2中小的數即是贈送的盒數
  • 測資會有0 0 0

10.a005: Eva 的回家作業

  • 判斷等差或等比數列,求第5項
  • while(t--)

11.d057: 11494 - Queen

  • 垂直、水平、或對角線1步可到,其它2步可到
  • abs()可求絕對值,需含入 cstdlib 標頭檔
  • if(x1 == 0 && y1 == 0 && x2 == 0 && y2 == 0) break;
  • 或 if(!x1 && !y1 && !x2 && !y2) break; 讓輸入0 0 0 0時結束。

12.d984: 棄保效應

  • &&、||
  • 運算子優先順序
  • unsigned int
  • a>b+c(a最大) 或 c>a>b(棄b保a) 或 b>a>c(棄c保a)
                               c>a && a>b && a+b>c

13.g275: 1. 七言對聯

14.b899: 2. 物品探測

  • 分別計算三點間的距離,最長的為正方形的對角線。
  • 正方形四點 A、B、C、D,假設 A、C 為對角,則 D = A + C - B

15.d095: 00579 - ClockHands

  • 分別計算時針與分針相對於12點的角度再相減
  • fabs()可求浮點數的絕對值,需含入 cmath 標頭檔
char colon; //設一個字元變數,把冒號讀掉
while( cin >> h >> colon >> m && !(h == 0 && m == 0) )	

16.c461: apcs 邏輯運算子(Logic Operators)

  • 位元運算子&(AND)、|(OR)、(^)XOR
  • 將a、b以位元運算子運算後和c比較

17.d502: 第三題:產品包裝

  • 裝3*3*3產品和2*2*2產品剩下的空間,用來裝1*1*1的產品,可讓需要的包裝箱最少。
  • 一個3*3*3產品裝在箱子裏,會剩37個1*1*1的空間。
  • 2*2*2產品裝在箱子裏,會剩64-8*(b%8)個1*1*1的空間。

三、重複結構

EX_3_1:a824: 2.藏寶問題

  • 型別轉換
  • 複合指定運算子
  • 每筆測資變數歸零

EX_3_2:a024: 最大公因數(GCD)

  • 暴力法(i++ v.s. i--)(break)
  • 時間複雜度
  • 輾轉相除法 (a=bq+r,則gcd(a, b) = gcd(b, r))
  • 除錯練習
    (1) 設中斷點
    (2) Debug (F8)
    (3) Debugging windows/Watches
    (4) Next line (F7)
    (5) Stop debugger

EX_3_3:a215: 明明愛數數

  • do_while迴圈

EX_3_4:c418: Bert的三角形 (1)
EX_3_5:c419: Bert的三角形 (2)

  • 巢狀迴圈(內外圈變數不能重複)

EX_3_6:b003: 運算式 + - 符號設定問題

  • 1+2+n=sum,沒有任何負號時是最大值,如果此時sum小於k,根本不可能有答案,所以sum一定要>=k。
  • 如果m前有一個負號時,sum會少2*m,所以如果sum-k為偶數,則可從1~n找出數字減掉。
  • 解題參考1解題參考2

1.d498: 我不說髒話

  • for迴圈

2.d490: 我也愛偶數

  • for
  • i=i+1(i++)
  • 變數初值,區塊變數 v.s. 區域變數

3.d074: 電腦教室

  • for、if

4.c022: 10783 - Odd Sum

  • 累加

5.d356: NOIP2002 1.级数求和

  • 型別轉換
  • 浮點數誤差(float->double)

6.a147: Print it all

  • break
  • continue

7.d010: 盈數、虧數和完全數

  • 將因數累加

8.c299: 1. 連號或不連號

  • 輸入數列時,找出其最大和最小值(可使用if或max、min函式)
  • 最大-最小+1==n,表示這個數列是連續的

9.d186: 11461 - Square Numbers

  • 完全平方數的判定

10.e622: 虛擬寵物大師 (Master)

  • 計算寵物成長後最終CP值,記錄最大值。

11.a038: 數字翻轉

  • while
  • 不斷取個位數加入翻轉數字

12.a536: 11689 - Soda Surpler

  • 每次換的汽水又可再變成空瓶子拿去換
  • 可以換的汽水數量=所有空瓶數/c
  • 手上空瓶=所有空瓶數/c+所有空瓶數%c

13.d189: 11150 - Cola

  • 不論開始有幾瓶,最後的剩餘狀況都只1瓶或2瓶

14.d122: Oh! My Zero!!

  • 0的數量為2和5因數個數的較小值,對n!來說2的因數個數一定會比5多

15.a149: 乘乘樂

  • 運算子優先順序 sum=sum*(n%10)
  • 複合指定運算子

16.c561: Bert 愛搗蛋

  • 將數值反轉的方法,假設 a為原數值,rvs為反轉後的數值(預設值為 0)
    rvs=rvs*10+(a%10);
    a/=10; // 讓個位數消失

17.d660: 11764 - Jumping Mario

  • prev=now

18.c420: Bert的三角形 (3)

  • 巢狀迴圈

19.f063: The Strongest Chain

  • 巢狀迴圈

20.c013: 00488-Triangle Wave

  • 巢狀迴圈
  • 下半部 for(k=A-1;k>0;k--)

四、陣列

EX_4_1:d212: 東東爬階梯

EX_4_2:d478: 共同的數 - 簡易版

EX_4_3:f579: 1. 購物車

  • 商品編號為陣列的索引值

EX_4_4:f606: 2. 流量

  • 二維陣列
  • 同城市的伺服器流量要合併計算費用,所以預處理先將伺服器流量加總到它所在城市編號那一列。
  • 計算花費時,i==j 代表伺服器在那個城市。
  • 整數最大值可用0x3f3f3f3f
  • memset將陣列歸零,memset(a, 0, sizeof(a)); 需含入 cstring 標頭檔

EX_4_5:d596: 1. 猜九宮格裡的地雷

  • 因為只有9個格子,且每個格子只有4個相鄰格子,所以以二維陣列記錄每個格子其相鄰格子的編號最簡單
  • 以一維陣列記錄格子編號是否有地雷(bool)
  • 「與地雷相鄰格子」的4個鄰居都可能是地雷
  • 「與地雷不相鄰格子」的4個鄰居都不是地雷

1.b138: NOIP2005 1.陶陶摘苹果

2.b127: 會議中心(Room)

  • 費式數列

3.c067: Box of Bricks

  • 一維陣列

4.a034: 二進位制轉換

  • 餘數輸出由下而上倒序寫 for(int j=i-1;j>=0;j--)

5.a240: 第一題:1 / 17 小數第 n 位

6.a020: 身份證檢驗

  • 以陣列將英文代號轉為數字

7.b139: NOIP2005 2.校门外的树

8.d097: 10038 - Jolly Jumpers

  • 宣告一個記錄差的陣列d(初值為0),若兩數的差為3,則d[3]=1
  • 輸入結束後,如果d[1~n-1]有0,則不是jolly jumper

9.d563: 等值首尾和

  • 以迴圈讓prefix由前往後加,suffix由後往前加
  • 如果prefix(前段和)==suffix(後段和)則答案加1,同時往前、後各加一個元素
  • 如果prefix<suffix,則prefix往後加一個元素
  • 如果prefix>suffix,則suffix往前加一個元素

10.a040: 阿姆斯壯數

  • pow(x,y)計算xy,需含入 cmath 標頭檔
  • 以迴圈和%求n位數整數的個位、十位…,放入陣列,並計算n
  • 再以迴圈將所有位數的n次方加起來,判斷是否等於此整數

11.d123: 11063 - B2-Sequence

  • 宣告一個記錄兩數和是否存在的陣列s(初值為0)
  • 以兩數和當成index,如果不存在,則s[兩數和]=1

12.d424: 00105 - The Skyline Problem

  • 使用陣列紀錄每個x軸座標上的最高高度
  • 輸出時注意邊界

13.c435: MAX ! MAX ! MAX !

  • 爆力解會TLE
  • 往後掃描時不斷記錄最大範圍答案和最大值(一層迴圈完成)
  • 解題參考

14.a693: 吞食天地

  • 每次都重算會TLE
  • S[-1]陣列除錯

15.a015: 矩陣的翻轉

  • 二維陣列

16.d481: 矩陣乘法

  • 二維陣列

17.a694: 吞食天地二

18.a417: 螺旋矩陣

  • 二維陣列
  • memset將陣列歸零,memset(a, 0, sizeof(a)); 需含入 cstring 標頭檔
  • 逆時針即順時針的轉置矩陣

19.b965: 第 2 題 矩陣轉換

  • 二維陣列
  • 旋轉座標轉換

    A (0,0) -> (0,2)
    B (1,0) -> (0,1)
    C (2,0) -> (0,0)
    D (0,1) -> (1,2)
    E (1,1) -> (1,1)
    F (2,1) -> (1,0)
  • 旋轉後的r,等於轉換前的c。
  • 旋轉後的c,等於r數量(3)-r-1。

20.a291: nAnB problem

  • 使用陣列紀錄是否比較過
  • 使用 scanf 和 printf 才不會TLE

21.e287: 機器人的路徑
22.g276: 2. 魔王迷宮

五、字串(字元陣列)

EX_5_1:a149: 乘乘樂

  • 改寫為以字元陣列方式讀入
  • 字串結束符號 '\0'

EX_5_2:a782: 4. Redundant Acronym Syndrome Syndrome

  • 不能使用cin >> s
  • cin.getline(s,1000)
  • getline(cin,s)
  • toupper()將字元變大寫
  • C 需用strcmp()比較兩字串是否相等,陣列的名字代表陣列開始的位址,s=="END"的寫法,即使s為"END"也不會相等。C++ string 可直接用==比較

EX_5_3:a011: 00494 - Kindergarten Counting Game

  • 不能只算空的數量,字母的前一個是非字母即一個字
  • 不能使用cin >> s
  • getline(cin,s)
  • isalpha()

EX_5_4:a022: 迴文

EX_5_5:a130: 12015 - Google is Feeling Lucky

  • 找最大值
  • struct
  • printf(),需含入 cstdio 標頭檔

1.b428: 凱薩加密

2.a009: 解碼器

3.d124: 3的倍数

4.c290: APCS 2017-0304-1秘密差

  • string類別
  • str.size()
  • abs()可求絕對值,需含入 cstdlib 標頭檔

5.a054: 電話客服中心

  • 注意100000000答案為KLY

6.a065: 提款卡密碼

  • abs()可求絕對值,需含入 cstdlib 標頭檔

7.d235: Q10929:You can say 11

  • 11的倍數判別法:奇數位數字和與偶數位數字和相差為11的倍數

8.a224: 明明愛明明

  • 統計每個字母出現的次數
  • 迴文的條件為:只有一個字母出現的次數是奇數或全部都是偶數
  • 每筆測資統計的陣列要歸零
  • isalpha()判斷字元是否為英文字母
  • toupper()將字元變大寫

9.d430: 第二題: 計算字數 (count)

  • islpha()、isdigit()、isalnum()

10.c440: Bert Love QQ !

11.f291: 試算表大小

  • 將輸入字串的字母轉成整數(26進位),A為1,B為2,…,AA為27,AA為28,…。
  • substr
  • stoi
  • isdigit()

12.d614: 簡易加法運算

  • 讀入測試筆數T後,需以getline(cin,str)將T後的換行字元讀掉,或cin.ignore()
  • 以cin.getline()或getline(cin,str),讀入一行
  • isdigit()判斷字元是否為數字
  • 如果是數字,減48(0的ascii)得到數值,加前一個數字*10
  • 如果不是數字,答案加上目前已經造出來的數字。

13.a865: 5. Greek Numerals

  • 將26個字母對應的值儲存為陣列
  • #、$、3為多的字母

14.d275: 11586 - Train Tracks

  • 只要M和F數量一樣且軌道一個以上即可
  • cin.ignore()

15.c459: 2. 自戀數

  • 可將N以字元陣列讀入
  • strlen(N)計算其長度
  • 數字字元-'0'求其數值
  • pow(a,b)計算ab,需含入 cmath 標頭檔
  • 根據進位制求出數值大小及每位數字的d次方合,比較是否相等

16.d103: NOIP 2008 1.ISBN号码

  • 數字字元-'0'求得其數值
  • 計算識別碼,如果等於最後一個數字,或餘10且最後一個字元為'X',則為正確

17.d086: 態度之重要的證明

  • toupper()將字元變大寫或tolower()將字元變小寫
  • A的ASCII值為65,a的ASCII值為97

18.a275: 字串變變變

  • 使用陣列儲存兩字串各別字母出現的次數(以字母的ascii為陣列索引)
  • 如果各別字母出現次數一樣,表示可經由調整順序後,讓兩字串一樣

19.d267: 11577 - Letter Frequency

  • cin.ignore()把數字後的換行字元讀掉
  • isalpha()判斷字元是否為英文字母
  • tolower()將字元變小寫
  • 以字母的ascii為陣列索引記錄出現次數,迴圈找出頻率最高的次數,迴圈印出頻率最高的字母

20.d671: 11716 - Digital Fortress

  • cin.ignore()把數字後的換行字元讀掉

21.c462: apcs 交錯字串 (Alternating Strings)

  • 找出每一個連續大(小)寫片段的長度並將其記錄在陣列

22.e294: APCS 類似題 - 小崴的新發現

  • 找下一個完全奇數的方法:從左往右找到某位數為偶數,把此位數加1,此位數之後的數都設為1
  • 找前一個完全奇數的方法:從左往右找到某位數為偶數,把此位數減1(偶數可能為0,要處理向前借位的問題),此位數之後的數都設為9
  • atoll()將C字元陣列轉成long long
  • s.c_str()將C++ string轉成C字元陣列

六、函式(遞迴)

EX_6_1:d171: 飛蛾撲火(二)

  • 內建函式:pow、log10、floor
  • logNM = M*logN

EX_6_2:c039: 00100 - The 3n + 1 problem

  • 自訂函式(先練習寫pow(n,m))
  • 內建函式:swap、max、min

EX_6_3:a216: 數數愛明明

  • 遞迴(先印出費式數列)
  • long long int
  • TLE(遞迴求一般項)

EX_6_4:f637: DF-expression

1.d658: 11636 - Hello World!

  • 以log2()求N為2的幾次方
  • 以ceil()無條件進位

2.f044: 2. 史萊姆生態區 (Slime)

  • log2()

3.c294: APCS-2016-1029-1三角形辨別

  • 自定交換函式swap(傳參考呼叫)(除錯Step into)
  • 使用swap讓a,b,c依小->大排序(c為最長邊)

4.a121: 質數又來囉

  • 1不是質數

5.b112: 5.高中運動會

  • 多個數的最大公因數

6.d237: 質數合

  • 以質數函式測試是否需加此數
  • 不可直接輸出142913828922

7.d117: 10924 - Prime Words

  • 以質數函式測試字母值總合

8.a623: Combination

  • 將n!寫成函式,在主程式呼叫3次

9.d255: 11417 - GCD

  • 將gcd寫成函式

10.c813: 11332 - Summing Digits

  • 將f(x)寫成函式,不斷呼叫了式,直到n為個位數

11.c015: 10018 - Reverse and Add

  • 將數字反轉寫成函式
  • 迴文的檢查為數字反轉後和原數字相等即是

12.a263: 日期差幾天

  • 判斷閏年可寫成函式
  • 可算出總天數再相減

13.a227: 三龍杯 -> 河內之塔

14.c002: 10696 - f91

  • 遞迴

15.d693: 最小公倍數

  • n個數的公倍數可以從兩兩連續求公倍數得到
  • long long int
  • 以遞迴求gcd

16.f638: 支點切割

17.f640: 合成函數

  • 遞迴
  • stringstream
  • 或用堆疊反向處理

18.d269: 11579 - Triangle Trouble


貳、TOI 線上練習賽 潛力組考式範圍

一、物件導向簡介

  • 封裝(私有型態)
  • 繼承(保護型態)

二、stringstream

EX_2_1:d392: 读取练习——强大的加法!

  • stringstream字串轉數字

EX_2_2:d574: 節約符咒

  • stringstream數字轉字串
  • string字串相加
  • 每次都開新的stringstream會TLE
  • ss.str("");
  • ss.clear();
  • ss.str()、ss.str().size()

1.a158: 11827 - Maximum GCD

  • 數字數量不定以stringstream拆解放入陣列,巢狀迴圈求兩數的GCD
  • __gcd(a,b)可求a、b兩數的GCD,需含入 algorithm 標頭檔

2.d098: Stringstream運用練習(C++)

  • stringstream字串數字轉換
  • str.length()
  • isdigit()
  • getline()
  • atoi()
  • string.c_str()

3.d018: 字串讀取練習

4.d672: 10922 - 2 the 9s

  • 遞迴
  • string.c_str()

三、C++ STL

(一) 演算法

EX_3_1_1:a225: 明明愛排列

  • 陣列名為指標說明
  • 常用C++ algorithm:sort
  • 自訂比較函式(小到大排列時,如果左邊元素<右邊元素,回傳true)
  • 大到小排列比較函式可用greater<int>()

EX_3_1_2:a362: 1. 搬雕像

  • sort
  • 自訂比較函式
  • struct
  • 排序後的位置-原來的位置編號

EX_3_1_3:a524: 手機之謎

EX_3_1_4:b582: 一個窩

  • nth_element,使第n大的元素置於n的位置。用 sort 亦可,但如果測資更大會TLE。
  • c++ I/O加速
  • 開一個1000000的全域變數陣列,用 vector 會 TLE。

1.a251: 假費波那契數

  • 陣列名為指標說明
  • sort
  • 陣列的編號為0~n-1,若從1開始放,要多加空間。

2.b964: 第 1 題 成績指標

  • 排序(STL sort)

3.f410: 芝麻街的郵件投遞

  • sort
  • 自訂比較函式

4.c230: 松鼠旅行

5.c044: 10008 - What's Cryptanalysis

  • isalpha()
  • toupper()

6.d829: 00146 - ID Codes

  • next_permutation

7.d913: 1. 彈珠配置

  • next_permutation依序產生一組彈珠順序
  • 比對前6次彈珠順序,如果都符合每次猜測的結果即是答案

8.g005: 倒置文章 (Inversion)

  • reverse(s.begin(), s.end())

9.a480: 導彈攔截系統

  • 設城市與導彈攔截系統1,2的距離為d1,d2
  • 先對各城市d1排序,之後再窮舉求p
  • p = c[i].d1        +        max(c[i+k].d2),k>=1
    (i城市與導彈1的距離) (其它城市與導彈2的最大距離)

(二) 循序式容器Sequence Container(vector)

EX_3_2_1:d323: 電腦-窮人的

  • 指標、樣板說明
  • vector
  • iterator
  • v.push_back(x) v.s. cin >> v[i]
  • sort(v.begin(), v.end())
  • STL vector 效率小記
  • C++ 11設定
    • CodeBlocks:Settings / Compiler / Have g++ follow the C++11 ISO C++ language standard
    • Dev-C++:專案 / 專案選項 / 編譯器訊息 / 程式碼產生 / 語言標準(-std) / ISO C++11
    • for(int e:v)
    • for(int& e:v)
    • v.resize(n)

EX_3_2_2:d186: 11461 - Square Numbers

1.f819: 圖書館 (Library)

  • 將逾期的書本編號放入vector,排序後印出。

2.f820: 極限運動 (Sports)

  • 將高度儲存在vector,從著陸點分別向左、右滑至停止點。比較停止點高度,輸出高度小(垂直落差大)的位置。

3.c295: APCS-2016-1029-2最大和

  • 將可以整除S的被選擇數字,以vector儲存後印出。

4.b051: 2. 排列最大值

  • sort
  • 自訂比較函式大到小排序(s1+s2>s2+s1)

5.a915: 二维点排序

for(point& p:v)
    cin >> p.x >> p.y;

6.b844: 一堆按鈕

  • 直觀解陣列會太大,且會TLE( O(N*K) )。
  • 用陣列記錄N個按鍵號碼,陣列中有幾個數字小於等於詢問的數字,即0、1切換的次數
  • 可先排序,以2分搜加速

7.b005: 布林矩陣的等價短陣

  • 分別計算每行、每列的和為奇數的個數,若沒有奇數為等價,若行、列中各有一個奇數則Change bit (該行,該列),其餘情況均為Corrupt

(三) 循序式容器Sequence Container(list)

1.a870: 10. List Maker

2.b938: kevin 愛殺殺

  • 鏈結串列Linked List
  • C++ I/O加速 ios::sync_with_stdio(false); cin.tie(0);
  • 已殺,排最後一個,剩最後一個,都要輸出0u0

(四) 關聯式容器Associative Container(set、multiset)

EX_3_4_1:d129: 00136 - Ugly Numbers

  • 第1500個醜數為8億多,暴力法會TLE
  • 醜數為2x * 3y * 5z,所以對已存在的醜數*2、*3、*5放入集合
  • set會自動排序,並過濾重複數字
  • next(it)

EX_3_4_2:c807: 一維凸包問題

EX_3_4_3:f607: 3. 切割費用

  • 加分題。
  • 依切割順序排序後,以set來儲存已切割的點,對每個切割點找它的前、後點。
  • s.lower_bound()、s.upper_bound()
  • insert() 返回值是pair<iterator,bool>,iterator代表插入的位置,若值已經在set中,則iterator表示原來值的位置;bool表插入是否成功。
  • next(it)、prev(it)

1.a541: 字典

  • set:insert、find、end

2.b523: 先別管這個了,你聽過安麗嗎?

  • set:count、insert、find、end

3.c122: 00443 - Humble Numbers

  • 類似d129
  • typedef long long ll;
  • vector<ll> v(s.begin(),s.end());

4.d442: 10591 - Happy Number

  • 以set記錄曾經出現過的數字,產生下一數字時檢查是否在set中

5.f929: 程式老師的作業

  • 以set記錄0的index,因為set會自動排序,每次操作只要處理s.begin()即可。

6.c421: pA 雲端列印

  • multiset同set會自動排序,但允許重複
  • set: size、empty、begin、end(指向最後一個元素之後的位置iterator)、erase

7.a016: 數獨(SUDOKU)

  • 可用set記錄橫向、縱向、九宮格裏的數字,因為set會過濾重複的數字,判斷是不是剛好有9個數字

8.d194: 11572 - Unique Snowflakes

  • 求最長相異子序列
  • set:count、insert、erase、find
  • queue:front、push、pop、size
  • 當新元素x重複時,刪除queue中x之前的元素(可能產生最多相異的新的開始)

9.c423: pB 還原密碼

(五) 關聯式容器Associative Container(map)

EX_3_5_1:a743: 10420 - List of Conquests

  • 在map插入<key, value>時,就會按照key的大小順序儲存。
  • map:find、end、iterator
  • stringstream
  • cin.ignore()
  • C++11 auto
for(auto it=mp.begin();it!=mp.end();it++)
    cout << it->first << " " << it->second << endl;
        
for(auto elm:mp) //取得的元素是pair
    cout << elm.first << " " << elm.second << endl;

EX_3_5_2:e288: 互補CP

  • map<long long ,int> mp;
  • mp.find(),mp.end()
  • 位元運算(|、^、<<)
  • 可將第n位元作為有無對應角色的狀態。「1」代表有該角色,「0」代表沒有。
  • 若 a xor b = c 則 a xor c = b。
  • 解題參考
  • C++ IO加速

1.b162: NOIP2007 1.统计数字

  • map<int,int>
  • map插入<key, value>時,就會按照key的大小順序儲存。

2.c054: 10082 - WERTYU

  • map:find、end

3.d517: 文字抄寫 I

  • map<string,int>
  • C++ IO加速(+'\n')

4.d244: 一堆石頭

  • map<int,int>
  • iterator
  • C++11 auto

5.d492: 10226 - Hardwood species

6.b265: Q11286 - Conformity

  • 將課程代碼排序後組成字串當成map的key。

7.a821: 4.王者之路

  • 將每一隊擊數的隊伍以set記錄,輸出擊數隊伍數為n-1,且沒有被擊數的隊伍。
  • map<string, set<string> > mp;

8.e839: P6. 飲食分類 (Food)

  • map<string, vector<string>> mp;

(六) 容器配接器Container Adaptor(stack)

EX_3_6_1:b304: 00673 - Parentheses Balance

  • stack:push、pop、top、empty
  • 空的stack執行sk.top()會錯誤
  • scanf("%d\n",&n) 或cin.ignore() 將換行字元讀掉
  • 輸入有空字串,要輸出 Yes,所以以getline(cin,s)讀一整行

EX_3_6_2:c123: 00514 - Rails

  • 將車廂依序從A方向「push」進Station(stack),並檢查stack的top是否為B方向要的車廂編號,若是則「pop」(表示開到B方向)。
  • 最後檢查stack是不是空的。
  • stack:push、pop、top、empty
  • 空的stack執行sk.top()會錯誤

1.b923: stack 堆疊的模板題

2.d318: 11185 - Ternary

3.a132: 10931 - Parity

  • 以stack記錄除2的餘數
  • stack:push、pop、top
  • n&1
  • n>>1

4.a565: 2.p&q的邂逅

  • stack:push、pop、empty
  • scanf("%d\n",&n) 或cin.ignore() 將換行字元讀掉
  • C++ IO加速

5.e799: p6. 資工系的浪漫

  • 正整數 Si 要宣告為long long。
  • 10進位轉2進位。

6.f698: 後序運算式

7.b838: 104北二2.括號問題

  • 遇「(」push
  • 遇「)」檢查stack是否是空的,如果不空pop,如果空,則括號不正確。

8.最接近的高人

  • TCFSH CIRC Judge
  • 暴力法會TLE,由前往後看時,那些是沒有用的資訊?
  • 如果 a[i-1]<=a[i],那麼a[i-1]不可能是i之後的高人,因為由後往前找時,一定會先碰到ai
  • 所以只要以stack維護好一個遞減序列,就可有效率的解決問題。

9.c907: 尋找最大矩形

10.a017: 五則運算

(七) 容器配接器Container Adaptor(queue)

EX_3_7_1:e289: 美麗的彩帶

  • 顏色編號介於0~10^150,以string儲存顏色代號。map<string,int>記錄顏色的數量。(離散化觀念 discretization)
  • 因為順序不重要,可用unordered_map查詢會更快。
  • 滑動視窗,使用queue或deque,模擬區間由左向右滑,左邊出去一個顏色(front pop),右邊進來一個顏色(back push)。比對queue內相異顏色數量是不是等於M。
  • 因為n最大只到20萬,可以將所有的彩帶顏色讀入陣列,再以L、R代表要出去、進來的顏色索引,即不用用到queue。
  • C++ IO加速。

EX_3_7_2:b151: NOIP2004 2.合并果子

  • 取priority_queue中兩個最小值相加後再放入佇列
  • priority_queue< Type, Container, Functional >
    • priority_queue<int, vector<int>, greater<int>> pq;
    • priority_queue<int, deque<int>, greater<int>> pq;
  • 欲取最大值使用less,欲取最小值使用greater

1.e447: queue 練習

2.e155: 10935 - Throwing cards away

3.d221: 10954 - Add All

  • 取priority_queue中兩個最小值相加後再放入佇列。

4.d900: NOIP2010 2.接水问题

  • 依輸入序,將其時間與優先佇列中最小值相加後,再放入優先佇列。

5.d371: 3. Huffman編碼中的編碼效能問題

  • 需要求出Huffman code嗎?

6.b298: 老闆阿我要退貨

  • 先把有問題的廠商放入佇列,不斷的從佇列中取出廠商,並且把其下游的廠商加入佇列,直到佇列空為止。

7.f816: TOI_y21m4_a02Youtube

  • priority_queue + 前綴和(累積的下降度)
  • ios::sync_with_stdio(false), cin.tie(NULL); + '\n'
  • 解題參考

8.f174: m6a2-蛋糕(Cake)

  • 雙向佇列(deque)兩端都可push、pop:push_front、pop_front、push_back、pop_back。
  • 前綴和、單調隊列
  • 解題參考

9.f631: 同學會

  • 以 priority_queue 模擬。

10.c835: 第六題:背包問題

  • 以01背包問題的解法會TLE
  • 2(1或2或…n-1) + 2n-1 ≤ 2n

(八) pair

EX_3_8_1:a915: 二维点排序

  • 以pair改寫,pair的比較原則是先比前面元素,一樣再比後面元素。

EX_3_8_2:b563: 3.魔法學校交換生問題

  • {v1,v2} 或 make_pair(v1,v2)

1.b512: 高維度稀疏向量

  • scanf("%d:%d",&n,&m)可忽略 ':'

2.c012: 10062 - Tell me the frequencies!

  • vector<pair<int,int>> v(mp.begin(),mp.end());

(九) bitset

EX_3_9_1:f630: 5. 共同朋友

  • 相鄰矩陣平方,計算有多少1。
    [0110101011010010][0110101011010010]=[2111121111301101]
  • O(n3),以陣列表示朋友關系只會過88%,改以bitset表示朋友關係,並以AND取代乘法。
  • 檢查是否為0,用count()還不會全對,改用any()。
  • C++ I/O加速。

1.f629: 3. 樣本解析

  • 以 int(第0個bit記錄有沒有a,第1個bit記錄有沒有b…) 或 bitset 表示集合。
  • 解題參考

四、枚舉(enumeration)(Brute Force)

EX_4_1:b230: TOI2009 第二題:方便數

  • idoreal number
  • 使用三層迴圈分別列舉 a、b、c(1~65),計算非方便數,並以陣列標記。

EX_4_2:c460: 3. 軍隊部署

  • 單純窮舉會TLE,可利用特性只有8種排列組合來思考。
  • 記錄army[種族][特性]的數量,可將3種特性表示成1個特性值(用2進位觀點,ai權值4、ri權值2、di權值1)。
  • 對3種族的特性值窮舉,如果3個特性值位元運算為7,數量相乘。
  • 狀態壓縮

1.a583: 1. 座位距離計算問題

  • 窮舉2點間距離

2.d809: 黑暗土地

3.b122: 用餐地點 (Lunch)

  • 窮舉所有可能的用餐地點,計算移動時間

4.a364: 2.神秘的進位問題

  • 窮舉a,b,c,檢查 C(a, 3) + C(b, 2) + C(c, 1) 是否等於n

5.c049: 00356-Square Pegs And Round Holes

  • 窮舉1/4圓的格子情形再*4
  • 判斷格子的四個點是否都在圓內

6.d914 2. 圍棋資料庫比對

  • 窮舉比較棋盤上每個點的狀況

7.c093: 00608 - Counterfeit Dollar

  • 數據小,直接窮舉可能的24種答案,看那一組符合秤重結果

8.APCS 201806 第2題 完全奇數

  • 從n開始往後,將每個數字都拿來檢查,找到第一個完全奇數。(測資只能過兩組)
  • 找下一個、前一個完全奇數的規律。

9.c074: 00441 – Lotto

  • 不用DFS也可解嗎?

五、排序

EX_5_1:b966: 第 3 題 線段覆蓋長度

  • 開107bool陣列,讀一筆線段就從L標計到R,最後計算標計的數量。時間O(n)*O(107)可行嗎? 空間?
  • 將輸入線段依左端點座標排序。則前後兩線段的關係只可能為重疊(包含相連)或不重疊(新線段)
    • 如果下一線段的左端點 > 前一線段的右端點,表示前一線段已結束,計算並加總覆蓋長度。
    • 如果下一線段的左端點 <= 前一線段的右端點,表示前一條線段可延續,調整前一線段右端點位置即可。
  • 掃描線演算法(sweep line algorithm)

EX_5_2:g277: 3. 幸運數字

  • 區間範圍會越來越小,且區間外的數字不會用到。因此可以先將數列排序後,從頭開始檢查是否在區間內(區間外直接忽略),即是區間最小值。
  • 區間和用前綴和。
  • 可用 map 記錄數值的索引值。
  • 也可用線段樹找區間最小值。

1.a737: 10041 - Vito's family

  • 將所有親戚的門牌號碼排序,中位數即為 Vito 新家的門牌號碼。

2.d150: 11369 - Shopaholic

  • 將商品價格降序排序,再取每三個內的最小值
  • reverse
  • i+=3

3.c010: 10107 - What is the Median?

  • 每次輸入都排序會TLE。
  • 以insertion sort的觀念,在已排序的序列找出新數字的正確位置。

4.a539: 10327 - Flip Sort

  • 找出每個元素右邊比它大的有幾個

5.d385: 10905 - Children's Game

  • 比較函數(a+b)>(b+a)時為true

6.b542: 聽到這兩個人的身高,讓十萬人都驚呆了

7.d501: 第二題:數列最小值

  • 中位數
  • 如果有兩個中位數,介於其中的所有整數都是答案

8.d555: 平面上的極大點

9.f461: 現金兌換點卷

  • 巢狀迴圈的暴力法只能過50%,其餘會TLE。
for(int i=0;i<n;i++) for(int j=i;j<n;j++) sum+=abs(a[i]-a[j]);
  • 將卡片的數字由小到大排序(a0、a1、a2 an-1),現金點數總和為 (a1-a0) + (a2-a0) + (a3-a0) + …… + (an-1-a0) + (a2-a1) + (a3-a1) + …… + (an-1-a1) + …… ……+(an-1-an-2)
  • 上述式子裏加總 ai (0<=i<=n-1)出現的地方,可得到 i*ai - (n-i-1)*ai
  • 排序可用sort(a,a+n),需含入 algorithm 標頭檔。
  • 還需使用 scanf、printf 才會AC。
  • long long int

10.e809: 1.字母排序 (Letters)

  • 1<=Q<=102、1<=S<=5×106
  • counting sort
  • 前綴和
  • 2分搜

六、搜尋

EX_6_1:d732: 二分搜尋法

  • 函式陣列參數。
  • 陣列從index 1 開始存。

EX_6_2:e616: Aggressive cows

  • 最小值最大化
  • 對答案二分搜。假設一個答案,檢查這個答案是不是符合條件限件,以二分搜尋的方式逼進最大值。

1.f679: 公會成員

  • 二分搜尋可用lower_bound

2.e541: 10474 - Where is the marble

  • 二分搜尋可用lower_bound

3.b836: kevin戀愛攻略系列題-2 說好的霸王花呢??

  • O(N) -> O(log2N) -> O(1)

4.f815: TOI_y21m4_a01遊戲升等

  • 以二分搜尋找出符合條件的最大等級。

5.c575: APCS 2017-0304-4基地台

  • 對n個服務點排序,並計算服務點兩兩相鄰距離。若要分成K群,則找出前K-1個最大的兩兩相離距離,作為分群切割處。(時間複雜度高)
  • 實做可用二分搜尋的觀點。因為基地台直徑的答案一定介於1~(最遠服務點-最近服務點)。先假設可能答案為最大最小值中間,測試k個基地台可否覆蓋所有服務點,不行則調整基地台直徑,以二分搜尋法找出答案(直接對答案進行二分搜尋)。

6.c904: 天龍國的蜜蘋果

7.c942: 露營區規劃

  • 每個圓都至少有一個露營點,所以各點之間環狀距離的最大值為「最小圓周長」,最小值為 0。
  • 以二分搜尋測試假設的環狀距離,是否可以規劃出 M 個露營點。
  • 可假設 PI=2*acos(0);

8.圓環出口

  • TCFSH CIRC Judge
  • prefix。例如在位子i開始找一個j,使a[i]~a[j]的和>=Q,相當於找 prefix[j]>=prefix[i-1]+Q。
  • 二分搜尋
  • 解題參考
  • 因為 qi 不會超過 p 的總和,所以將原序列複製一次再求前綴和,可簡化操作。如果沒有此限制,也只需將 qi 預先 mod p的總和即可。

七、模擬

EX_7_1:f580: 2. 骰子

  • 骰子有每個相對面之點數和等於7的特性,所以只需儲存三個面的點數即可,如題目所提的上、前、右。
  • b為-1向前翻轉,所以原本上面會變成新的前面、原本後面(7-前面點數)會變成新的上面。
  • b為-2向右翻轉,所以原本上面會變成新的右邊、原本左邊(7-右邊點數)會變成新的上面。

EX_7_2:f313: 2. 人口遷移

1.c006: 10550 - Combination Lock

  • 逆時針旋轉度數為後刻度減前刻度

2.c036: 00573 - The Snail

3.c094: 00661 - Blowing Fuses

4.d192: 11351 - Last Man Standing

  • 模擬的時間為O(n*k),當n,k很大時會TLE
  • 遞迴解

5.c296: APCS-2016-1029-3定時K彈

  • 約瑟夫斯問題
  • 模擬的時間為O(n*k),當n,k很大時會TLE
  • 遞迴解

6.b351: 幻方(魔方陣)之一:奇N 階

  • 二維陣列
  • 全域變數
  • 記憶體不足
  • memset將陣列歸零,需含入 cstring 標頭檔
  • while(!(r == R && c == C))
    錯誤:while(r!=R && c!=C) r或c其中一個等於時就不繼續執行。

7.c292: APCS2017-0304-3數字龍捲風

8.c297: APCS-2016-1029-4棒球遊戲

八、Greedy

EX_8_1:d044: 例題 P-4-3. 十年磨一劍(最少完成時間)

  • TCFSH CIRC Judge
  • minimum completion time 經典題
  • 放在越前面的工作,等它的人越多,所以短的工作先做。

EX_8_2:d045: 例題 P-4-4. 幾場華山論劍(activity selection)

  • TCFSH CIRC Judge
  • activity selection problem 經典題
  • 若[x,y]是還未選取線段中右端點最小的線段,那麼最佳解一定會挑選[x,y]。
  • 一開始依照右端點由小到大排序,然後不斷將最小右端的線段挑進最佳解,略過與它重疊的線段。
  • 排序自訂比較函數的偷懶寫法→利用pair。

EX_8_3:c471: apcs 物品堆疊 (Stacking)

  • next_permutation計算所有排列的消耗能量,時間複雜度 O(n!)
  • 假設a,b其上物品的重量為x,則這些物品的順序,不會影響(a,b)或(b,a)消耗的能量的計算,所以只要考慮a,b順序即可。
    • (a,b)-> x*f(a) + (x+w(a))*f(b) = x(f(a)+f(b)) + w(a)*f(b)
    • (b,a)-> x*f(b) + (x+w(b))*f(a) = x(f(a)+f(b)) + w(b)*f(a)
    • 依兩兩物品(a,b) 其上重量*頻率的值排序(a.w * b.f < b.w * a.f)
  • w(i)/f(i) 由小到大排序。

1.d042: 例題 P-4-1. 少林寺的代幣

2.d043: 例題 P-4-2. 笑傲江湖之三戰

3.a465: 12405 – Scarecrow

  • 遇到可耕種土地時,即在右邊之土地放一個稻草人,並將已被涵蓋的可耕種土地視為不可耕種之土地

4.e538: 11389 - The Bus Driver Problem

  • 將早晨巴士路線由小->大排序,傍晚巴士路線由大->小排序。( sort搭配比較函式 greater<int>() )
  • 最短的早晨巴士路線搭配最長的傍晚巴士路線,會使支付的總加班費最小。

5.f832: 隕石 (Meteorite)

  • 將隕石重量、捕捉器容量排序
  • 由捕捉器容量大到小,決定是否可以裝入此時最大重量的隕石。

6.e801: p8. 排課表

  • 依照課程結束時間由小到大排序(結束時間早可增加後面選課的機會),然後從小的開始選。

7.f627: 1. 礦砂採集

  • Fractional knapsack
  • 依單位重量價值由大到小排序。
  • 不斷將單位重量價值最大的礦砂放入背包,直到背包已滿或沒有礦砂可放入。

8.d418: 00993 - Product of digits

  • 將整數分解因數,因為要求Q最小,所以從9開始找
  • 當因數全部分解完,n不等於1,表示不存在Q

9.b231: TOI2009 第三題:書

  • 印刷機只有一台,所以不管順序為何,總列印時間不變
  • 隨時可以裝訂無限本書,所以要先列印裝訂久的書

10.d731: 11039 - Building designing

  • 樓層分顏色儲存排序,分別從兩陣列中交錯拿出符合條件的最大面積
  • 運算子多載

11.c134: 00668 - Parliament

  • 將n切割成相異數字,並且各數字的乘積最大

12.a673: 10026 - Shoemaker's Problem

  • 兩相鄰工作a(Ta,Fa),b(Tb,Bb),無論成ab或ba,其他部分的罰金是固定的。差別在於ab(Ta * Fb)還是ba(Tb * Fa)的損失較小
  • 假如ab較小,則 (Ta * Fb)<(Tb * Fa) => (Fa/Ta)>(Fb/Tb) (a的「罰金/時間」比較大),因此工作的「罰金/時間」大的優先做
  • 解題參考

13.e915: pC. 追求完美的廚師

  • 點餐所需的累積時間要用long long。

14.f160: 1. 音檔剪輯

  • 從頭開始,盡量讓每次切割出的區間最長,區間個數即會最少。

九、Divide & Conquer

EX_9_1:d219: 00374 - Big Mod

  • 分配律
  • (A*B)%M=[ (A%M)*(B%M) ]%M→BP%M=[ (BP/2%M)*(BP/2%M) ]%M
  • EX:4*5%3=(4%3)*(5%3)、5*8%3=(5%3)*(8%3)%3

EX_9_2:d064: P-5-4. 反序數量 (APCS201806)

EX_9_3:d065: P-5-7. 大樓外牆廣告

  • TCFSH CIRC Judge
  • 以最小高為中間的切割點,如果每次的最低點都在邊緣,例如輸入高度是遞增或遞減,時間複雜度會高到O(n2)。
  • STL min_element

1.d636: 大爆炸bomb

2.a233: 排序法~~~ 挑戰極限

  • MergeSort

3.d542: 10810 - Ultra-QuickSort

  • MergeSort

4.b373: [福州19中]车厢重组

  • 當n很大時(100000),逆序數對O(n2)會TLE(TIOJ 1080)
  • 需用D&C(MergeSort) 或 BIT

5.d861: NOIP2001 3.求先序排列

6.d828: Pascal's triangle's secret (II)

7.f372: 崑棋的臭豆腐

十、Graph

(一) DFS

EX_10_1_1:d626: 小畫家真好用

  • 全域變數
  • 分四個方向做DFS

EX_10_1_2:d091: P-7-2. 開車蒐集寶物

EX_10_1_2:c463: apcs 樹狀圖分析 (Tree Analyses)

1.d365: 10336 - Rank the Languages

  • 類似d626

2.d165: 八、草场普查

  • 類似c129

3.c129: 00572 - Oil Deposits

  • 可以在地圖外包一層0,則不用檢查邊界
  • 可以使用陣列儲存要走的方向

4.a290: 新手訓練系列 ~ 圖論

5.c139: 00291 - The House Of Santa Claus

6.d324: 00750 - 8 Queens Chess Problem

  • 一維陣列queen[8],陣列索引為皇后的col,值為皇后的row

7.a229: 括號匹配問題

8.d115: 數字包牌

  • 窮舉

9.d653: VAC+ _ 社費問題 d115加強版

  • 剪枝(將不可能的解剪掉,不繼續遞迴下去)

10.b110: 3. 黑白影像的四分樹表示法

11.d536: 第三題:圖形迴圈偵錯問題

  • DFS偵測環

12.c291: APCS 2017-0304-2小群體

  • 陣列
  • 不斷追蹤下一位朋友,直到他已經被紀錄過
  • DFS偵測環

13.b967: 第 4 題 血緣關係

  • 類似c463

14.b108: 1. 銀河帝國旅行社

  • 類似b967

15.f161: 3. 尋寶之旅+ 在 DFS 過程中,每次走到一個節點,就將該點顏色數量加一。當 DFS 返回父節點時,把該點顏色數減一,以表示回復到沒有走到此點的狀態。

  • 在拜訪每個節點時,檢查該點的顏色數量有沒有超過最大值。
  • 寶石的顏色號碼不超過109,記錄每一顏色的寶石數用陣列會太大,離散化可以用 STL map

16.b343: 11518 - Dominos 2

  • 骨牌後可能有多張骨牌
  • vector二維陣列
  • v.clear()
  • fill()

17.d768: 10004 – Bicoloring

  • vector二維陣列
  • v.clear()
  • fill()

18.a470: 12406 - Help Dexter

  • 數字*10+1或2,產生下一位p位數DFS

19.d762: 10344 - 23 out of 58

  • next_permutation
  • DFS窮舉所有可能

20.c812: 1. 觀光景點

  • DFS搜尋所有和Vk相鄰的點
  • Edge List
  • vector、pair

21.f168: m4a2-分配寶物(Treasure)

  • 枚舉各個寶物分配的情況,總共有3^N種可能的組合。
  • 剪枝。

(二) BFS

EX_10_2_1:d090: P-7-1. 探索距離

EX_10_2_2:f170: m5a1-尋找小狗(Dog)

  • queue
  • pair
  • C++ IO加速

1.a982: 迷宮問題#1

  • queue
  • pair

2.d406: 倒水時間

3.d663: 11730 - Number Transformation

  • 產生轉換次數相同的所有數字B(佇列開頭A+小於它的質因數),放入佇列
  • 如果產生的數字已在佇列則忽略(新數字轉換次數一定較大)
  • 解題參考

4.c077: 00417 - Word Index

  • 取出佇列前的字串,添加可以加的字母後放入佇列
  • 使用map存字串對應的值

5.b059: 4. 靈犬尋寶

  • BFS
  • 類似a982: 迷宮問題

6.b701: 我的領土有多大

  • BFS或DFS

7.c117: 00439 - Knight Moves

  • 騎士L走法有八個方向
  • queue
  • struct

8.a634: 14. Knights Path

  • BFS+DFS

(三) Floyd-Warshall

1.d908: 4. 最佳路徑

  • memset
  • 因為陣列包含所有26個字母,所以檢查時沒有連通要略過

2.d282: 11015 - 05-2 Rendezvous

  • 先求所有兩點之間的最短距離,再加總求每個人到其他人的路徑總合最小
  • 整數最大值可用0x3f3f3f3f
  • memset(a, 0x3f, sizeof(a));

3.c128: 00544 - Heavy Cargo

  • d[i][j]=max( d[i][j], min(d[i][k],d[k][j]) )

4.a874: 14. Trace Route

5.a674: 10048 - Audiophobia

  • n[i][j]=min( n[i][j], max(n[i][k],n[k][j]) )

(四) Dijkstra

1.d793: 00929 - Number Maze

(五) SPFA(Shortest Path Faster Algorithm)

1.c125: 00534 - Frogger

(六) 最小生成樹

1.a129: 最小生成樹

2.b181: 2. 網路設計

3.d909: 公路局長好煩惱!?

4.e810: 2.潛水 (Diving)

(七) 尤拉路徑(Eulerian Path)

1.b924: kevin 愛畫畫

(八) 拓撲排序(Topological Sort)

1.f167: m4a1-社團 Club

2.a552: 模型

3.f628: 2. 村莊與小徑

  • 圖為 DAG(有向無環圖),所以存在拓樸排序,依照拓樸排序由前往後算,O(n+m)。
  • 邊的權重可能是負的,Dijkstra 不能處理負權的最短路徑。
  • Bellman–Ford / SPFA: 在最糟狀況下的複雜度為 Θ(nm),只能過比較小的測資。

(九) 最大流(Maximum Flow)

1.d667: 00820 - Internet Bandwidth

(十) 二分圖

1.c889: 2. 二分圖

2.c455: 4. 警力配置

(十一) 關結點(articulation point、割點)

(十二) 強連通元件

十一、Set

EX_11_1:a445: 新手訓練系列- 我的朋友很少

1.d831: 畢業旅行

  • 並查集(Union-find Sets、disjoint set)

2.d813: 10583 - Ubiquitous Religions

  • 並查集(Union-find Sets、disjoint set)

3.c131: 00615 - Is It A Tree?

十二、Tree

1.a584: 2. 親等關係

  • 找尋距離兩節點最近的共同祖先。

2.d526: Binary Search Tree (BST)

  • 鏈結串列
  • 二元搜尋樹

3.c126: 00536 - Tree Recovery

  • 二元樹追蹤(前序、中序、後序)

4.f163: 貨物分配

十三、DP

(一) 基本

1.d038: 00900 - Brick Wall Patterns

  • F(1) = 1,F(2) = 2,F(n) = F(n-1)+F(n-2)

2.d054: 11310 - DELIVERY DEBACLE

  • F(0) = 1,F(1) = 1,F(2) = 5,F(n) = F(n-1)+4*F(n-2)+2*F(n-3)
  • 解題參考

3.a111: 12149 – Feynman

4.d378: 最小路徑

  • dp[i][j]=min(dp[i-1][j],dp[i][j-1])+map[i][j]

5.d887: 1.山脈種類(chain)

  • F[0] = 1
  • F[n] = F[n-1]*F[0] + F[n-2]*F[1] + F[n-3]*F[2] +… + F[1]*[n-2] + F[0]*F[n-1]
  • 解題參考

6.b062: 1. 城市道路連通網

  • DFS會TLE
  • i->j路徑長度為m的走法,為檢查所有中繼點k(i->k->j)。
    亦即所有 i->k(直接連通) k->j(路徑長度m-1)的總和

7.d198: 00825 - Walking on the Safe Side

  • stringstream可能有問題?
  • dp[i][j]=dp[i-1][j]+dp[i][j-1];

8.c100: 00116 - Unidirectional TSP

  • 從右向左掃描,以解決要求輸出字典序最小的問題

9.f173: m6a1-作物種植(Plant)

(二) Maximum Consecutive Sum(MCS)

1.a540: 10684 - The jackpot

MCS(i)={element[i],MCS(i1)<0element[i]+MCS(i1),otherwise

2.d784: 一、連續元素的和

  • 類似a540

3.d206: 00108 - Maximum Sum

4.b565: 5.採蘑菇攻略問題

(三) 零錢

1.d904: 換零錢

2.d253: 00674 - Coin Change

3.d289: 多元一次方程式

  • 數學解?

4.b232: TOI2009 第四題:分房子

  • 將1,3,5,7,9…視為幣值,n間房子視為金額
  • f(n)=f(n-1)+f(n-3)+f(n-5)…

(四) 01knapsack

1.d637: 路過的鴨duck

  • F(n,w)為背包有前n樣物品,重量為w時的最大價值
    {F(0,j)=0F(i,j)=MAX(F(i1,jw[i])+v[i],F(i1,j))
  • 解題參考

2.a587: 祖靈好孝順

  • 二維 -> 一維

3.b184: 5. 裝貨櫃問題

  • 二維 -> 一維

4.b140: NOIP2005 3.採藥

5.b131: NOIP2006 2.开心的金明

6.a522: 12455 - Bars

7.f455: 詠竣的哀鳳12

6.d890: 3.禮物分配(gift)

  • 背包負重上限為所有禮物單價總和除以2
  • 物品重量與價值相同,取能放入背包的最大價值

7.d390: 00562 - Dividing coins

  • 同上

8.b116: TOI2008 3. 加減問題

  • 同上,問題可視為可否將N個正整數分成數值和相等的兩堆數字。

9.c147: 105北二5搬家規劃問題

  • ss.str("");
  • ss.clear();
  • stoi(str);

10.g278: 4. 美食博覽會

(五) LIS

1.d078: P-6-15. 一覽衆山小

2.d242: 00481 - What Goes Up

  • LIS(i)=MAX1<=j<i && element[j]<element[i] LIS(j)+1
  • 找出i之前所有比i小的元素j,LIS(i)即LIS(j)+1其中的最大值
  • 上述O(n2)的方法會TLE,要用O(nlog2n)的方法
  • Robinson-Schensted-Knuth Algorithm(只能求長度)
    • EX:
      451234515121231453214145135125

3.f608: 4. 飛黃騰達

  • 將點依 x 座標排序後,對 y 座標求LIS。
  • 排序時 x 相等則比較 y,可以用 pair 來記錄點,預設即會這樣比較。
  • STL vector(1) (2) [(3)]+ STL sort、upper_bound
  • STL pair

4.d052: 11456 - Trainsorting

  • 解題參考1解題參考2
  • fill()
  • LIS+LDS
  • 接後面的車廂重量要越來越小即LDS,接前面的車廂重量要越來越大即LIS
  • 計算每個節點的LIS、LDS,相加-1(自己會重覆)的最大值
  • 序列要逆序儲存(Why?)
    • LIS、LDS的最大值是記錄在序列最右的元素,但兩序列的接點卻是最左邊的元素

(六) LCS

1.c001: 10405 - Longest Common Subsequence

  • X陣列的index由0開始,長度i的元素為X[i-1]
  • LCS(0,j)=0 ,LCS(i,0)=0
    LCS(i,j)={LCS(i1,j1)+1,ifX[i]==Y[j]MAX(LCS(i1,j),LCS(I,j1)),otherwise

2.a133: 10066 - The Twin Towers

3.c499: ♋大耳神下麵真好吃♋

4.d674: 10192 - Vacation

5.d231: 97北縣賽-2-基因序列密碼問題

  • 記錄來源

6.a252: Another LCS

(七) 最小編輯距離(Minimum Edit Distance)

1.f507: 1207 - AGTC

2.e828: 3.猴子打字遊戲 (Typing)

(八) Largest Empty Rectangle

1.b123: 最大矩形 (Area)

  • 計算每列的面積,再往上找出能構成最大面積的高度

(九) 矩陣鏈乘積(Matrix Chain Multiplication)

1.d086: Q-6-18. 矩陣乘法鏈

2.c112: 00348 - Optimal Array Multiplication Sequence

3.d652: 貪婪之糊

4.f817: TOI_y21m4_a03枯枝

  • dp[i][j] = dp[i][i] + min( max(dp[i+1][k], dp[k+1][j]),i+1 ≦ k < j)

(十) 區間DP

1.d686: 10003 - Cutting Sticks

(十一) 集合最優配對

1.d879: 10911 - Forming Quiz teams

十四、數學

(一) 雜項

1.d111: 10110 - Light, more light

  • n的因數如果是奇數個,燈就會是亮的
  • 一個數會等於成對的因數相乘,完全平方數的因數個數為奇數

2.d361: 10515 - Power et al.

  • 將2n~9n的最後一個數字列表,會發現規律,最長的循環周期為4
  • 解題參考

3.a858: 數三角形

  • 正算 v.s. 反算

4.a241: 第二題:1 / x 是有限小數

  • x的因數只能為為2或5
  • 若用x是否能被2、5除盡的方式檢查,會TLE
  • 改進方式1:採用位元運算子x%2、x/=2 -> x&1、x>>=1
  • 改進方式2:建表查詢

5.b897: 10219 - Find the ways !

  • 直接計算n!會爆掉
  • 可用floor(log10(n))+1判斷n是幾位數
  • log10(1*2*3)= log10(1) + log10(2) + log10(3)
  • 解題參考

(二) 大數

1.c034: 00424 - Integer Inquiry

  • 大數加法

2.c119: 10220 - I Love Big Numbers

  • 大數乘法

3.a884: 11448 - Crisis

  • 大數減法

(三) 數論

1.d256: 11388 - GCD LCM

  • a、b是最大公因數的倍數,所以最小的a就是gcd(a,b)
  • lcm(a,b)=a*b/gcd(a,b),a為最大公因數,則b為最小公倍數
  • 最小公倍數(G)是最大公因數(L)的倍數,所以G%L!=0則輸出 -1

2.a007: 判斷質數

  • 單純埃拉托斯特尼篩法建質數表(取質數將其倍數們篩掉)還是會TLE
  • 埃拉托斯特尼篩法建質數表,只要判別小於等於根號此數的質數是否為其因數即可

3.d362: 10394 - Twin Primes

  • 以埃拉托斯特尼篩法建質數表,並同時找出所有的Twin Primes

4.b467: NOIP2013 Day1.1.转圈游戏

5.a289: Modular Multiplicative Inverse Extended Euclidean Algorithm

6.d440: 10299 - Relatives Euler's Totient Function

7.e902: 昴的交響樂

  • 模逆元

8.b429: 離散對數

(四) 機率

1.e162: 01636 - Headshot

(五) 矩陣

1.a410: 解方程

2.a272: 猥瑣罐頭下樓梯

3.d639: 企鵝村三兄弟penguin

4.e811: 3. 密碼產生器 (Password)

  • 矩陣建構
  • 矩陣快速冪

十五、計算幾何

1.d055: 11437 - Triangle Fun

2.d170: 飛蛾撲火(一)

十六、進階資料結構

1.d788: 排名順序

2.f315: 4. 低地距離

  • BIT

3.d794: 世界排名

  • BIT
  • 離散化

4.d847: 2D rank finding problem

5.d539: 區間 MAX

6.b687: 7. 坐好坐滿

  • Sparse Table

7.c424: pC 框架區間

  • 建Sparse Table,窮舉數列任兩數,只要兩數值差==序號差且,左數為區間最小值,右數為區間最大值即是一解