現在要購買股票，每一個股票都有其花費和預期的在未來的出售價格。
但是股票採用組合包的方式進行販售，但是每一種組合包都只能購買一次，請問在資金只有 C 元的情況下，最多能在未來淨利多少。
|
|
|
|
每個東西只能購買一次，可見是一個 01 背包問題，但是由於 C 很大，也就是背包容量過大，導致 DP 上的困難。
但是題目並沒有特別說明測資的特殊性，後來才得知可以用 gcd 最大共同因數去降，就是縮小幣值，相當於換外國幣去思考。這麼一來 C 可以降很多，但在一般的背包問題中，gcd 的效應並不高。
把我的純真還回來啊，不想自己 yy 測資特殊性。
|
|
一個可以行走在靜止水面上的蜘蛛，現在要靠近瀑布，瀑布會於鄰近周圍會產生流速。
蜘蛛最多可以在 P 速度的水面上前進，請問最近可以靠近瀑布多少。現在已知從靜止水面靠近瀑布的部分流速，在未知的部分根據觀察是前面單位距離 1 距離 2 的線性關係。$v_{i} = a v_{i-1} + b v_{i-2}$)
|
|
|
|
其實這題不難，在最後已知得部分解二元一次方程式即可，把未知的流速算出來，統計可以跑多遠即可。
一開始看不懂題目，以為所有流速都是線性關係，求出來的答案怪怪的。從最後已知的四個流速推測剩餘流速。
|
|
平面上有士兵和戰車，分別有 S 個、T 個，接著會有 Q 組詢問，每組詢問有三條線，每組詢問之間的線保證斜率會彼此相同 (只是移動線，這需求非常奇怪。)，請問三條線拉出的 7 個區域中，中間與外側三塊地士兵、戰車個數差異為何？
|
|
|
|
先獲得需要劃分的斜率，對三種斜率進行點的排序，因此對得到六個排序結果 (士兵和戰車)。之後就能在排序結果中，二分搜尋該線的左側、右側分別有多少點。
解決這個之後，要來看看噁心的排容原理，這裡還是建議參照 flere 的圖示：
對於拉出的三角形三個交點編號 A, B, C，接著對其做區域編號，
(1) BC 線段的左邊 有區域 1 2 3 6
(2) AC 線段的左邊 有區域 2 6 7
(3) AB 線段的下面 有區域 2 3 4
(1) - (2) - (3) 就可以得到區域 1 - 2 - 7 - 4
就是我們要的答案
在程式邏輯上，挑一點與其一線同側，另兩條線與點異側。
沒有辦法單獨對區域內部搜尋點個數，然後統計完再相減，即使使用 range query，也無法在有效時間內完成任意三角形的範圍搜索 (矩形可以考慮，用等腰直角三角形也好。)。
|
|
給 N 個城市，城市之間會有 M 條當前的安全邊，在其餘邊皆有邪惡組織出現，來阻擋城市之間的運行。
現在人在編號 1，每次將隨機挑任何相鄰的城市走過去 (隔天又會再挑一個鄰近的城市)，如果走過去的路上遇到邪惡組織則會將其殲滅，請問期望值需要幾天才能將 N 個城市彼此之間都存有連通路徑。
|
|
|
|
特別小心輸出的誤差要在
1e-6，以為只需要輸出 1 位，結果一直 WA。
事實上，將狀態壓縮成每一個連通元件的節點個數，對於連通元件之間做拉邊即可。
對於狀態 u, v，期望值 E[u] = 1 + E[v] p + E[u] q，
E[v] * p 表示：將兩個不同連通元件之間拉邊，則會將兩個連通元件融合，機率 p。E[u] * q 表示：在各自的連通元件內布拉邊，不影響狀態結果。
左移一下得到 E[u] = (1 + E[v] * p) / (1 - q);
這一題必須考慮現在位於哪個連通元件，所以特別標記狀態的第一個連通元件為當前所在位置。
|
|
任挑三個點拉出三角形，三角形內部的點數期望值為何？
|
|
|
|
反過來寫，這一點會被多少個三角形包含住。
為了要計算這一個點 P 被多少三角形包含住，把這個點 P 當作基礎點，對其他點做極角排序。排序完套用極角掃描線算法，對於當前線上的點 Q，往回追溯 180 度內，任挑兩個點與其並成三角形，保證不包含 P。
那麼要得到包含 P 的就反過來用全部組合扣到不包含的結果。
因為要窮舉每一點做極角排序，作法會在 O(n^2 log n)。
|
|
將一個簡單多邊形三角化，並且讓最大面積的三角形越小越好。
|
|
|
|
矩陣鏈乘積的方式著手 dp。
在此必須檢查劃分兩區間的三角形中內部不包含任何點，這裡利用外積 cross 進行計算。
|
|
在 n 個點的高速公路上，需要監視 m 條邊上的情況，監視器只能位於點上，並且可以監控所有與該點相連的邊，費用有限最多只能放置 k 個監視器，找到其中一種使用少於等於 k 個監視器的方法。
|
|
|
|
解決最少點集覆蓋所有邊，是一個 NP 問題，雖然這一題已經給定限制搜索必須小於等於 K。
對於 DLX (Dancing Links and Algorithm X) 運用在最少重複覆蓋而言，K 是沒有太大的必要，事實上根據 degree 最大的節點開始窮舉的效果跟 DLX 差不多的。而這一題沒有要求最少，只是請求在範圍內的任一解輸出即可。
DLX 一開始用在精準覆蓋，解決重複覆蓋的效果只能說還算可以，大多的時間都花在計算估價函數，那個啟發式估價是用最簡單的貪心。有時候需要覆蓋的 colume 數量非常多，所以寫法上用 memset 也許是不錯的，但是用懶標記是更為快速。
DLX 的精神在於雙十字鏈表，並且每次找最少可能的 colume 開始窮舉，窮舉時會斷開所有相關在其他 colume 的可能，並在移除掉不需要窮舉的 colume，而在重複覆蓋上則不會移除掉需要窮舉的 colume。
- 精确覆盖：
首先选择当前要覆盖的列(含1最少的列)，将该列和能够覆盖到该列的行全部去掉，再枚举添加的方法。枚举某一行r，假设它是解集中的一个，那么该行所能覆盖到的所有列都不必再搜，所以删除该行覆盖到的所有列，又由于去掉的列相当于有解，所以能够覆盖到这些列的行也不用再搜，删之。- 重复覆盖：
首先选择当前要覆盖的列(同上)，将该列删除，枚举覆盖到该列的所有行：对于某一行r，假设它是解集中的一个，那么该行所能覆盖到的列都不必再搜，所以删除该行覆盖到的所有列。注意此时不用删去覆盖到这些列的行，因为一列中允许有多个1。这里有一个A*的优化：估价函数h意义为从当前状态最好情况下需要添加几条边才能覆盖。
這一題會有 n 個 row，每一個 row 會覆蓋第 i 個節點覆蓋哪些邊。因此需要對所有輸入的邊進行編號，也就是 colume 會有 m 個。m 最大 50 萬，窮舉起來相當刺激。
|
|
給一張圖有 N 個節點、M 條邊，其中要放置 S 台新主機於其中 S 個節點，而沒放置的節點繼續使用舊主機，為了服務舊主機的網咖，每個舊節點旁邊最多只能有一個新主機網咖。
請問有多少種放置方法。
|
|
|
|
對於每一個節點的連接方式用一個 32-bit 壓縮，接著窮舉所有可能放置方法 state，對於沒有放置的節點，直接壓縮結果與 state 做 AND 運算，算 bits 數是否都小於 2。
|
|
好比 2D 方格，從左下角到右上角的方法數。而這一題是在三維空間，一樣的方式要越來越靠近右上方的頂點，但是部分點會有障礙物，會造成無法通行。
題目給定的維度事實上是終點座標，而非該維度數，用 row major 的時候要計算 dim[i]+1。
|
|
|
|
特地用懶標記完成 dp 計算，但是忘了有可能無法抵達終點，忘了補上最對於終點的懶標記操作，直接輸出 dp[ret] 結果一直噴 WA。
懶標記檢查 if (used[ret] != testcase) dp[ret] = 0;。
|
|
給定一個 N x M 地圖，已知有部分的牆壁和一個透明的牆壁，每一個障礙物都佔據一個方格，而透明牆壁一開始不知道位於何處，直到碰壁的時候才發現，找一條最慘情況下的最短路徑。
|
|
|
|
最小化最大值，首先窮舉任何一個透明牆壁可能出現的地方，對於透明牆壁的鄰近四格建立再碰壁方向下，抵達終點的最短路徑。
接著，使用最短路的方式進行更新，在這裡使用 dijkstra 的方式，對於每一個點的狀態為 (走到這裡第幾步) = 從起點走到這，最慘的偏移路徑最小化 為何。
概念上理解，設計一條路徑，路徑畫好後，對於每一點賭下一個點就是透明牆壁，偏移路徑長最長為何就會是該路徑的花費。
|
|