演算法解題(2)

練習題uva-1001 - Say Cheese，Floyd演算法找最短路徑，hole與hole之間可以快速轉換，吃cheese的速度很慢，hole與hole中心點之間直線是最短距離，求出n個hole之間的距離儲存到G[][]，開始與結束點可以視為兩個hole，半徑為0，相當於求n+2個hole的G[n][n+1]最短路徑。

Topology Sort

*(上課)練習題 uva 10305 - Ordering Tasks 使用陣列紀錄每個點的in-degree，若某點的in-degree為0，該點可以輸出，並將該點所連出去所有點的in-degree減1，再找出下一個in-degree為0的點輸出。

APCS202306第4題開啟寶盒拓樸排序 2023.06.19

APCS202401第3題邏輯電路類似拓撲排序 2024.01.12 C++

Euler Circuit一筆畫

練習題 uva-10129 - Play on Words Euler Circuit問題

Kruskal最小生成樹前言--並查集(Union-find Algorithm)

練習題UVa1160-X-Plosives 2021/01/25

練習題UVa 1329 - Corporative Network 2021/01/26

Kruskal最小生成樹

練習題 a129-最小生成樹 Kruskal、最小生成樹

練習題 d909: 公路局局長的煩惱！？ Kruskal、最小生成樹

練習題 d946-npsc-高中組初賽 D. 阿克圖洛斯‧蒙斯克的煩惱 Kruskal、最大生成樹

練習題 acm 10034 – Freckles Kruskal、最小生成樹，輸出距離和

練習題 acm 10147 – Highways Kruskal、最小生成樹的變形，已經有一些邊被選了，輸出選擇的邊

練習題 acm 10397 - Connect the Campus Kruskal、最小生成樹的變形，已經有一些邊被選了，輸出距離和

acm 10034 – Freckles、 acm 10147 – Highways與 acm 10397 - Connect the Campus三個問題很接近。

練習題uva-1395-SlimSpan Kruskal由最小weight為起始邊，找出生成樹，就計算苗條度，不斷往越重的邊為起始邊，直到起始邊的剩餘邊數一定要大於n-1個邊

練習題uva1665-Islands，Kruskal演算法變形，將每個點以高度由高到低排序，每次找高度最高的點，與附近四個點看高度是否也符合，若是進行合併。

articulation point(關節點)

練習題 acm-10199 - Tourist Guide articulation point

練習題 acm-315-Network articulation point

articulation edge(關節邊或橋)

練習題 uva796 - Critical Links articulation edge

練習題uva-12783 - Weak Links articulation edge

Strongly connected components

練習題 b201:npsc2008高中組初賽 F. 國家有向圖的Strongly connected components使用deque建立順向與逆向adjacency list，使用algorithm的sort

MAX-Flow

練習題 10092 - The Problem with the Problem Setter MAX-Flow

練習題 10249 - The Grand Dinner MAX-Flow

練習題uva-753-A Plug for UNIX 插座到目標點流量為1，來源點到設備流量為1，設備到設備的插座流量為1轉換器的兩種插座流量為無限大。使用hash(map)將字串名稱轉成數字，最後使用Edmonds-Karp演算法計算最大流量。

練習題11082 - Matrix Decompressing所有陣列元素值減去1，起始點到第j行加總的每個點(編號為j)，流量為Cn[j]-R，所有陣列元素值減去1，第j列加總的每個點(編號為C+j)到結束點T，流量為Rn[j]-C，第j行加總的每個點(編號為j)到第k列加總的每個點(編號為C+k)，流量上限為19(每個元素值為0~19)，表示Ajk元素的值，Ajk正確元素值須加1，最後求出邊中fm為j，to為C+k的邊，f+1就是Ajk的解。

練習題 uva-1658 - Admiral最小流量最大花費MinCost-MaxFlow，點1對應的點v+1，流量為2，花費為0，點1為出發點，點2對應的點v+2，流量為1，花費為0，點3對應的點v+3，流量為1，花費為0，...，到點(v-1)對應點(v+v-1)，流量為1，花費為0，點v對應的點v+v，流量為2，花費為0，點2*v為目標點，題目輸入邊，點a到點b的邊，花費為c，相當於點a+v到點b，流量為1，花費為c，不斷找出最小花費的最大流量，maxF回傳true就繼續找下一條路徑的花費。

練習題 uva1349 - Optimal Bus Route Design 最小權重的二分圖完美匹配，來源點在2*n+1，目標點在T=2*n+2，n為點的個數，根據題目敘述，點j到點a，流量為1，花費為c，j等於1~n；點S到點j，流量為1，花費為0，點S為出發點，j等於1~n；點n+j到點T，流量為1，花費為0，點T為目標點，j等於1~n。不斷找出最小花費的最大流量，maxF回傳true就繼續找下一條路徑的花費。

練習題uva 820 - Internet Bandwidth最大流MaxFlow，雙向流，建立亮兩個方向的流量

練習題uva-1660 - Cable TV Network，最大流MaxFlow，拆點，雙向流，建立亮兩個方向的流量。v-> v+n ，流量為1，v=0~(n-1) 。邊(a,b)，改成v+a -> b，流量為INF；v+b -> a，流量為INF。列舉s與t，將s->s+n，流量為INF；將t->t+n，流量為INF，求MaxFlow(s,t+n)

練習題uva1663 - Purifying Machine二分圖最大匹配數，先將點分成兩部分以color[]的值決定，這兩部分內的點之間都不能有邊相連，color[]的定義為跟第一個數字字串差奇數個color[]為1，跟第一個數字字串差偶數個color[]為0。來源點S在n，目標點T在n+1，n為點的個數，在左半部點j(color[]為0)連到點j有關係的點(color[]為1且數字差異的個數為1)，流量為1，點S到點j(color[]為0)，流量為1，點S為出發點，點k(color[]為1)到點T，流量為1，點T為目標點，找出最大流量，結果為點的個數減去最大流量。

練習題uva12549 - Sentry Robots二分圖變形，列的編號記錄在row[][]，從1開始編號，遇到障礙要拆開，假設編到R，行的編號記錄在col[][]，從R+1開始編號，遇到障礙要拆開，假設編到R+C。來源點S在0，目標點T在R+C+1，根據題目敘述，使用巢狀迴圈找出所有gra[][]為1的點，該點的row[][]到該點的col[][]，流量為1，點S到1~R，流量為1，點S為出發點，點(R+1)~(R+C)到點T，流量為1，點T為目標點，找出最大流量。

Floyd's cycle-finding algorithm

練習題uva-1594 - Ducci Sequence 暴力或Floyd's cycle-finding algorithm解題

其他

練習題 115 - Climbing Trees 建立關係圖，使用DFS找尋要查詢兩位關係的所有祖先，再判斷是什麼關係。

練習題 d768: 10004 – Bicoloring DFS加上顏色判斷

練習題 10054 - The Necklace Euler Cycle

練習題 acm-10158-War 使用集合與集合的聯集

二分圖(Bipartite Graph)

練習題 APCS202111 第4題真假子圖 DFS、並查集、二分圖

練習題 UVa1627 - Team them up 二分圖+DP 2024.02.01

ch12幾何

練習題d055: 11437 - Triangle Fun

練習題UVa11646 - Athletics Track 圓弧 2021.12.08

練習題 uva 1451 Average

Step1)已經形成下凸幾何圖形所有點，新加入的d點，若造成下凸幾何最後一些點變成上凸點就可以刪除這些上凸點

Step2)在剩下的下凸點中，找出至少長度為L的i點，i點與剩下的下凸點斜率最大的值，若斜率一樣最比較長度是否較短，

較短就更新長度、紀錄起始點與終止點；若斜率較斜更新長度、紀錄起始點與終止點。

練習題d170-飛蛾撲火(一)

練習題c049: acm-356-Square Pegs And Round Holes 判斷四分之一圓的每個方格的四個點是否在半徑內，或者部分在半徑內，或都沒有

練習題378 - Intersecting Lines 四個點求直線，八個點求兩條線是平行、重疊、交於一點，是否有相同斜率不要用除法，zerojudge會有浮點數不精確問題

練習題c116-uva-438The Circumference of the Circle 平面中三點求圓的周長

練習題d174: uva10297: Beavergnaw 公式解

