# GPE準備

- helpful ref: [GPE Helper](https://gpe-helper.setsal.dev/exams)
- [github repo](https://github.com/F64081169/UVa.git)

## 2023/10/18
[A.Search in Special array](https://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/)
- [code](https://github.com/F64081169/UVa/blob/main/A_SearchinSpecialarray.cpp):Binary search + Divide and conquer

[B.Climbing stairs](https://leetcode.com/problems/climbing-stairs/)
- [code](https://github.com/F64081169/UVa/blob/main/B_Climbing%20stairs.py):注意大數(用python)

[C.Oil Deposits](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=513)

- [code](https://github.com/F64081169/UVa/blob/main/C_OilDeposits.cpp):我憑我考試的印象重打一遍AC，但考試當下我吃WA拿部分分數而已，是judge有問題嗎？

[D.Take the Land](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1015)

- [code](https://github.com/F64081169/UVa/blob/main/D.Take%20the%20Land.cpp):DP，處理輸入的時候就建表，須再寫一遍

[E.Tight words](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1022)
[F.Minimal Coverage](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=961)
- [code](https://github.com/F64081169/UVa/blob/main/p10020.cpp)

## 2024/03/06

[A.Coronavirus]()
- [code](https://github.com/F64081169/UVa/blob/main/A_Coronavirus.py):F(n)=a*F(n-1)+b，且F(1)=1快速冪＋大數，因為10^18>N>0，會塞爆記憶體和O(n)仍然會TLE
- 一般式
- $a^{n-1}+b\times\dfrac{a^{n-1}-1}{a-1}$

- [費馬小定理求乘法逆元](https://medium.com/algorithm-solving/modular-multiplicative-inverse-333ab622d886)
- 乘法逆元`pow(a, p-2, p)`


[B.Largest Squares](https://leetcode.com/problems/climbing-stairs/)
- [code](https://github.com/F64081169/UVa/blob/main/B_LargestSquares.cpp):感覺是經典題

[C.Longest Increasing Subsequence](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=422)
- [IT邦幫忙](https://ithelp.ithome.com.tw/articles/10253577)
- [Leetocde 300](https://leetcode.com/problems/longest-increasing-subsequence/description/)

- [code](https://github.com/F64081169/UVa/blob/main/C_LongestIncreasingSubsequence.cpp):DP考試差點寫出來==

[D.Line overlap problem](https://gpe-helper.setsal.dev/problems#:~:text=2009%2D02%3A%20Line%20Overlap%20Problem%C2%A0%C2%A0)

- [code]():不會寫，很難==，可能需要線段樹。

[E.Network Connections](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=734)
[F.The Priest Mathematician](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1195)
- [code]()

## 2024/03/13
[A.Train swapping](https://onlinejudge.org/external/2/299.pdf)
- [video](https://www.youtube.com/watch?v=wF4vNZ_vHtE)
- [code](https://github.com/F64081169/UVa/blob/main/A_Trainswapping.cpp):reverse table紀錄之前的車廂有幾輛比自己大

[B.Dungeon Master](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/532.pdf)
- [code](https://github.com/F64081169/UVa/blob/main/B_Dungeon%20Master.cpp):給一個3D迷宮，求最短路徑（BFS）
- 三維迷宮問題。可以行走前後左右及上下六個方向。求起點(S)到終點(E)的最短路徑。
- 一個L層的立體地牢，每一層都有 R * C 格。格子內如果是石塊(“#”)表示無法通行。

[C.Bit Mask](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1659)

- [code](https://github.com/F64081169/UVa/blob/main/C_BitMask.cpp):用最直覺的方式寫會TLE，但還是可以80分

[D.Smith Numbers](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=983)

- [code](https://github.com/F64081169/UVa/blob/main/D_Smith%20Numbers.cpp):很簡單照刻就好

[E.The N-th Element](https://gpe-helper.setsal.dev/problems#:~:text=The%20N%2Dth-,Element,-%E5%AD%97%E4%B8%B2)
[F.Making Change](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=102)
- [code]()
## 2024/03/20
[A.Maximum Product](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2000#google_vignette)
- [code]():我建2D DP 算每個consecutive subset的和，然後return maximum value，這樣拿80分(可能有邊緣case沒寫好。

[B.Brick Wall Patterns](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=841)
- [code]():題目list的題目，只要考慮unsigned long long就會100分AC，費式數列。如果數值超過50就要處理大數問題。

[C.Sorting Array in Relative Order](https://www.geeksforgeeks.org/sort-array-according-order-defined-another-array/)

- [code]():用兩個hashmap紀錄每個element的count就會60分了，四十分是TLE，懶得解，我不求甚解。

[D.Umcompress](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=181)

- [code]():

[E.Irreducible Basic Fractions](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1120)
[F.Network Connections](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=734)
- [code]()

## 練習題

### 朋友分享的考古
- [A . Social Distancing 1.0](https://drive.google.com/file/d/1NOKVcmVC29PgJBKWjjQ5dmoraBDPn_UK/view?usp=sharing)
- [B . Coronavirus Outbreak](https://drive.google.com/file/d/1rks0REZyCDprKze9tDSaAZP0wnZOx5et/view?usp=sharing)
- [C . Buying Vaccines](https://drive.google.com/file/d/13GXfuJuj_lSIPMh5f-y1pWZB18jCK7AX/view?usp=sharing)
- [D . Social Distancing 2.0](https://drive.google.com/file/d/1lv5RORb6jyFk16BMGSzxkO8sm9k9UDps/view?usp=sharing)
### 刷題List2
- GPE mock1
- [Robot Instructions](https://github.com/F64081169/UVa/blob/main/Robot%20Instructions.cpp)
- [Dollars](https://github.com/F64081169/UVa/blob/main/p147.cpp)
- Easy Longest Increasing Subsequence
- Big Mod
- Oil Deposits
- Extend to Palindrome
- GPE mock2
- Happy Number
- Minimal coverage
- Largest Square
- Sudoku
- Longest Common Subsequence
- Dungeon Master
- GPE mock3
- Quirksome Squares
- Digit Primes
- Longest Paths
- Roads in the North
- Longest Increasing Sequence
- Network Connections
- GPE mock4
- The Priest Mathematician
- Power Crisis
- Rank the Languages
- Contest Scoreboard
- Tight Words
- Count the Trees
- GPE mock5
- Making Change
- Light, more light
- Show the Sequence
- Prime Distance
- Tug of War
- Marbles
- GPE mock6
- Simple Minded Hashing
- Smith Numbers
- Snow Clearing
- The Grand Dinner
- Uncompress
- Luggage
- GPE mock7
- Brick Wall Patterns
### [刷題List3](https://hackmd.io/@aKU8AeP1T0SbFrR-AtNANw/HJBhBuUB5#NYCU-GPE)
## [UVA practice github](https://github.com/F64081169/UVa.git)

~~p12503 p10404~~ ~~p10591~~ ~~p10905~~ ~~p11286~~ ~~p10057~~ ~~p900~~ ~~p10684~~ ~~p10324~~ ~~p991~~ ~~p147~~ ~~p10125~~ ~~p374~~ ~~p10664~~ ~~p1210~~ ~~p10020~~ ~~p572~~ ~~p10908~~ ~~p10298~~ ~~p10015~~ ~~p10162~~ ~~p10405~~ ~~p151~~ ~~p10003~~
~~p103~~

## Second round
[A_SearchinSpecialarray](https://github.com/F64081169/UVa/blob/main/A_SearchinSpecialarray.cpp)

- Binary search 變形，先判斷左右哪邊已經sorted（另一邊則為mountain起伏），再多注意target是是否在sorted的那邊。