個人推薦書籍列表

封面	書名	簡介	評價
	原子習慣	本書介紹了習慣的強大力量，且提出了多個有別於傳統框架的習慣養成法	從早上起床到夜晚入睡，人類生活中很大部分的一切都受習慣所控制。我從沒想過，習慣竟然強大到是足以改變人的一生。以前我們總是被教導著，養成一個好習慣就是要靠強大的意志力，看完之後才知道，原來那些我們認為意志力很強大的人，往往是最少用到意志力的
	六分鐘日記的魔法	以正向心理學、習慣、自我反省等多種理論研究構成，一本通往快樂、更充實人生的日記	待補

Codeforces 918 Div 4 題解

為了慶祝第一次在 CF 破台所以難得來寫一下題解這成績我可以開心一個禮拜了 : ~~然後今天早上過的太廢一題都沒寫不知道是不是因為這樣把能量都留到這場釋放了~~給定三個數，其中兩個數相同，找到不同的那一個數直接照題意模擬做就行了，實作的部分用 map 很方便cppusing namespace std; int main { int t, tmp; cin t; while t-- { mapint, int cnt; 計算每個數字出現幾次 for int i = 1; i = 3; i++ { cin tmp; cnttmp++; } 找到出現次數為 1 的那個數 for auto num, frq : cnt { if frq == 1 cout num endl; } }}給予一個 3x3 的矩陣，每行、列都剛好包含各一個 A、B、C 字母，但某一格未知，任務是找到未知的那格是什麼直接照題意模擬做就行了，實作的部分用 set 很方便cppusing namespace std;char tb55; 檢查矩陣是否合法bool check { 檢查每個 row for int i = 0; i 3; i++ { setchar st; for int j = 0; j 3; j++ { st.inserttbij; } if st.size = 3 return false; } 檢查每個 column for int i = 0; i 3; i++ { setchar st; for int j = 0; j 3; j++ { st.inserttbji; } if st.size = 3 return false; } return true;}int main { int t; cin t; while t-- { int px, py; 未知格的座標 for int i = 0; i 3; i++ { for int j = 0; j 3; j++ { cin tbij; if tbij == '?' { px = i; py = j; } } } 枚舉該放哪個字母 for char c = 'A'; c = 'C'; c++ { tbpxpy = c; 如果合法就輸出 if check { cout c endl; } } }}有 n 個盒子，第 i 個盒子裝著 ai 個 1x1 的紙片，求是否可以剛好用所有的紙片拼成一個平片的正方形？事實上題目問的就只是 sum{i=1}^n ai 是否為完全平方數所以只需要加總後開根在平方看是否跟原始的數相等就行了cppusing namespace std;signed main { int t; cin t; while t-- { int n, tmp, sum = 0; cin n; for int i = 0; i n; i++ { cin tmp; sum += tmp; } if squareintsqrtsum == sum { cout "YES" endl; } else { cout "NO" endl; } }}有一種只包含 a、b、c、d、e 的語言，這些字母被分成兩種類型- Vowels — 包含字母 a 和 e，用 V 表示- Consonants — 包含字母 b、c、d，用 C 表示一個合法的段落可能為 CV 或 CVC 給予一串文字求將它按照規則分段的結果直接隨便取的話會出一些問題不過其實只需要觀察到兩個 C 不能連再一起就完事了雖然我也還沒完整的證過因為我不是數學家cppusing namespace std; 儲存每個字母是 v 或 c 類mapchar, char tb = { {'a', 'v'}, {'b', 'c'}, {'c', 'c'}, {'d', 'c'}, {'e', 'v'},};void sol { int n; string s; 題目給的字串 string ss; 轉換過後只包含 c 跟 v 的字串 cin n s; 轉換字串 for auto c : s ss += tbc; 分段後的結果 vectorstring ans; for int i = 0; i s.size; { if i == s.size - 3 { 只剩下最後三個字就直接全取 ans.pushbacks.substri, 3; break; } if ssi+3 == ssi+2 ssi+2 == 'c' { 如果選 CV 會導致兩個連續 C 的情況出現就改選 CVC ans.pushbacks.substri, 3; i = i + 3; } else { 否則就選 CV ans.pushbacks.substri, 2; i = i + 2; } } 輸出解 for int i = 0; i ans.size; i++ { if i = 0 cout "."; cout ansi; } cout endl;} int main { int t; cin t; while t-- sol;}給定一個陣列，求是否存在一段連續的區間滿足偶數 index 的所有元素加起來等於奇數 index 的元素把偶數 index 的元素都加上負號再套上前綴和之後題目就被轉換成找到一個區間滿足總和為 0也就是說只要從左掃到右並對於每個位置檢查左邊是否存在相同值的元素即可cppusing namespace std; void sol { int n; cin n; vectorint an; for int i = 0; i n; i++ { cin ai; if i % 2 == 0 ai = -1; } vectorint psumn + 1; partialsuma.begin, a.end, psum.begin + 1; setint st; for auto e : psum { if st.finde = st.end { cout "YES" endl; return; } st.inserte; } cout "NO" endl;} signed main { int t; cin t; while t-- sol;}有 n 個人在數線上以每秒 1 格的速度往右走，第 i 個人的起點為 ai 終點為 bi，求他們倆倆碰面（同時出現在同一格）的次數仔細觀察之後會發現只有 ai aj 且 bi bj 的情況下 i 跟 j 才會碰面也就是一個區間把另外一個區間包住的情況可以發現其實就跟 CSES 的 Nested Ranges Count 完全一樣那這題網路上題解很多算法細節就不多提了cppusing namespace std;using namespace gnupbds;template class T using orderedset = treeT, nulltype, lessT, rbtreetag, treeorderstatisticsnodeupdate;void sol { int n; cin n; vectorint beconn, yidxn; vectortupleint, int, int bn, cn; for int i = 0; i n; ++i { int l, r; cin l r; bi = {l, r -1, i}; ci = {r, l -1, i}; } sortb.begin, b.end; sortc.begin, c.end; for int i = 0; i n; ++i yidxget2bi = i; orderedsetint s; for int i = 0; i n; ++i { int idx = get2ci; int cur = yidxidx; beconidx = s.size - s.orderofkeycur; s.insertcur; } int ans = 0; for int i = 0; i n; ++i ans += beconi; cout ans endl;} signed main { io; int t; cin t; while t-- sol;}給一張無向帶權圖，第 i 條邊連接著 vi 及 ui 且權重為 wi，你可以在節點 i 拿到一台速度為 si 的腳踏車，騎著速度為 si 的腳踏車經過第 j 條邊時需要花費 si times wj，求全程騎腳踏車從 1 走到 n 的最少時間花費不難想到從點 v 獲得腳踏車後到其他每個點 u 的最少時間花費為 distv, u sv 其中 dist 代表兩點最短路徑長度那其實就只要依照上面的規則把那些邊都建在新的圖上最後對新的圖做最短路就可以了補充資料: 最短路演算法cppusing namespace std;const int maxn = 1e3 + 10;const int inf = 1e13; int n, m;vectorpii gmaxn;int bikemaxn; vectorpii g2maxn;int dist2maxnmaxn; int distmaxn; void sol { 初始化讀取輸入 cin n m; for int i = 0; i = n; i++ { for int j = 0; j = n; j++ { dist2ij = inf; } } for int i = 0; i = n; i++ { gi.clear; g2i.clear; } for int i = 0; i m; i++ { int a, b, w; cin a b w; ga.pushback{b, w}; gb.pushback{a, w}; } for int i = 1; i = n; i++ { cin bikei; } 在原始的圖上求每個點對得最短路 for int v = 1; v = n; v++ { 初始化 for int i = 1; i = n; i++ { disti = inf; } 使用 dijkstra 演算法 priorityqueuepii, vectorpii, greaterpii pq; pq.push{0, v}; distv = 0; while pq.size { auto now = pq.top; pq.pop; if now.ff distnow.ss continue; for auto other : gnow.ss { if distother.ff distnow.ss + other.ss { distother.ff = distnow.ss + other.ss; pq.push{distother.ff, other.ff}; } } } 建邊在新的圖上 for int i = 1; i = n; i++ { if i == v continue; g2v.pushback{i, disti bikev}; } } 初始化準備在新的圖上做最短路 for int i = 1; i = n; i++ { disti = inf; } 使用 dijkstra 演算法 priorityqueuepii, vectorpii, greaterpii pq; pq.push{0, 1}; dist1 = 0; while pq.size { auto now = pq.top; pq.pop; if now.ff distnow.ss continue; for auto other : g2now.ss { if distother.ff distnow.ss + other.ss { distother.ff = distnow.ss + other.ss; pq.push{distother.ff, other.ff}; } } } 輸出解 cout distn endl;} signed main { int t; cin t; while t-- sol;}