練習題uva 1641 - ASCII Area由上到下，由左到右，奇數的/或\表示之後的.在圖形內

練習題uva1643 - Angle and Squares，外積求面積，最大面積為所有正方形對角線成一直線相連

練習題105北市賽導線短路判斷兩線相交

練習題 UVa 1398 - Meteor 計算XY平面的直線運動多鍵值排序 2020.10.17

練習題UVa11178 - Morley's Theorem計算兩直線交點 2021.11.26

練習題UVa1342-That Nice Euler Circuit 尤拉定理 2021.11.29

練習題UVa11800 - Determine the Shape 內積與外積 2021.12.08

練習題UVa 12304 2D Geometry 110 in 1 與圓有關的計算幾何 2021.12.1

練習題103北市賽領土凸包

練習題UVa-10652 - Board Wrapping 凸包 2021.12.4

練習題UVa11168 - Airport 凸包 2021.12.5

練習題UVa10256 - The Great Divide 兩凸包是否相交 2021.12.5

練習題UVa11275 - 3D Triangles 三維計算幾何 2021.12.7

ch13數學

練習題a059. 完全平方和

練習題d059: 數學函數練習

練習題d493-入求(求系列1)

練習題d171: 飛蛾撲火(二)

練習題d658: acm 11636 - Hello World 取log2

練習題d709: 判断质数（一）求質數演算法要優化

練習題d265:acm10165 Stone Game exclusive-OR

練習題c015-uva-10018 reverse and add

練習題uva 701 - The Archeologists' Dilemma 使用數學對數，N*10^K <= 2^E < (N+1)*10^K 取log2，log2(N)+K*log2(10)<= E < log2(N+1)+K*log2(10) K=(輸入N的位數加1開始往上遞增)直到包夾一個整數為止。

練習題a993-uva 10127 – Ones 數學數字位移與求餘數

練習題uva-847 A Multiplication Game 2 - 9 Stans Wins. 10 - 9x2 Ollie Wins. 9x2+1 - 9x2x9 Stans Wins. 9x2x9+1 - 9x2x9x2 Ollie Wins

練習題uva-10049Self-describingSequence 1,2,2,3,3,4,4,4,5,5,5,6,6,6,6….

練習題a007判斷質數使用篩選法求質數。

練習題c088: 00516 - Prime Land 質因數分解

練習題d362: 10394 - Twin Primes 求20000000以內所有質數，n與n+2皆為質數使用篩選法求質數。

練習題a702: Cousin Primes求20000000以內所有質數，n與n+4皆為質數使用篩選法求質數。

練習題a626: 6. Prime Directive 求1000以內所有質數五個五個一行

練習題d613: Prime Gap質數與質數間間隔幾個數字，使用二元搜尋

練習題d239: Problem 47 找出質因數分解連續四個數都有四個質因數

練習題d262: Problem 47 HARD找出質因數分解連續五個數都有五個質因數

練習題a647: 投資專家不要用除法，要小數點以下三位轉成整數相除，再四捨五入

練習題d256: 11388 - GCD LCM

練習題uva11582-ColossalFibonacciNumbers Fib數列求2到1000的餘數，Fib(0)=1,Fib(1)=1，找到下一個重複的0,1，求出2到1000的長度與餘數數列，長度(儲存在cycle[])與餘數數列(儲存在m[][])。Fib(a^b)求n的餘數，相當於求(a%cycle[n])^b除以cycle[n]的餘數(使用divide-and-conquer)，依照此餘數再到m[n][餘數]得到結果

練習題uva12169 - Disgruntled Judge列舉a與b，根據x1、x3...判斷是否a與b是正確的，若正確，輸出x2、x4...

練習題uva10375 - Choose and divide p!/(q!(p-q)!)=p(p-1)(p-2)…(p-q+1)/q(q-1)(q-2)…1 => (p-q+i)/i,i=1,2,3,…,q 而 (s!(r-s)!)/r!=s(s-1)(s-2)…1/r(r-1)(r-2)…(r-s+1) => i/(r-s+i),i=1,2,3,…,s

