douobb

大概刷了 50 題左右 GPE Helper 上面比較常出現的題目，根據題目類型分類做一些筆記，方便之後複習。 DFS&BFS Problem UVA 11006 Rank the Languages 10336 22171 Dungeon Master 532 Tree&Graph Problem UVA 2009-17 Binary tree traversals 10038 Disk Tree 1556 10602 Longest Paths 10000 24731 Roads in the North 10308 DFS & BFS Rank the Languages UVA 10336 題目大意 給定一張地圖，上面標有小寫英文字母，字母 k 的區域代表裡面所有的字母皆為字母 k，要求計算每個字母所有的區域數量，並且將他們排序。 解題方法 每次使用 DFS 尋找相鄰的相同字母，並將其標示為其他字元 (題目中不會使用到的) 代表已經處理過，使用 vector 來儲存每個字母的區域數量，最後用自訂的 c ...

大概刷了 50 題左右 GPE Helper 上面比較常出現的題目，根據題目類型分類做一些筆記，方便之後複習。 字串處理 Problem UVA 24941 Uncompress 245 11041 Children’s Game 10905 10582 Power Strings 10298 動態規劃 Problem UVA 23681 Bachet’s Game 10404 22181 Dollars 147 2008-28 Longest monotonically increasing subsequence 10621 Luggage 10664 23651 The jackpot 10684 字串處理 Uncompress UVA 245 題目大意 介紹了一種文本壓縮的方式，每次遇到重新單字時，將其移入一個 list 的最前方，如果遇到已經出現過的單字，則以其在 list 中的位置來代替該單字，並且將其在 list 中再次移到最前方。現在給定一段壓縮文本，要求將其復原。 解題方法 用 getlin ...

紀錄一些關於 hexo 的小事。 數學公式 最近發現文章中的數學公式看起來怪怪的，後面都會重複一次原本的文字，後來調整了一些 MathJax 的設定之後就正常了。 參考資料： Butterfly 文檔(三) 主題配置 在終端機中輸入以下指令，卸載 hexo 的 markdown 渲染器，並且安裝 hexo-renderer-kramed： 12npm uninstall hexo-renderer-marked --savenpm install hexo-renderer-kramed --save 在 _config.yml 中加入以下代碼： 12345678kramed: gfm: true pedantic: false sanitize: false tables: true breaks: true smartLists: true smartypants: true 在 _config.butterfly.yml 中加入以下代碼： 1234# MathJaxmathjax: enable: true per_page: true 分類相關 ...

