LFsWang's World

最近又燃起了都是探險的動力，於是利用下午的空檔，來挑戰這一個新竹算是難到的一個景點，新竹風空老樟樹與土地公廟。 新竹風空位在科學園區東南方，至高鐵高架橋之間，這裡有一座土地公廟，後方有一棵被認定為全市最老的老樟樹，原本該處位於高鐵預定路線上要被砍除，但後來高鐵公司為此微幅調整高鐵路線避開此處，也為此拍了一支廣告宣傳。詳細的細節可參閱維基百科 風空開山伯公 前陣子也看到 Tony 也曾來訪過，想說自己也來探勘一下路線。 直接說結論的話，目前不建議使用徒步或騎單車以外的方法前往，北面比較便利寬敞的路線目前因高鐵橋下道路的工程，目前挖了應該是未來水溝的橫向壕溝，道路受阻，機汽車無法通行，腳踏車可以扛車通過。如果工程完成的會建議由此通行。南面則是路狹與路面破損，要小心通行。 最後就附上目前現場的照片吧。 ...

今年清華大學的資工系的傳統「兩岸清華交流賽」在疫情後正式恢復為實體舉辦了。據北京的老師表示今年正好是這活動的第 25 年。蠻有幸的我自 2016 年第一次以選手參加這場交流，到現在已經是以教練身分隨隊出席。 今年輪到北京清華來主辦，同學一行人凌晨便搭著系辦定的車輛前往機場搭乘 7 點 40 的飛機。飛機在接近北京時氣流相當的不穩定，看新聞 10 號也有中國國內航班因往北京的亂流而導致機組員受傷的事故。抵達至北京時，外頭正一片大雨。具導遊的說法，這是北京乾旱以來，這兩個月的第二場雨。 第一天基本上由於大家前天幾乎都沒睡好，所以北京的同學帶我們回飯店吃午餐後後，大家就回房間睡了，等著晚上與香港的同學會合吃飯店一旁的食平方烤鴨店。 第二天再交送完系辦要贈與給北京與香港兩校的禮品後，教練一行人便被帶到另一間教室觀賽。當然程式設計競賽的可看度不是很高，因此基本上就是用筆電連回台灣做工作，然後在稍微盯一下賽場的變化。北京命題時似乎不會放較簡易的題目，因此大多數隊伍都在比賽過了 1...

今天下午查看了一下湖口有設立 UBike 了，讓原本從湖口車站到湖口老街的路途有了稍便捷的方案，於是就搭火車前往了。之前之所以沒去湖口老街，就是因為大眾運輸不便，至少往返火車站到老街的公車不多，今天實地前往，也發現確實沒什麼人利用公車，大多是自駕前往，部分人則選擇使用 UBike。 湖口車站門口的 UBike 站點常態性的沒車，可以步行到附近的新竹縣湖口鄉公所借，中間會經過湖口市場，下午也是頗有人潮可以逛逛。 從火車站到老街幾乎是一直線的緩上坡，沒什麼車，但也沒什麼建築物，如果遇到颳風日應該稱不上能優閒地騎乘。到達老湖口天主堂後，取左邊的單行道前往停車場，一路騎進去到接近廟口的地方， Ubike 站點位於公廁旁。可以發現原本的機車考照練習區已經蓋起建築物了，只剩下地上的油漆痕跡。 往停車場路上有一座通過國道一號的涵洞，非常多人，查了一下健行筆記，後方有仁和步道/金獅步道，約 2KM 的路程，而且正值賞花季節，但到達時間已偏晚，且騎腳踏車有點累，或許就下次再專門前來。 整個老街基本上算是熱鬧，但又不壅擠，逛起來相當愜意，如果把行程修正一下，改成搭 14:20...

入手了 Steam Deck ，稍微把一些稍微需要點步驟才能玩的遊戲紀錄一下 符號表示 狀態 用來表示初步的遊戲執行概況，標準為是否可以啟動、執行並從頭開始完成約 3 分鐘的遊戲。默認環境語系是繁體中文。可參考此文章 安裝繁體中文環境。 有些遊戲個人也還沒開始認真玩，所以不能保證全部的內容都是能玩的，就只是確定能有個開始畫面。 符號 意義 :white_check_mark: 在 Steam 上可以直接下載 / 加入遊戲庫後，無須參數，可以直接啟動遊玩 :eight_spoked_asterisk: 須經過簡易步驟調整後，可以正常遊玩 :bell: 部分功能不正常，但仍可操作遊玩 :x: 動不了，或是能啟動但功能不正常，無法遊玩 :question: 尚未測試 Steam 商店可購入 ( 基本上可以到 ProtonDB 查詢其他玩家如何開啟的 ) 遊戲中文名稱 遊戲原文名稱 狀態 備註 G弦上的魔王 G線上の魔王 :bell: 可以使用討論區的 V4 (附R18)...

看完 Clannad 後，意外的喜歡 After Story 第 22 集的插曲：少女の幻想。這首歌有非常空靈的感覺。 查了一下歌詞之後，意外的發現在原來的專輯內並未紀載，這首 少女の幻想 僅有記載標題，因此這首歌的歌詞僅能靠聽力判讀。網路上流傳的歌詞版本有兩種： 日本網友 makura 聽寫版 : http://www.i-love-key.net/archives/2007/01/post_77.html PTT 網友 aozakisora 修正版 : https://www.ptt.cc/bbs/LeafKey/M.1237813961.A.9C2.html 關鍵上只有第三句話理解不一樣。網路上目前的歌詞記載以 makura 版的為主。而根據 aozakisora 的內文來看，makura 版的歌詞有些錯誤，因有做了一些修正。正想幫萌娘百科補上假名時，意外的發現 makura...

題目大意 寫一個資料結構， 支援插入資料以及求第 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>...

題目大意 判定一個數字的因數總和與本身的大小關係。 題解 如果能快速獲得一個數字的質因數分解，就能使用高中課本公式計算一個數字的因數總和。由於一個數字的質因數很少，因此本題的關鍵在於如何做質因數分解。 考量到雖然輸入範圍是 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...

題目大意 給定一個度序列，問這個度序列是否能構成一張簡單圖？ 題解 這一題與 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) { ...

...