Peienwu's Blog

題目敘述
給定二維平面上 $n$ 個點，每一點都有座標 $(x_i,y_i)$ ，求出最近的點對之歐幾里德距離為多少？
$dis(p_i,p_j) = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$

閱讀全文 »

這個暑假看了動態規劃(1),(2)，線段樹、最短路徑、計算幾何、字串演算法，這一篇的完成算是暑假的一個里程吧！接下來繼續學習不同的主題，再把筆記更新到部落格中！

課程內容

字串

• 定義
  • 大寫 $\Sigma$ 表示字元集
  • 字串：有限個字元集組成
  • $|\Sigma|$ 字元集大小、|S|字串長度
  • S[a:b]表示連續從字元a到b
    閱讀全文 »

題目目錄

• 可魚果運輸問題
• 百慕達三角洲
• 江神與他的小火車
• 貨物運送計劃
• E.漢米頓的麻煩
• 旅遊規劃問題
• Codeforces 543B: Destroying Roads
  閱讀全文 »

動態規劃的要素

可以動態規劃的問題符合兩個條件

• 重複子問題
• 可分治性

動態規劃的三要素

• 0.定義
• 1.狀態轉移方式
• 2.初始狀態（邊界條件）

上課內容

雙連通元件

樹壓平、點雙連通、邊雙連通

SCC強連通元件

LCA（最低共同祖先）

今年是2021，資芽的二階主題跟2020上的有很多的差別，因此會利用暑假把2020的東西也補一補！

課程內容

儲存

線段樹很多人都用陣列來實作，空間$O(n)$，在處理樹的左右節點也十分的方便。如果以1-base來儲存陣列這棵線段樹，左右節點可以用以下的index來表示。線段樹有一個優點就是它可以用儲存完滿二元樹的方式來儲存，雖然它不一定是完滿但會是平衡的一棵樹。左節點：$2n$，右節點$2n+1$。

題目目錄

• 向量加法
• 等長線段對
• 向左轉向右轉
• 線段相交
• 最小凸多邊形
• TIOJ 1178 Convex Hull
• 來吧，遊戲開始了
• 遊戲：最終回
• TIOJ 1205 直角三角形
  閱讀全文 »

此文將從萬有引力定律開始，在只考慮萬有引力的狀況下，探討衛星運動、雙星運動、三星運動、四星系統甚至是N體問題的軌跡與運動模式並進行模擬，並進行理論的驗證。

模擬連結：點這裡

理論與數學

萬有引力定律

牛頓於1687年提出：「任何兩個質點之間必有一吸引力F，其量值和兩質量的乘積成正比，和它們之間的距離平方成反比，其方向在連心線上。」

P1 修補圍籬

題目連結

題解

如果在兩端就直接取旁邊的高度，否則取跟左右邊高度的最小值。

資訊之芽的上課內容，用了幾節下課加回家的時間把程式實作出來
用紙跟筆解數獨的過程就是把所有可能剔除明顯不可能的之後下去試，如果遇到問題就換下一種方式