字典樹 (Trie) 是一種樹狀結構，可以用來儲存 字串 或是 層狀資料夾 類型的資料，每個節點分別可以儲存一個字元或是資料夾名稱，並且可以進行插入、查詢等操作。 儲存字串 結構 node 中包含了儲存的字元、後續字元的位置、以及目前位置是否是一個字串的結尾，如果能夠確定後續字元的種類的話 (如 ‘a’ ~ ‘z’)，也可以使用一般的陣列來儲存。 1234567891011121314151617struct node{ char ch; //字元 unordered_map<char, int> nextNode; //後續字元位置 bool wordEnd; //是否為字串結尾 node(){ nextNode.clear(); wordEnd = false; } node(char c){ ch = c; nextNode.clear(); wordEnd = false; }};vector&l ...

把原本複雜的問題分解為相對簡單的子問題，通常適用於有重疊子問題的情況，可以透過儲存子問題的答案減少之後處理複雜問題的時間。 Rod Cutting Problem 有一根長度為 L 的棒子，以及價格表 v[i] 代表 長度為 i 的棒子的價值，找出一種切割方案，使得切割後的棒子價值總和最大。 建立一個 vector 來儲存長度為 i 的棒子切割後的最大總價值。 1234567891011int rodCutting(int L, vector<int> v){ vector<int> dp(L + 1, 0); for(int i = 1; i <= n; i++){ int m = 0; for(int j = 1; j <= i; j++){ m = max(m, v[j] + dp[i - j]); } dp[i] = m; } return dp[L];} 陣列的更新是由較短的長度開始 ...

L15 社會心理學 人的思考和行為如何受到與別人互動的過程所影響。 Social Roles (社會角色) - 一個人在社會中的地位，期望他有哪些行為。 史丹佛監獄實驗 - 監獄中權威者和被監管者行為影響。 Social Cognition 社會認知 Attribution (歸因) - 是什麼導致了某人的這種行為? Internal (dispositional) - 內部的性格 External (situational) - 外在的情境 歸因時的偏誤： Fundamental attribution error - 低估了外在環境對於行為的影響。 ex:她現在很生氣，所以她一定是個脾氣暴躁的人。 Actor-observer bias - 傾向於將他人的行為歸因於內在因素，將自己的行為歸因於外在因素。 Self-fulfilling prophecies (自我實現預言) - 偏誤可能會形成事實。 老師被告知某一群學生是"黑馬" (事實上隨機抽出的學生)。 在學年度的最後，這些"黑馬"在 IQ 分數上多了 22 分，顯著高 ...

L14 心理治療 Psychodynamic approach 心理動力學方法 進行 Psychoanalysis (精神分析)，目標： 增強自我, 讓本我, 自我和超我達到平衡 協助病人幫潛意識的思想帶到意識上 方法： free association - 讓患者在放鬆的情境下交談。 Resistance - 當患者抗拒討論某個話題時，可能就是問題的線索。 dream analysis - 淺意識可能會在夢中顯露出來 (進行夢的解析)。 Transference & Countertransference Transference 移情作用 - 當事人(患者)將對 A 的情感投射至 B (治療師)身上。 Countertransference 反移情作用 - 治療師將對 A 的情感投射至 B (患者)身上。 Behavior approach 行為方法 利用古典制約 (classical conditioning)： Exposure therapy (暴露治療) - Systematic desensitization (系統脫敏) 放鬆肌肉 -> ...

L13 心理異常 任何的行為都可以看成一個連續尺度，每個人都會感傷，焦慮或是感到壓力 (負面情緒有演化上的功用)。 當這些負面情緒影響你的正常生活時，才算是異常： 我很焦慮所以我無法離家去工作。 我很沮喪所以我無法睡得好。 客觀化 (objectify) 所會遇到的問題： 同一個行為，在某情境下正常，但換了一個情境變成異常。 誠實是個正常行為，但在某些情況下誠實會變得白目。 因此我們會在連續的尺度上劃定界線，超過了界線就算是異常，目前的標準為 DSM-5 (Diagnostic and Statistical Manual of Mental Disorder)。 Psychotic Disorders 精神障礙 精神病 特徵：Delusions (妄想)、Hallucinations (幻覺)。 妄想：個人堅持錯誤的信念。 幻覺：想像出來的感覺。 神經認知障礙 阿茲海默症 Delusional disorder (妄想症) Erotomanic type (情慾型) - 認為自己被另一個人所愛。 Grandiose type (誇大型) - 認為自己有某 ...

L12 人格 The trait approach Trait 特徵 - 人在不同環境中一致性的特質。 Five-factor model 從英文形容詞中的同義字整理在一起 (200個字)。 建立出兩極 (kind vs cruel)。 給一群人施測並統計分析，相關高的形容詞擺在一起。 建立出五個 factors (O-C-E-A-N)。 預設人的性格是靜態不變的。 缺點：無法解釋行為怎麼產生。 Psychodynamic theories Freudian Psychoanalysis 佛洛伊德精神分析 所有行為都有背後成因。 沒有隨機的行為。 兩種基本驅力 (drives) Self preservation - 饑餓或口渴。 Eros - 性欲望 (試圖跟別人有生體接觸的欲望)。 Fixation - 在某個階段中太過滿足或是太過挫折。 Freudian slip (弗洛伊德式錯誤) - 潛意識的衝動會自己尋找出口。 筆誤、口誤。 動機性遺忘、童年回憶遺忘。 對於潛意識的描述。 缺點： 概念缺乏明確的操作型定義。 不能被否證。 ...

L11 情緒 八種主要情緒 (Robert Plutchik)： Fear Surprise Sadness Disgust Anger Anticipation Joy Trust (acceptance) 情緒與生理 Autonomic nervous system 自主神經系統 The sympathetic division 交感神經 - 危險情況 The parasympathetic division 副交感神經 - 放鬆 Central nervous system 中央神經系統 Hypothalamus 下視丘。 Amygdala 杏仁核 - threat detector：可以意識到危險。 測謊儀 記錄心率、血壓、呼吸和皮膚電阻變化的設備。 主要是測量說謊時交感神經活躍導致的結果，而不是說謊的本身，僅能做為參考。 Guilty Knowledge Test (改良版的測謊方式) 提出一系列多項選擇題，只一個答案是正確的，只有有罪的人才能知道答案，犯人可能會對該選項產生較強的反應。 情緒來源 情緒的來源： James-Lange ...