在數學意義上並沒有真正的亂數,因此都只能用時間種子或者是怪怪的公式去假裝亂數
所以我們今天使用的是時間種子
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 阿
shuffle(arr,arr+n,mt);
跟sort的用法一樣,代表直接把你的arr全部打亂 就這樣。
如題 MOD 2 的話,那就隨機兩次(X
*絕對眾數 數字出現次數超過長度的一半
給你長度為N的 arr,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\) 就可以保證會是對的。
這種東西只能找機率XD
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