練習題uva1635 - Irrelevant Elements將m進行質因數分解，m最大到1000000000，先求出100000以內質數，進行質因數分解，判斷C(n-1,i)是否是m的倍數，是否大於m質因數分解的每個質數的次方值

練習題uva10820 - Send a Table 求小於等於n所有任選兩數互質的個數令為f(n)，phi(i)為小於i與i互質的個數，f(n)=phi(2)+phi(3)+…+phi(n)，答案為2*f(n)+1，1為(1,1)，2*f(n)表示兩數可以互換，視為不同。

練習題uva1262 - Password找出每行相同的字元，去除重複的字元，將字元進行排序，記錄每行字元個數，利用排列的概念、除法與求餘數得到最後的答案。

練習題uva1636 – Headshot，shoot機率，計算00個數除以00與01個數加總(0的個數)，第一個與最後一個字元視為相連， rotate機率，計算0個數除以字元長度

練習題uva10491 - Cows and Cars機率，第一次選到cow的機率cow/(cow+car)，選擇一定換到車的機率car/(cow+car-show-1)，第一次選到car的機率car/(cow+car)，選擇一定換到車的機率(car-1)/(cow+car-show-1)

練習題uva12230 - Crossing Rivers期望值，過河的時間介於L/v與3L/v(到時船已經開走)，平均期望值為2L/v，走路的時間為走路的距離(D-sum(L))/1

練習題uva11346 – Probability 積分

練習題uva11971 - Polygon機率與幾何，無法形成多邊形，其中一邊大於等於一半，其餘k個點(含最大邊的另一端點)落於另一

半，機率為1/(2^k)，這樣的k點有k+1種可能組合，1減去無法形成多邊形，就是可以形成多邊形，1-(k+1)/(2^k)=(2^k-k-1)/(2^k)需約分

練習題uva1640 - The Counting Problem 假設a<b，分別計算0到(a-1)與0到b所有數字出現次數，將0到b所有數字出現次數減去 0到a所有數字出現次數

練習題uva 1363 - Joseph's Problem，n與k，i=1到k，n/i=p(取整數)，相同p的情形下，餘數呈現遞減等差數列，等差數列有n/i=p...q第一個遇到的i，q/p+1為等差數列的長度

練習題uva11440 - Help Tomisu，1到m!的所有數求與m!互質的個數，相當於取phi(m!)，m為非質數，phi(m!)=phi((m-1)!)*m，m為質數，phi(m!)=phi((m-1)!)*m*(1-1/m)=phi((m-1)!)*(m-1)，答案為phi(m!)*n!/m!

練習題uva-10791 - Minimum Sum LCM，質因數分解，每個因數與該因數的指數當成一個數字的和最小。n=1，結果為2；當質因數只有一個數字，結果為n+1；n=2147483647,是質數，結果為n+1，使用int會溢位。

練習題 uva1644 - Prime Gap質數與二分搜尋

練習題uva1210 - Sum of Consecutive Prime Numbers連續質數和

練習題uva10539 - Almost Prime Numbers利用篩選法找出1000000以內的質數，將所有質數的二次方、三次方...小於10^12以內的n次方都加入陣列中，排序陣列，使用二元搜尋左邊界與右邊界，輸出左右邊界相減的個數。

練習題uva294 - Divisors，求出31622(sqrt(10^9))以內質數，利用這些質數進行質因數分解。

練習題10622 - Perfect P-th Powers，求出31622(sqrt(10^9))以內質數，利用這些質數進行質因數分解。注意-2^31與負數，負數的次方須除以2剩下奇數為止

練習題uva 11526 - H(n) n/i結果相同的數字，一起累加，注意n<=0的部分，輸出0

練習題UVa 12716 - GCD XOR 2024.02.17

練習題UVa 11105 - Semi-prime H-numbers 2024.03.03

ch14 IterativeDeepening反覆運算加深搜尋(IDA)

練習題 uva1374-Power Calculus 使用iterative deepening，不斷增加深度，每次只能使用一個乘法或除法，一次只能增加一個新的次方

練習題uva-1343-The Rotation Game，在DFS過程中使用目前深度(d)，與八個位置中1,2,3數字，最多的數字個數，將8減去上述數字，得到mindiff，還差幾個數字完成8個都相同，將d+mindiff進行剪枝