random
- 要怎麼random(產生亂數)
- hash
- 更多 random 題目
產生亂數
產生亂數
亂數？很簡單啊，大一程式設計就有教
rand();
srand(seed);
但真的好嗎？
在某些系統上 rand() 回傳範圍為 \([0, ?]\)
\(?\)為一個數值，根據library or 系統決定
解決方法：
- rand()拼成很多次很大的數字
- 用 mt19937 :D
以下會用 mt19937 實作隨機
在數學意義上並沒有真正的亂數，因此都只能用時間種子或者是怪怪的公式去假裝亂數
所以我們今天使用的是時間種子
chrono::steady_clock::now().time_since_epoch().count()
那記得使用這個要引入標頭檔
#include<chrono>
這是一個單位以 ms 來計算的時間亂數
分析
chrono::steady_clock::now().time_since_epoch().count()
首先 \(steady\_clock\) 是一個單調的時鐘
然後 \(now()\) 就是指現在的時間
接著 \(time\_since\_epoch()\) 是指 現在獲取的 \(now\) 到時間元年的間隔
最後 \(count()\) 當然就是指有幾個間隔
*時間元年 1970/01/01
再來是產生器，我們會使用到的是 mt19937
什麼是mt19937呢，背後支持的數學演算法是梅森旋轉算法，可以使得在一個範圍內有隨機分布。
那要怎麼產生呢?
mt19937 變數名稱(亂數種子);
所以我們的定義就會變成
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
那我們就可以開始利用mt了
那因為mt是我們的產生器，我們還需要給他一個分布的範圍
uniform_int_distribution<> dis(0, 1e9);
那他的預設值就是int 如果今天要用小數點的話就分別是以下
uniform_int_distribution<int> 分布變數名稱(最小值, 最大值);
uniform_real_distribution<double> 分布變數名稱(最小值, 最大值);
所以最後就會這樣寫出東西
#include<iostream>
#include<random>
#include<chrono>
using namespace std;
void solve(){
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<> dis(0, 1e9);
cout<<dis(mt)<<endl;
}
int main(){
solve();
return 0;
}
Shuffle
random標頭檔下有shuffle函式
shuffle(arr,arr+n,mt);//開頭,結尾,亂數產生器
跟sort的用法一樣，直接把你的arr全部打亂。
算數學時間
簡單的練習
題目有 \(T\) 筆測資，每筆測資你的程式會有 \(p\) 的機率答對，並且你做了 \(k\) 次取最好的，請問你 AC 的機率是多少
題目有 \(T\) 筆測資，每筆測資你的程式會有 \(p\) 的機率答對，並且你做了 \(k\) 次取最好的，請問你 AC 的機率是多少
- 一筆測資對的機率 \(\rightarrow p\)
- 單筆測資答錯：猜了 k 次全部都錯，機率是 \((1 − p)^k\)
- 單筆測資答對：\(1 − (1 − p)^k\)
- 全部答對：\((1 − (1 − p)^k)^T\)
生日悖論
假設一年有 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
- 一樣的子字串，拿去做hash，出來的值一定一樣
- 但是一樣的 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\) 矩陣裡面的數值具體要塞什麼？
先別急，再觀察一個性質
- 如果 \(AB = C\)，則不論 \(R\) 是什麼，等號一定成立
- 如果 \(AB \neq C\)，則不論 \(R\) 是什麼，等號「不一定」成立
有這個性質可以幹嘛？
可以 random!!
讓 \(R\) 裡面所有的元素全部都是亂數生成的
考慮 \(AB \neq C\) 的情況，思考一下會發現，等號「成立」的情況機率很低，直接去算 \(A(BR)=CR\) 好像很大機率會過！
不對啊！等號「成立」怎麼辦 \(\rightarrow\) 多做幾次!!
多做幾次，讓WA的機率越乘越低，是 random 演算法的精神之一!
while(time--){//做個 t 次，不要超過複雜度就好
1.隨機生成R矩陣
2.算A(BR)
3.算CR
4.如果ABR != CR -> "NO!!!!!"
5.如果ABR == CR -> 再做一次
}
做t次做完了，都沒問題 -> "YEESSSSSSS!!"
這裡我們學到了「二維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:
9, 1, [3, 5, 3, 5], 2
為什麼呢？因為相同的數字透過 Xor 的性質，兩兩互相打架抵銷成 0
但是也有情況 Xor 會爛掉
- Xor 的好情況： \(a\) \(\oplus\) \(a =0\)
- Xor 的不夠好情況 \(1\) \(\oplus\) \(2\) \(\oplus\) \(3 =0\)
因此要避免這種情況發生，這時就要用到隨機ㄌ
可以選擇把每個元素透過隨機打到 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\)打架(?) ，一樣讓他們打起來，有兩種方法：
- 設計一個 \(\oplus_k\)，代表 \(k\) 進制的 xor
- 用相加的，同一種元素讓他們加起來為0
顯然 1. 很好懂但很難實作，讓我們講講2.
用相加的，我們假設一個區間裡面有 \(k\) 個 \(a\)，我們可以把 \((k-1)\) 個 \(a\) 打到 \(+x\)，第 \(k\) 個 \(a\) 設定成 \((k-1) \times (-x)\) ， 這樣可以使得這段區間的 \(a\) 相加為 0
因此可以這樣構造新的序列：
| 序列 | \(c\) | \(a\) | \(a\) | \(c\) | \(c\) | \(b\) | \(c\) | \(b\) | \(b\) | \(a\) |
|---|---|---|---|---|---|---|---|---|---|---|
| 打到的數字 | \(+z\) | \(+x\) | \(+x\) | \(+z\) | \(-2z\) | \(+y\) | \(+z\) | \(+y\) | \(-2y\) | \(-2x\) |
這樣就只要算區間和為零的子區間有多少就好了，因為是一個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…
但如果你有實作過的話，會發現最近點對分治超難寫，那我們試試隨機！
- 假設現在有 \(i-1\) 個點在平面上，而且知道前 \(i-1\) 個點的最近距離為 \(d\)
- 如果距離變短，那最近點對的其中一個點一定是 \(i\)
- \(i\) 周圍畫一個半徑為 \(d\) 的圓內有其他點
- 但是要檢查半徑為 \(d\) 的圓內有沒有其他點太難了 QQ
- 退而求其次，我們找到一些可能跟它距離小於 \(d\) 的點
- 把整個平面切成 \((\frac{d}{2})\) × \((\frac{d}{2})\) 的網格
- 檢查所有 \(i\) 所在的格子和周圍 8 格和再往外一圈共 25 格裡的點
- 如果找到距離小於 \(d\) 的點，就把網格重畫 ; 否則把 \(i\) 直接加進它在的那個格子裡
聽起來，我們這時想到的做法會是：
- 先把兩個點放在平面上，以這個點對當做目前的最近點對，距離為 \(d\) ，並用這個 \(d\) 在平面上分割網格
- 對於第 \(3\)~\(n\) 的點\(i\)，檢查點 \(i\)在網格上的附近25個點，如果有點並且這個點跟點 \(i\) 可以更新 \(d\)：
- 就：用這個新的最近點對重新畫網格
- 否則：放進網格內
算算看複雜度
-
每個格子內最多只有 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)\) 就可以做完了
一些細節
- 因為有些點座標會有負數，所以要事先把座標搬到第一象限
int mnx=1e18,mny=1e18;
for(auto [x,y]:a){
mnx=min(mnx,x);
mny=min(mny,y);
}
for(auto& [x,y]:a){
x-=mnx;
y-=mny;
}
- 為了好好分割網格，你可能會砸 map ，但是在值域很大 (ex:1e9,1e16)的時候還是乖乖做分治，不然map會炸掉QQ
如果不信任 map 的話，也可以自己寫一個 hash
唬爛吧！
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe