LFsWang's World

Planetarian ～ちいさなほしのゆめ～ 中譯：星之夢 遊戲 2004 年發行 Steam 可購得高畫質重製版 TV 版全 5 集已完結 電影版 星之人 1 集 (內容包含 TV 版全部內容，以及後傳) OVA 雪圈球 1 集 (夢美前傳) 在考日檢前不務正業的用 galgame 練日文閱讀。而我選的是 Planetarian 星之夢。星之夢長度相當短的電子小說，整體沒有選擇枝的單線劇情。一於是透過 Key 社大禮包購入的，裡面有兩個版本的星之夢，以下截圖都是舊版星之夢的 CG，不是 HD 版本的 (HD Steam 版本有中文沒日文，DL 版的才有日文)。 .hidtext { background: black; color: black; } .hidtext:hover { background: white; color: black; } 劇情紀錄 敬請搭配遊戲中解說星空的主題曲 - Gentle Jena 故事劇情描述了無名的主角 - 廢墟獵人 在因戰爭而廢棄的城市中，偶然踏入廢棄百貨公司，邂逅了機器人 - 星野夢美的故事。 ...

題目大意 寫一個資料結構， 支援插入資料以及求第 k 大。 題解 看其他人提解，這一題可以暴力 O(n2) 水過去，不過複雜度看起來不正確就是了。 如果不想寫平衡樹，可以直接用黑魔法平衡樹 (pbds tree)，有內建 find_by_order 求第 k 大，可以穩定 O(nlog⁡n) 解出來。 AC Code 風ふう子こちゃんがかわいい。 1234567891011121314151617181920212223242526272829#include <bits/stdc++.h>using namespace std;using ll = long long;#include <ext/pb_ds/assoc_container.hpp>using namespace __gnu_pbds;using pii = pair<int, int>;tree<pii, null_type, greater<pii>, rb_tree_tag, tree_order_statistics_node_update> hito ...

題目大意 判定一個數字的因數總和與本身的大小關係。 題解 如果能快速獲得一個數字的質因數分解，就能使用高中課本公式計算一個數字的因數總和。由於一個數字的質因數很少，因此本題的關鍵在於如何做質因數分解。 考量到雖然輸入範圍是 1012 量級，但側資比數比較少，約 1000 筆，因此這裡使用了較簡單的建表法來處理。使用建表法的話，能夠在 O(π(N))∈O(nln⁡n) 計算完畢，剛好能壓線過這一題。 如果使用 Pollard’s Rho Algorithm 拆解可以進一步的加速到期望 O(N4)，但程式碼長度會變得很攏長，有興趣的話再寫一篇吧。 AC Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include <bits/stdc++.h>using namespace std;using ll = long long;int mai ...

題目大意 給定一個度序列，問這個度序列是否能構成一張簡單圖？ 題解 這一題與 1210. 圖論 之 簡單圖測試 其實差不多，但是要求的 n 更大了，因此需要實作線性演算法。 這裡使用 Erdős–Gallai theorem 來完成。 Erdős–Gallai theorem 若度序列 d:d1≥d2≥…dn 是圖序列 ⟺ ∑d 是偶數，且對於 1≤k≤n 都有 ∑i=1kdi≤k(k−1)+∑j=k+1nmin{k,dj} 簡單來說，就是把 k=1∼n 都帶入公式即可。但如果每一次都要重算，會需要 O(n2) 的時間，因此這裡把等式左右邊的數值都好好的保存下來並維護。 左半邊的部分比較簡單。右半邊的部分，如果大於 k，就只加上 k。因此我們先使用 Counting sort 把資料由大到小排序後，再認真的紀錄可以直接加起來的區間。由於度序列合法的值域為 0∼n−1，因此排序的步驟是 O(n) 的。 這一個加總區間的變化較特別，一開始會向右擴張，再隨著 k 變大，又會逐漸地向左收縮。由於每一個數字只會被加入或移除一次，因此區間的維護成本是平攤 O(1) 的，總時間複雜度就能控制在 ...

題目大意 輸入時間後加總排序。兩題差不多就放一起了。 題解 不正確的教學文件真的誤人一生，很多 C++ 基礎教學都沒有很認真地介紹 cin 的細節處理，遇到特殊格式，比如說本題的時間 hh:mm 就要繞一圈做。殊不知其實單純的 cin 就能正確處理了，不需要改寫成 C 語言的 scanf("%d:%d")，用 cin >> i >> ch >> j即可處理，非常直觀！ 真應該認真寫一篇 C++ 輸入截斷規則的教學才對。 AC Code 123456789101112131415161718192021222324252627#include <bits/stdc++.h>using namespace std;using ll = long long;int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, M; while (cin >> N >> M) { vector&l ...

