1. 評量方式
- 上課基本練習 40%
- 作業解題數(ZJ共通過(AC)題數) 20%
- 本課程是為了考APCS,檢定的難度會比上課更難,不願意自主練習是沒機會到3級(約能完整解出2題)以上。
- 作業題目選擇
- 可從題單裏沒教過的題目選擇,或任選其它題目都可。
- 不會的可以去參考網路上的程式碼、解法。
- 同學也可以互相討論,而且是鼓勵的。
- 不論如何,都要在了解解法後,不看別人的程式碼,自己親自寫一遍。
- 不要為了分數直接貼別人的程式碼,那是無意義的行為,上機考你就會現出原形。
- 題數登記時間:上機考當週。
- 成績計算方式:作業不批改,以上機考檢核作業是否抄襲。
原始作業成績=min(題數*4,120)
if(原始作業成績>=100)
作業成績=原始作業成績*(上機考成績/100)
else if(上機考成績>=原始作業成績)
作業成績=原始作業成績
else if(上機考成績<原始作業成績)
作業成績=上機考成績
- 期中上機考 20%
- 時間約第1、2次期中考中間。
- 上機考時網路會切斷,無任何其它參考資料可看。
- 每單元請至少練習一半題目,熟練基本語法。
- 因為課程的目的是要考APCS,上機考會比較難,也會算分(資概的上機考只是基本語法檢核,不算分)。
- 期末作業解題報告 20%
- 上機考考差的同學請保握最後的機會。
- 10~12題。
- 每寫一題10分,上限120分(12題)。
- 期中考之前的舊範圍(上學期:四、陣列之前。下學期:STL 演算法之前),最多只能放3題。
- 其餘的必須是新範圍(上學期:五、字串之後。下學期:STL vector之後)新寫的題目,每個單元至多可放3題(不可以都寫同一單元的題目)。
- 每題的子標題為
(1) 單元、題號、題目、題目簡述
(2) 解題動態、評分結果截圖
(3) 解題思路
(4) 程式碼
(5) 反思(遇到的錯誤、修正的地方、更好的方法…)
(6) 錯誤程式碼
- 檢核方式
- 請儘量放一開始有錯,然後修正的題目。如果你每一題都是一次AC,那你應該是骨骼清奇、萬中無一的練武奇才,應該不用怕老師的檢核吧。
- 有交期末作業解題報告者,會請你在沒有網路的狀態下重寫一題當做檢核(題目由老師挑選),寫不出來作業直接作廢0分,所以作業請務必自思考己完成,如果你只想上網找程式複製貼上賺分數,就不用做這種白工了。
- 可放到學習歷程檔案。
- 成績計算
- 新手組:分數/300直接加在總成績。
- 潛力組:分數/100直接加在總成績。
- 上學期10、11、12月,下學期3、4、5月,最後一週。
- 星期一08:00 ~ 星期五20:00。90分鐘。
- 證書
3. 學習歷程檔案(修課記錄、課程學習成果)(Bonus)
5. APCS
6. APCS 實作題檢測從三級到五級(中正大學 吳邦一教授)
7. 軟體
8. 面試線上題庫
一、變數與運算子
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);
- 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
4.d226: 10071 - Back to High School Physics
5.d053: Big Chocolate
- 3x4巧克力需要11刀
- m-1+m*(n-1) (why?)
6.d489: 伏林的三角地
7.d827: 買鉛筆
- /、%、(( ))
- n/12*50+(n-(n/12)*12)*5
8.d277: 矩陣對角線
- 3元運算子、%
- 對角線奇數可共用對角線交叉的花盆,偶數不共用
9.b681: 1. 山洞探險
- 3元運算子
- 向北公式為2L-1,向南為?
- long long int
10.d127: 二、牧場面積
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_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';
}
}
1.d064: ㄑㄧˊ 數?
2.a012: 10055 - Hashmat the Brave Warrior
3.d058: BASIC 的 SGN 函數
- 巢狀if
- 比較運算子 > >= < <= == !=
4.d066: 上學去吧!
5.a006 一元二次方程式
6.a053: Sagit's 計分程式
7.d460: 山六九之旅
8.a273: 小朋友下樓梯
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_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_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: 我不說髒話
2.d490: 我也愛偶數
- for
- i=i+1(i++)
- 變數初值,區塊變數 v.s. 區域變數
3.d074: 電腦教室
4.c022: 10783 - Odd Sum
5.d356: NOIP2002 1.级数求和
- 型別轉換
- 浮點數誤差(float->double)
6.a147: Print it all
7.d010: 盈數、虧數和完全數
8.c299: 1. 連號或不連號
- 輸入數列時,找出其最大和最小值(可使用if或max、min函式)
- 最大-最小+1==n,表示這個數列是連續的
9.d186: 11461 - Square Numbers
10.e622: 虛擬寵物大師 (Master)
11.a038: 數字翻轉
12.a536: 11689 - Soda Surpler
- 每次換的汽水又可再變成空瓶子拿去換
- 可以換的汽水數量=所有空瓶數/c
- 手上空瓶=所有空瓶數/c+所有空瓶數%c
13.d189: 11150 - Cola
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
18.c420: Bert的三角形 (3)
19.f063: The Strongest Chain
20.c013: 00488-Triangle Wave
- 巢狀迴圈
- 下半部 for(k=A-1;k>0;k--)
四、陣列
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: 吞食天地
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_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_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: 電話客服中心
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
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)
3.c294: APCS-2016-1029-1三角形辨別
- 自定交換函式swap(傳參考呼叫)(除錯Step into)
- 使用swap讓a,b,c依小->大排序(c為最長邊)
4.a121: 質數又來囉
5.b112: 5.高中運動會
6.d237: 質數合
- 以質數函式測試是否需加此數
- 不可直接輸出142913828922
7.d117: 10924 - Prime Words
8.a623: Combination
9.d255: 11417 - GCD
10.c813: 11332 - Summing Digits
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: 合成函數
18.d269: 11579 - Triangle Trouble
一、物件導向簡介
二、stringstream
EX_2_1:d392: 读取练习——强大的加法!
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
三、C++ STL
(一) 演算法
EX_3_1_2:a362: 1. 搬雕像
- sort
- 自訂比較函式
- struct
- 排序後的位置-原來的位置編號
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 題 成績指標
3.f410: 芝麻街的郵件投遞
4.c230: 松鼠旅行
5.c044: 10008 - What's Cryptanalysis
6.d829: 00146 - ID Codes
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)
EX_3_2_2:d186: 11461 - Square Numbers
1.f819: 圖書館 (Library)
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_3:f607: 3. 切割費用
- 加分題。
- 依切割順序排序後,以set來儲存已切割的點,對每個切割點找它的前、後點。
- s.lower_bound()、s.upper_bound()
- insert() 返回值是pair<iterator,bool>,iterator代表插入的位置,若值已經在set中,則iterator表示原來值的位置;bool表插入是否成功。
- next(it)、prev(it)
1.a541: 字典
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 還原密碼
- set:begin、end、insert、erase
- for(auto it:s) //C++11
- stringstream字串數字轉換
- string字串截取str.substr(pos,n)
- C++基础-string截取、替换、查找子串函数
(五) 關聯式容器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)
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
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
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編碼中的編碼效能問題
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: 同學會
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。
- 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 第二題:方便數
EX_4_2:c460: 3. 軍隊部署
- 單純窮舉會TLE,可利用特性只有8種排列組合來思考。
- 記錄army[種族][特性]的數量,可將3種特性表示成1個特性值(用2進位觀點,ai權值4、ri權值2、di權值1)。
- 對3種族的特性值窮舉,如果3個特性值位元運算為7,數量相乘。
- 狀態壓縮
1.a583: 1. 座位距離計算問題
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
五、排序
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
6.b542: 聽到這兩個人的身高,讓十萬人都驚呆了
7.d501: 第二題:數列最小值
- 中位數
- 如果有兩個中位數,介於其中的所有整數都是答案
8.d555: 平面上的極大點
9.f461: 現金兌換點卷
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_2:e616: Aggressive cows
- 最小值最大化
- 對答案二分搜。假設一個答案,檢查這個答案是不是符合條件限件,以二分搜尋的方式逼進最大值。
1.f679: 公會成員
2.e541: 10474 - Where is the marble
3.b836: kevin戀愛攻略系列題-2 說好的霸王花呢??
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-右邊點數)會變成新的上面。
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. 十年磨一劍(最少完成時間)
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
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. 追求完美的廚師
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: 排序法~~~ 挑戰極限
3.d542: 10810 - Ultra-QuickSort
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: 崑棋的臭豆腐
- 如果只能通過75%,試著以數學觀念(費馬小定理)找出循環的現象,建表查表。
- 還需使用 scanf、printf 才會AC。
十、Graph
(一) DFS
EX_10_1_2:d091: P-7-2. 開車蒐集寶物
EX_10_1_2:c463: apcs 樹狀圖分析 (Tree Analyses)
1.d365: 10336 - Rank the Languages
2.d165: 八、草场普查
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: 第三題:圖形迴圈偵錯問題
12.c291: APCS 2017-0304-2小群體
- 陣列
- 不斷追蹤下一位朋友,直到他已經被紀錄過
- DFS偵測環
13.b967: 第 4 題 血緣關係
14.b108: 1. 銀河帝國旅行社
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
19.d762: 10344 - 23 out of 58
- next_permutation
- DFS窮舉所有可能
20.c812: 1. 觀光景點
21.f168: m4a2-分配寶物(Treasure)
- 枚舉各個寶物分配的情況,總共有3^N種可能的組合。
- 剪枝。
(二) BFS
EX_10_2_1:d090: P-7-1. 探索距離
EX_10_2_2:f170: m5a1-尋找小狗(Dog)
1.a982: 迷宮問題#1
2.d406: 倒水時間
3.d663: 11730 - Number Transformation
- 產生轉換次數相同的所有數字B(佇列開頭A+小於它的質因數),放入佇列
- 如果產生的數字已在佇列則忽略(新數字轉換次數一定較大)
- 解題參考
4.c077: 00417 - Word Index
- 取出佇列前的字串,添加可以加的字母後放入佇列
- 使用map存字串對應的值
5.b059: 4. 靈犬尋寶
6.b701: 我的領土有多大
7.c117: 00439 - Knight Moves
8.a634: 14. Knights Path
(三) Floyd-Warshall
1.d908: 4. 最佳路徑
- memset
- 因為陣列包含所有26個字母,所以檢查時沒有連通要略過
2.d282: 11015 - 05-2 Rendezvous
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.a129: 最小生成樹
2.b181: 2. 網路設計
3.d909: 公路局長好煩惱!?
4.e810: 2.潛水 (Diving)
(七) 尤拉路徑(Eulerian Path)
(八) 拓撲排序(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: 新手訓練系列- 我的朋友很少
- 並查集(Union-find Sets、disjoint set)
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
- F(1) = 1,F(2) = 5,F(n) = F(n-1)+n*n
- 解題參考
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
2.d784: 一、連續元素的和
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時的最大價值
- 解題參考
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
3.f608: 4. 飛黃騰達
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
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
(九) 矩陣鏈乘積(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: 數三角形
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.a410: 解方程
2.a272: 猥瑣罐頭下樓梯
3.d639: 企鵝村三兄弟penguin
4.e811: 3. 密碼產生器 (Password)
十五、計算幾何
1.d055: 11437 - Triangle Fun
2.d170: 飛蛾撲火(一)
十六、進階資料結構
1.d788: 排名順序
2.f315: 4. 低地距離
3.d794: 世界排名
4.d847: 2D rank finding problem
5.d539: 區間 MAX
6.b687: 7. 坐好坐滿
7.c424: pC 框架區間
- 建Sparse Table,窮舉數列任兩數,只要兩數值差==序號差且,左數為區間最小值,右數為區間最大值即是一解