給定 n 個圖騰的座標，問有幾個格子點與奇數個圖騰恰好在距離 r 裡面。
觀察：滿足所求的格子點 x, y 座標的值會坐落在 [100-r, 100+r] 裡面。
因此可以枚舉範圍內的所有格子點，每枚舉一個點再花 O(n) 檢查與 n 個圖騰的距離就可以算出答案。 複雜度 O(1002 n)。
雖然只有一個圖騰，但因為圖騰座標的範圍很大不能像 subtask 2 一樣枚舉地圖上的所有點。
因為符合所求的點必須要和圖騰在距離 r 裡面， 可以辦法以 (x1, y1) 為中心往外枚舉。 一個簡單的方法是可以 x 座標枚舉 x1 ± r， y 座標也一樣枚舉 y1 ± r。
這樣枚舉的點數是 O(r2) 且可以枚舉所有與圖騰距離 r 以內的點。
觀察:
延伸 subtask 1 的解法，從某個圖騰旁距離 r 的點開始枚舉。 可以一邊枚舉點，一邊紀錄與枚舉的點距離 r 以內圖騰的數量：
int count_ans(vector<Point> input_totem) {
// cnt[x] = 與 x 距離 r 內的圖騰數量
unordered_map<Point, int> cnt;
for (Point t: input_totem) {
for (Point p: distance_r(t)) { // distance_r(x) 回傳與 x 距離 r 以內的所有點
cnt[p] += 1;
}
}
int ans = 0
for (auto it: cnt) {
if (it.second %2 == 1) {
ans += 1;
}
}
return ans
}
如上，用 unordered_map, hash_map 等資料結構可以簡單紀錄與一點距離 r 內的圖騰數量， 複雜度為 O(nr2)。
順帶一提，在 unordered_map 中要拿 non-native type 當 key 的話 hash function 是一個不得不注意的事情。 這裡提供一個壞的範例如下:
struct Hashp {
size_t operator () (const Point &a) const {
return hash<long long>()(a.x) ^ hash<long long>()(a.y);
}
};
在這個實作中 std::hash()(a.x) 與 std::hash()(a.y) 的 xor 和被當作一個二維座標的 hash 值。
很不幸這個實作是會超時的（一敗），原因是在 GCC 的實作裡 std::hash<int>()(x) 的回傳值就是 x 本身(ref) 不夠分散，
在圖騰集中的情況下會有大量的 hash collision 造成 lookup 退化到線性。
一個好一點 hash 實作如下:
struct Hashp {
size_t operator () (const Point &a) const {
return 10'000'000LL * a.x + a.y;
}
};
給一個鍵盤，一開始左、右手食指分別在 F 與 J 的位置。 每次可以選擇一隻手指往按鍵的旁邊六個相鄰按鍵移動，移動需要花 1 單位時間， 除了移動以外其他時間不計。
給一個字串 S，問最少需要花多時間才能輸入完整個字串。
定義以下 DP 狀態，dp[i][c1][c2] = t:
可以寫出以下轉移式:
dis 的表格可以預處理用 BFS 或 ad-hoc 的算出來。 轉移所要花的 iteration 次數為 263 n。
另外上面的 DP 式裡，Si+1 的維度其實可以刪除只記錄非 Si 那隻手指的位置：
dp[i][c] = 一隻手指在 Si，另一隻在 c 按完前 i 字元所花最少時間。
從 dp[i][c] 往前找 dp[i-1][*] 的狀態需要花 O(26) 轉移， 但如果從 dp[i][c] 往後推到 dp[i+1][*] 的話轉移只需要 O(1)。 因此可以做到複雜度 O(26n) 的 DP。
給一棵樹，樹上每個節點是個 ubike 站點。 已知一共有 nk 台自行車，問要如何移動自行車，使得每個站點恢復恰有 k 台自行車的狀態， 且移動距離總和最小。
可以反著考慮每條邊最少要有幾台自行車經過。 考慮某條邊 e 以及 e 兩頂點所形成的子樹 T1, T2。 若 T1 的頂點上共有 W1 台自行車，T2 共有 W2 台。
則可以發現至少要有 |k|T1| - W1| = |k|T2| - W2| 台自行車需要單方向通過邊 e。 此數字是要恢復題目所求狀態要經過 e 的最小自行車台數。 因此將每條邊的必經自行車台數乘以邊長加總可以得到一個答案的 lower bound，又這個下界也同時是個可行解， 根據 duality principle 可以知道我們找到一個最佳解。
另外可行解的證明可以用類似歸納法的方式來想， 詳細的說明因為作者語彙力太低無法將概念言語化所以這裡就省略了， 有興趣的讀者可以試著自己證明看看（他力本願）。
上面的子樹點數與子樹自行車數量總和都可以透過 DFS 線性計算，複雜度為 O(n)。
輸出 10 進位裡由 n0 個 0 與 n2 個 2 所組成第二大與第二小的 22 倍數。(可以有 leading zeros)
可以枚舉出全排列再找出第二小、第二大的數字。
全排列最多會有 $\binom{n_0 + n_2}{n_0} \le \binom{20}{10} = 184576$ 種。
考慮以下 DP 狀態
dp[p][x][y][m] = d
轉移式的話不考慮邊界非常簡略地可以寫成:
dp[p][x][y][m]
= 位置 p 放 0 的可能數 + 位置 p 放 2 的可能數
= dp[p+1][x-1][y][m] + dp[p+1][x][y-1][(m-2**(n-p)) % 11]
轉移為 O(1)，總排列數 C(60, 30) 大約是 1.18e+17 左右，用 int64 保存不會 overflow。
DP 表格算完後可以依著表格找出第 k 大的數字:
k - dp[p+1][x][y-1][(m-2**(n-p)) % 11] 大的數字找第 k 小的方法也類似，DP 為複雜度瓶頸，可以做 O(n3) 的 DP。
另外，由於 n-p = x+y，所以其實可以省掉一個維度。 DP 的複雜度可以變成 O(n2)。
和 subtask 2 可以用差不多的解法，但要注意兩個細節
關於數字太大的問題這裡提供兩個可能的解法
這裡雖然將過大的數字全部用 INF 表示，但並不影響上述找第 2 大，第 2 小解作法的正確性。
從這個子問題開始就是構造法為主的作法。
首先顯然 2 的倍數完全不需要考慮。 根據題目提示 11 倍數的性質，可以發現滿足題目所求的數字若且惟若: 「奇數位置2的個數 - 偶數位置2的個數 = 11倍數」。
因為 n2 為偶數，可以很簡單的求出最大的 11 倍數必定為: 22..200..0。 為了構造第二大，自然地會想考慮把某幾個右邊的 2 往右移。 經過嘗試後會發現這裡還可以分成兩個 case
注意到如果沒有 0 的話排列只有一種，因此不需要考慮第二大可以直接輸出 -1。
和最大的情況類似，首先找出最小的 11 倍數必定是 00…022…2。
這邊可以發現把從左邊數第 2 個 2 往左移兩格可以構造出第二小的數字。 例如 00002222 → 00022022
奇數會變複雜一點，因為條件的 「奇數位置2的個數 - 偶數位置2的個數」不可能為 0。 所以只好從 11 開始枚舉，首先求出最大的 11 倍數為:
22..2 202020202020202020202 0…0
中間的「202020202020202020202」是由 11 個 2 與 10 個 0 組出的交錯數列。 若 n2 < 11 或 n0 < 10 則連 11 的倍數都無法組出來為無解。 另外 n2 = 11 且 n0 = 10 的情況，因為只有一種 11 倍數的排列所以第二大也無解。
接下來想辦法構造第二大的數字， 這邊概念上和偶數的情況差不多但情況會變複雜， 為了讓數字越大越好，我們想移動最少個最右邊的 2。 可以找出下面幾個 case:
無解的條件和第二大一樣這邊就不重複說明了，首先先找出最小的 11 倍數:
00…0 202020202020202020202 22..2
第二小可以分成以下幾種情況
給定一 n*m 棋盤，輸出任意一個 Hamiltonian cycle 經過棋盤所有的格子。
限制是每次移動時，前一步與後一步不可以在同一列、行或者對角線上。
這題有幾種不同的解法可以拿到滿分， 下面會逐一介紹各種不同的滿分想法。
在這裡得先介紹一個定理 Ore’s theorem:
[定理]
對所有非鄰接的兩頂點 v, u 若滿足 deg v + deg u ≥ n， 則圖上必有 Hamiltonian cycle。
[構造]
將所有的頂點排成任意一個環狀序列:
v1, v2, …, vn
若序列中任意兩相鄰頂點 vi, vi+1 都互相有邊連接， 則代表找到一個 Hamiltonian cycle。
否則可以找到序列連續兩未連接的頂點 vi, vi+1。 並且往後再尋找另外兩頂點 vj, vj+1， 使得 vi vj+1，vi+1 vj 兩點對在原圖中有邊相鄰。
將環狀序列中 [vi+1, vj] 的部分反轉後， 環狀序列中有邊相連的連續點對個數至少 +1。 只要一直重複以上步驟就可以使得序列任意相鄰點都有邊相連，得到一個 Hamilton cycle。
[證明]
重點在於證明滿足條件的 vj vj+1 必定存在。 已知:
deg vi + deg vi+1 ≥ n。
不失一般性我們假設 deg vi ≥ deg vi+1。 也就是:
2deg vi ≥ n。
根據上面算法的步驟，已知 vi, vi+1 在圖上並不相連， 也就是說剩下的 n-2 個頂點裡面會有 deg vi 個與 vi 相連的頂點。
若所有與 vi 相連的頂點 vj 的右邊 vj+1 都與 vi+1 不相連的話， 則扣除 vi, vi+1 還至少要有 2deg vi ≥ n 個頂點。
這與只剩 n-2 個頂點的假設不符，由反證法得證。
回到原題，可以發現在 n, m 充分大的情況下幾乎都可以滿足 Ore’s theorem 所敘述的條件。 可以寫個簡單的小程式將 n≤m 所有不滿足 Ore’s theorem 條件的測資都爆搜出來:
n=2, m=any
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
4 4
4 5
4 6
4 7
4 8
5 3
5 5
5 6
5 7
6 6
6 7
除了 n=2 的情況以外點數都不多，因此可以分成以下的 case 處理:
在這裡僅提供一個範例討論所有的 case，假設 n ≤ m
如果在比賽中有勇氣嘗試搜索的話，可以發現在適當地剪枝後，大部分測資都可以跑得非常快。 對自己剪枝技巧沒信心的也可以加上建表來做輔助，相信應該可以拿到不少分數。
在接近完全圖的情況下，按照某些序列順序搜索其實有蠻高的機率在要求的時間找到所求的 Hamiltonian cycle。 利用這個特質可以寫出十分快的解答來搜索出所有答案。 詳細可以參考 spy_brute.cpp 的實作，在我們本機測試裡， 上面的時做大概可以在 1 分鐘左右算完所有滿足 nm ≤ 2000 的測資。