or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
random
產生亂數
產生亂數
亂數?很簡單啊,大一程式設計就有教
但真的好嗎?
在某些系統上 rand() 回傳範圍為 \([0, ?]\)
\(?\)為一個數值,根據library or 系統決定
解決方法:
以下會用 mt19937 實作隨機
在數學意義上並沒有真正的亂數,因此都只能用時間種子或者是怪怪的公式去假裝亂數
所以我們今天使用的是時間種子
那記得使用這個要引入標頭檔
這是一個單位以 ms 來計算的時間亂數
分析
首先 \(steady\_clock\) 是一個單調的時鐘
然後 \(now()\) 就是指現在的時間
接著 \(time\_since\_epoch()\) 是指 現在獲取的 \(now\) 到時間元年的間隔
最後 \(count()\) 當然就是指有幾個間隔
*時間元年 1970/01/01
再來是產生器,我們會使用到的是 mt19937
什麼是mt19937呢,背後支持的數學演算法是梅森旋轉算法,可以使得在一個範圍內有隨機分布。
那要怎麼產生呢?
所以我們的定義就會變成
那我們就可以開始利用mt了
那因為mt是我們的產生器,我們還需要給他一個分布的範圍
那他的預設值就是int 如果今天要用小數點的話就分別是以下
所以最後就會這樣寫出東西
Shuffle
random標頭檔下有shuffle函式
跟sort的用法一樣,直接把你的arr全部打亂。
算數學時間
簡單的練習
題目有 \(T\) 筆測資,每筆測資你的程式會有 \(p\) 的機率答對,並且你做了 \(k\) 次取最好的,請問你 AC 的機率是多少
題目有 \(T\) 筆測資,每筆測資你的程式會有 \(p\) 的機率答對,並且你做了 \(k\) 次取最好的,請問你 AC 的機率是多少
生日悖論
假設一年有 365 天,班上有 \(n\) 個人,有任兩個人生日相同的機率是多少?
Answer : \(1-\frac{P^{365}_n}{365^n}\)
hash 的成功率跟這個悖論有關,附上連結,有興趣可以看!
不一樣的 Hash
以前教過的hash
在字串課教過 rolling hash,可以讓你把一個字串的子字串壓成一個數字
\(h(s_1,s_2 . . . s_n) = (s_1 × C^{n−1} + s_2 × C^{n−2} + · · · + s_n)\) \(mod\) \(M\)
以前教過的hash
例題 : 矩陣相乘
給你 \(N*N\) 的矩陣 \(A,B,C\),問你 \(A \times B\) 是否等於 \(C\) ?
\(N \le 10000\)
暴力算矩陣乘法複雜度為 \(O(n^3)\),就目前已知的計算矩陣乘法複雜度一定炸開,因此可以考慮對矩陣去做 hash !
什麼!!!矩陣可以拿來hash!!?秉持 Hash 的精神,把矩陣 Hash 掉!
以前教過的 hash 可以把一個 「子字串」 or 「子區間」 hash 成一個數值,再去判斷兩者是不是一樣
如果這時候可以把矩陣 Hash 成「某個東西」的話,好像就很好判斷\(AB = C\) 了?
設 \(h\) 函數為可以把某矩陣 Hash 之後的變成某個東西的函數,所以要滿足:
\(h(AB) = h(C)\)
所以接下來要想個辦法算出 \(h(AB)\) 和 \(h(C)\)…
對於以前學過的子區間 Hash , 可以展開成以下 matrix 形式
設 \(R = \left[\begin{matrix} c_0 \\ c_1 \\ : \\ c_n\\ \end{matrix}\right]\),\(\left[\begin{matrix} a_0 & a_1 & ... & a_n\\ \end{matrix}\right] \times R = hash\) 值
子區間可以看成 \(1 \times N\) 的 matrix ,對於每一項,乘以他對應的 base ,而得到 \(1 \times 1\) 的 hash 值
那我們是不是也可以把一個矩陣 (\(N \times N\) 的matrix) 壓成更小的矩陣 (?)
因此考慮…
\(\left[\begin{matrix} a_{00} & a_{10} & ... & a_{n0}\\ a_{01} & a_{11} & ... & a_{n1}\\ : & : & ... & :\\ : & : & ... & :\\ a_{0n} & a_{1n} & ... & a_{nn}\\ \end{matrix}\right] \times R = \left[\begin{matrix} hash_0 \\ hash_1 \\ : \\ hash_n\\ \end{matrix}\right]\)
這樣做可以把一個 \(N \times N\)的矩陣 hash 成 \(N\times 1\) 的小矩陣了
因此問題變成 \((AB)R = CR\) ,交換一下矩陣計算順序
\(\rightarrow ABR = CR\)
\(\rightarrow A(BR) = CR\)
這樣計算的複雜度為 \(O(n^2)\)
前面好像都沒講到 \(R\) 矩陣裡面的數值具體要塞什麼?
先別急,再觀察一個性質
有這個性質可以幹嘛?
可以 random!!
讓 \(R\) 裡面所有的元素全部都是亂數生成的
考慮 \(AB \neq C\) 的情況,思考一下會發現,等號「成立」的情況機率很低,直接去算 \(A(BR)=CR\) 好像很大機率會過!
不對啊!等號「成立」怎麼辦 \(\rightarrow\) 多做幾次!!
多做幾次,讓WA的機率越乘越低,是 random 演算法的精神之一!
這裡我們學到了「二維Hash」,「生成隨機數把東西映射到其他東西(?)」的技巧,下面會再提更多 hash 的例子!
成雙成對
給妳一個長度為 \(n\) 的序列 \(a_1, a_2, ... ,a_n\),給你 \(q\) 筆詢問,每筆詢問給你 \([l,r]\)
問你 \([l,r]\) 區間內是否每一種數字都出現偶數次,
\(1 \le n,q \le 10^6\)
\(a_i \le 2^{31} -1\)
不可能 \(O(nq)\) 暴力去算,太白癡了
但我們好像學過根號算法?
複雜度 \(O(n \sqrt n)\),好像還是不會過
這時候就要用隨機來
唬爛了!透過觀察,會發現一個好的區間 \([l,r]\),滿足\(a_l\) \(\oplus ...\) \(\oplus\) \(a_r = 0\)
ex:
為什麼呢?因為相同的數字透過 Xor 的性質,兩兩互相打架抵銷成 0
但是也有情況 Xor 會爛掉
因此要避免這種情況發生,這時就要用到隨機ㄌ
可以選擇把每個元素透過隨機打到 long long 範圍的任意數字,
由於我們把值域範圍從 「\(2^{31}-1\)」 打到 「\(2^{64}-1\)」 左右,使碰撞的機率降低,在這樣的序列下去找好的區間,\(1\) \(\oplus\) \(2\) \(\oplus\) \(3 =0\) 的情況發生機率極低。
其實隨機就這樣,很唬爛,看起來超玄,但會過 :/
K的倍數
這時題目變成…
給妳一個長度為 \(n\) 的序列 \(a_1, a_2, ... ,a_n\),給你 \(q\) 筆詢問,每筆詢問給你 \([l,r]\)
問你 \([l,r]\) 區間內是否每一種數字都出現 \(K\) 的倍數次,
\(1 \le n,q \le 10^6\)
概念一樣,把所有元素打到任意一個隨機數,再去找好的區間
這時限制變成,每種數字都出現 \(K\) 的倍數次,怎麽做?
上一題當中,對於同一種元素,我們讓他兩兩打架,打到最後讓他消失不見
那可以讓他們\(k\)\(k\)打架(?) ,一樣讓他們打起來,有兩種方法:
顯然 1. 很好懂但很難實作,讓我們講講2.
用相加的,我們假設一個區間裡面有 \(k\) 個 \(a\),我們可以把 \((k-1)\) 個 \(a\) 打到 \(+x\),第 \(k\) 個 \(a\) 設定成 \((k-1) \times (-x)\) , 這樣可以使得這段區間的 \(a\) 相加為 0
因此可以這樣構造新的序列:
這樣就只要算區間和為零的子區間有多少就好了,因為是一個long long範圍的隨機數,所以「區間和為零但不是一個好的區間」的機率會非常小
休息一下~
讓你覺得「蛤?為什麼這樣做會AC」的例題們
眾數
絕對眾數的定義:數字出現次數嚴格超過長度的一半
題目 be like :
給你長度為 \(N\) 的序列,\(q\) 筆詢問
每次詢問給出區間 \([l,r]\) ,詢問裡面的區間絕對眾數是誰?
你會發現,在區間裡面戳一個數字,它會是區間絕對眾數的機率會有\(\frac 1 2\)
所以我們只要戳30次 這樣連戳30次都不是眾數的機率是 \({\frac 1 2}^{30}\)
那要怎麼確認一個數字是不是區間絕對眾數呢?
把每個數字的index記錄下來
然後使用二分搜去算它在此區間有幾個數字,就可以知道它是不是區間絕對眾數
因此複雜度是 \(O(30 Q log N)\)
變化題
給你一個長度為 \(n\) 的 arr ,求出一個 MOD 讓這個 arr 有絕對眾數
要取模誒 那他怎麼可能可以隨機?
還真可以。
因為在 MOD 完之後他會是絕對眾數,因此你任選一個數字,它取模完會是眾數的機率是 \(\frac 1 2\)
所以隨機挑選兩個數字,兩個都是眾數的機率是 \(\frac 1 4\) ,然後枚舉 \(|x-y|\) 的質因數 當成模數去計算即可。
分析
一次取到兩個都是眾數的機會是 \(\frac 1 4\) 也就是說不是的機率是 \(\frac 3 4\)
那我只需要 \({\frac 3 4}^T\) 就可以保證會是對的。
最近點對
給你平面上 \(N\) 個點,對於任意 \((i,j)\), 點 \(i\) 和點 \(j\) 的歐幾里德距離最小值是多少?
以前有教過分治的算法,一直分左邊分右邊然後blablabla…
但如果你有實作過的話,會發現最近點對分治超難寫,那我們試試隨機!
聽起來,我們這時想到的做法會是:
算算看複雜度
每個格子內最多只有 1 個點 => 最多只要檢查 25 個點
每次重畫格子要花 O(i) 的時間,不然加入只要花 O(1) 的時間(用 hash table)
這樣總時間需要考慮重畫格子、放進方格的機率,大約是
\(\sum\)加入第 \(i\) 個點花的時間 \(=\sum(p_i × O(i) + (1 − p_i) × O(1))\)
\(p_i\) = 第 \(i\) 個點要重畫格子的機率
但測資一定非常嚴格,一定會構造要你一直重畫格子的測資,因此會退化成 \(O(n^2)\)
但如果我們把點都 random_shuffle 呢?
既然現在 random 了,那複雜度一定會小於等於 \(O(n^2)\) ,接下來就來算算看 random 後重新畫方格的機率 \(p_i\)
其實重新畫方格的機率就是 \(O(\frac{1}{i})\),因此在shuffle之後複雜度會是:
\(\sum(p_i × O(i) + (1 − p_i) × O(1)) = O(n)\)
因此我們期望 \(O(n)\) 就可以做完了
一些細節
如果不信任 map 的話,也可以自己寫一個 hash練習題單
唬爛吧!