Codeforces

題解 CSES Common Divisors

找到兩個數字使得兩數的最大公因數盡量大可以把題目想成找到最大的 x 使得陣列中出現至少兩個他的倍數於是我們可以先用 cnt 陣列紀錄每個數字的出現次數然後枚舉每個可能的因數假設目前枚舉到 k 從 k、2k、3k dots 計算陣列中存在多少個倍數根據調和級數.harmonic-series可以算出時間複雜度為 On log ncppconst int maxn = 1e6 + 10;int cntmaxn;signed main { int n; cin n; vectorint vn; for int i = 0; i n; i++ { cin vi; cntvi++; } for int k = maxn; k 0; k-- { int cur = 0; for int j = k; j maxn; j += k { cur += cntj; } if cur = 2 { cout k endl; return 0; } }}

CSES

題解 CSES Sum of Divisors

定義 sigmax 為 x 的所有因數之和給予一個 n 求 sum^n{k=1}sigmak 之值以 12 為例先看一下這張圖列出了 1 sim 12 的所有因數可以發現每兩個數字就會出現一次 2 每三次數字就會出現一次 3 觀察後可知對於一個數字 x 它的出現次數會是 lfloor frac{n}{x} rfloor 因為每 x 個數字就會出現一個 x 的倍數用這個做法枚舉每個數字計算就可以得到一個 On 的算法但這樣還不夠快到足以處理這題 10^{12} 的資料量如果我們把剛剛那張圖的呈現方式改一下上面那一橫排代表因數 1 sim 12 下面那一行排代表該因數出現的次數可以發現這張圖內有幾串連續的因數出現次數相同因為事實上在計算這個的過程中只會出現最多 2 sqrt n 個相異數字證明上面那張圖每個紅色圈起來代表一塊如果我們可以塊為單位來計算就可以把時間複雜度降到 Osqrt{n} 了想像一下如果 n 除以 x 可以剛好整除的話令 k = lfloor frac{n}{x} rfloor 則 lfloor frac{n}{k} rfloor 必定等於 k 那如果不是剛好整除的呢？ lfloor frac{12}{5} rfloor = 2 ,quadlfloor frac{12}{2} rfloor = 6 再試試看 6 lfloor frac{12}{6} rfloor = 2 ,quadlfloor frac{12}{2} rfloor = 6 觀察後發現這裡的 6 就是最大的 x 滿足 frac{n}{x} 為 2 於是這樣我們就可以找到最後一個連續出現次數相同的因數最後只要把每次一塊的第一個數和最後一個數用梯形公式求總和乘上共同的出現次數就可以得到答案了不過這邊要注意的是因為答案很大所以題目要我們對 10^9 + 7 取模但梯形公式中又會用到除法所以我們不能直接除需要先求出模反元素.modulo-inverse再乘進去才行cppusing namespace std;const int mod = 1e9 + 7;const int inv = 500000004; signed main { int n; cin n; int cur = 1; int ans = 0; while cur = n { int cnt = n cur; int last = n cnt; int sum = last + cur % mod last - cur + 1 % mod % mod inv % mod; ans += sum % mod cnt % mod % mod; cur = last + 1; } cout ans % mod endl;}

CSES

推薦文章

Codeforces 918 Div 4 題解

題解 CSES Common Divisors

題解 CSES Sum of Divisors