25214abb9717465e5711e13016eaf07c208f29667d98ec38b18c4f43e24c40b78e3a33f860b27f368af797be4d488896bef07c9103305ab22267176e8f675ec658fd661bafd8b8bd6d359cea21b0342b50e7a552c587801601c670e434fe0568ff8677125221a1a10d6063f10a9e06819a310bee563ff176f0eb65579fe2fe7351c99be02c28ca037ab457f51edcec05af8f03bfb7ad916b960697c9ee3f1587940438804500b26d0c926c02598bda65b1949553d4b5ba1feeef897fdb1afa35717d7600f4791af3814d179eed135cf11c48ca86dee504a37869a4d85355293574eaa627194d6c9ae02d09f32de1f839fc142c06bfcba8e2e ...

題目大意 計算 3xmod10007 題解 使用歐拉降冪公式 ak≡{akk<φ(n)ak%φ(n)+φ(n)k≥φ(n)對 x 取 φ(10007)=10006 的餘數即可。 AC Code 12345678910111213141516171819202122#include <bits/stdc++.h>using namespace std;using ll = long long;int main() { ios::sync_with_stdio(false); cin.tie(0); const ll mod = 10007; const ll phi = mod - 1; // 10007 is prime ll pw[2 * phi] = {1, 0}; for (int i = 1; i < 2 * phi; ++i) pw[i] = 3 * pw[i - 1] % mod; int x; while (cin >> x) { ...

題目大意 實作 heap，並輸出 level order 題解 能懶就懶。 C++ 有 heap 實作的函數可以用，可以不用自己寫。 push_heap 的用法是，先把元素放到陣列的最後面，再呼叫此函數即可。 由於 heap 是一個完全二元樹 (Complete Binary Tree)，因此該資料結構的 level order 就是由陣列順序直接輸出即可。 AC Code 123456789101112131415161718192021222324252627#include <bits/stdc++.h>using namespace std;using ll = long long;int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, x; vector<int> v; while (cin >> N) { vector<int> mhp, Mhp; while (N--) { ...

在實作一些演算法，如 Miller-Rabin 時，會出現 long long 整數相乘再取餘數的步驟。 12long long a, b, c;auto res = a * b % c; 然而若 a*b 的結果大於 long long 的表達範圍的話會溢位，便無法取得正確的結果。因此會需要自行實做乘法來避免溢位。具體方法可以參考維基百科，簡單來說就是模擬直式乘法：如果每次最多乘以 2，那麼一個 63 bit 的整數可以在 64 bit 的空間內計算出來不會發生溢位。因此實作上用 uint64_t 來儲存即可。 不過絕大多數的 OJ 與競賽編譯器都使用 GCC，而 GCC 帶有非標準的 128 bit 整數 __int128 🔗，如果環境允許使用的話，那麼就只需要把 long long轉型到__int128運算即可。 很久以前有人說__int128運算上很慢，因此似乎讓後者的實做不是特別的流行。既然最近剛好寫到了一題，就來做個實驗。 就直白說結論了：__int128 比自行用迴圈實作乘法快了 30~50 倍 (O3 優化)。 因此如果環境許可的話，就用 __int128 ，程式碼既簡 ...

A. 威廉伯爵的農場 題目大意 給平面座標的三個點，問圍成的三角形面積乘以一個常數 c，所有數字都是 int 範圍的整數，c 是 2 的倍數，保證答案可以用 long long 表示 題解 Keys : 向量運算 數值處理 高中數學有提到，兩向量 a→、b→，圍成的平行四邊形面積是 |a→×b→|，所以這一題的答案就是 12×c×|a→×b→|，其中 |a→×b→|=|xayb−yaxb|，此外要注意除以 2 的次序避免溢位的問題。 B. ⼤樓彩繪 題目大意 有 m 角柱，角柱的側邊每個面都有 n×n 的網格，每個網格有 c 種顏色可以選擇，問有幾種著色方法 題解 Keys : 排列組合 Burnside’s lemma 快速冪 一個很顯然的事情是一個面有 cn2 種不同的塗法，這個數字姑且稱為 p ，那如何計算有多少的塗法呢？ 如果知道 Burnside’s lemma 的話就有 1m∑i=1mpgcd(m,i)C. 金坷垃運輸網 題目大意 給一張無向圖，問 a、b 兩點之間是否存在兩個獨立的路徑，即如果任意地把圖中的一條邊移除， a、b 依舊連通 題解 Keys : Ta ...