tags: 電資圈接力 Challenge

隨機大法好

---

前言

本來想寫連通分量跟 tarjan 的介紹，但我發現可能會寫得又臭又長，加上我不會畫畫，於是就決定來介紹更酷的東西。

第一篇教學文／
廢話不多說，直接進入正文

---

先備知識 — 如何產生亂數

懶人包：已經會的話可以直接跳過這一部分。

參考資料：https://blog.gtwang.org/programming/cpp-random-number-generator-and-probability-distribution-tutorial/

要有一個可以產生亂數的工具，首先必須備齊三大工具：

1. 亂數種子（Random Seed）

點我

亂數的生成幾乎都是用一些複雜的數學公式（偽隨機），而種子的功能就是做為這些公式的某些初始參數。

常用的種子是時間資訊，取用方法有 time(NULL) 或是 chrono::steady_clock::now().time_since_epoch().count()。

另外也可以用 std::random_device，這東西會抓系統的一些隨機資訊來產生亂數，詳細介紹可以看上面那篇參考資料。

.

2. 引擎（Generator）

點我

隨機算法的核心，把種子餵給他後，就可以幫你產生一連串的亂數。

個人最常用的是 std::mt19937，背後的演算法是梅森旋轉演算法。

宣告一個引擎的語法：引擎 名稱(種子);
例如：std::mt19937 gen( time(NULL) );

其他引擎可以參考上面那篇文。

.

3. 數值分布（Distribution）

點我

分布的功能就是將引擎產生的數值，依照我們的需求轉換為各種機率分布，例如均勻分布、常態分布、二項分布等等。

基本上如果沒有特別的需求，使用 uniform distribution （均勻分布）就夠了。

如果是使用整數，語法是 std::uniform_int_distribution<int> 分布名稱(最小值, 最大值)。
如果是使用小數，語法是 std::uniform_real_distribution<double> 分布名稱(最小值, 最大值)。

舉例：std::uniform_int_distribution<int> dis(0, 100);
而產生一個亂數的語法：分布(引擎)

其他數值分布可以參考上面的文章。

.

以下示範如何隨機產生 100 個介於 0~10000 的整數：

#include <chrono>
#include <random>
#include <iostream>

using namespace std;

int main() {
    mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> dis(0, 10000);
    
    for (int i = 0; i < 100; i++) {
        cout << dis(gen) << endl;
    }
}

---

暖身：大數運算

題目來源：改編自 2020 資訊之芽團體賽

給一個正整數

$N$，令

$M=N\text{mod}987654321$，請計算

$M^N\text{mod}2$ 的結果。

$N\le {10}^{{10}^5}$，測試資料共

$\lfloor \pi \rfloor$ 筆。

完蛋，看起來好難喔，怎麼辦 QQ？

別忘了，解一道題目最重要的步驟便是好好觀察題目的性質。

注意到

$\lfloor \pi \rfloor =3$，並且答案只有

$0$ 跟

$1$ 兩種。

因此我們可以不管

$N$，直接隨機決定要輸出

$0$ 還是

$1$ 就好。

這個做法的 AC 機率

$=(\frac{1}{2}{)}^3=\frac{1}{8}$。期望上只要丟 8 次就會過了，夠有緣的甚至一發爽爽 AC。

類題練習

延續例題，只是測試資料從

$\lfloor \pi \rfloor$ 筆變成

$\lfloor \text{🥧}\rfloor$ 筆。

提示一

🥧 = pie

提示二

pie =

$\pi e$

作法

$\lfloor \text{🥧}\rfloor =8$，和例題的作法一樣，有

$\frac{1}{256}$ 的機率可以 AC，期望只要丟 256 次就行了。

---

不那麼隨機的隨機

先備知識：前綴和

先看簡單版的題目：

輸入一個長度為

$N$ 的陣列

$A$，接下來有

$Q$ 筆詢問。

第

$i$ 筆詢問有兩個數字

$L_i,R_i$，問每種數字在區間

$A[L_i]\sim A[R_i]$ 出現次數是否恰好為

$3$ 的倍數？

對於每筆詢問，輸出一行 YES 或 NO。

$N\le {10}^5,Q=3,$ 測資只有一筆。

$1\le A_i\le N$

首先先盯著這個問題，然後會發現一個關鍵的性質 —

$Q=3$，且答案只有兩種。類似剛才所學到的作法，枚舉這三筆詢問要輸出的是 YES 或 NO，最多只要丟 8 次就會過了。不要跟我說什麼 O(NQ) 暴力統計出現次數就可以解決我不聽我不聽我不聽

.

接著是加強版：

輸入一個長度為

$N$ 的陣列

$A$，接下來有

$Q$ 筆詢問。

第

$i$ 筆詢問有兩個數字

$L_i,R_i$，問每種數字在區間

$A[L_i]\sim A[R_i]$ 出現次數是否恰好為

$3$ 的倍數？

對於每筆詢問，輸出一行 YES 或 NO。

$N\le {10}^5,Q\le {10}^5$

$1\le A_i\le N$

有個很聰明的作法，用文字不太好形容，直接舉例子。

假設陣列是

$[1,2,1,1,2,1,2,2]$。

讓

$1$ 映射到任意數字

$x$，

$2$ 映射到任意數字

$y$。

定義陣列

$B$ 如下：

陣列 $A$	1	2	1	1	2	1	2	2
陣列 $B$	$x$	$y$	$x$	$-2x$	$y$	$x$	$-2y$	$y$

概念就是，若數字為

$a$，其對應到的數字為

$m_a$，若該數字由左往右出現第 「

$3$ 的倍數」次，則它在

$B$ 陣列中的值就要被設為

$-2m_a$，反之則設為

$m_a$。

有了

$B$ 陣列，該如何判斷答案呢？

詢問的時候，若每種數字在區間

$[L_i,R_i]$ 出現次數皆為 3 的倍數，

則代表

$B[L_i]+B[L_i+1]+...+B[R_i]=0$

這時就輸出 YES，否則輸出 NO。

而只要套用前綴和的技巧，

$O(1)$ 回答

$B[L_i]+...+B[R_i]$，就可在

$O(N+Q)$ 的時間內解決這題。

.

然而這作法還是有問題，因為

$B[L_i]+...+B[R_i]=0$ 的時候答案不一定是 YES。

舉例

陣列 $A$	1	1	1	2
陣列 $B$	$x$	$x$	$-2x$	$y$

讓

$x=1,y=2$，詢問

$[3,4]$ 便會判斷錯誤。

問題在於

$A$ 中每個數字的映射範圍不能太小，否則很容易就會發生判斷錯誤的情況。

這時只要保證

$A$ 的每個數字隨機映射到的數字夠大、夠分散，例如隨機映射到

$[1,{10}^9]$ 之間的數字，就有很高的機率能夠避開判斷失誤，穩穩 AC。

類題練習

題目：資芽 OJ 793 — 想不到題目標題QQ

---

我不會下標題，但這真的很有趣

先備知識：二分搜

經典例題：資芽 OJ 794 — 區間絕對眾數

若某個數字

$x$ 在一個序列中出現次數 嚴格超過 序列長度的一半，稱

$x$ 為該序列的絕對眾數。

輸入一個長度為

$N$ 的正整數序列

$a_1,...,a_N$，接下來有

$Q$ 筆詢問。

每筆詢問輸入

$l_i,r_i$，輸出區間

$[l_i,r_i]$ 的絕對眾數，若不存在請輸出

$0$。

$N,Q\le 5\times {10}^5,1\le a_i\le 5\times {10}^5$

提示

如果我在一個區間隨機戳一個數字的話…

.

溫馨提示

建議直接點開以下提示，因為我本人想了一年多才在偶然獲得的提示下想到這題的關鍵。

對，整整一年。

.

破題關鍵

如果我在一個區間隨機戳一個數字的話，那我戳中絕對眾數的機率會是

$\frac{1}{2}$。

.

完整做法

那我們不妨在這個區間內隨機選

$30$ 個數字，然後一一檢查它們是不是絕對眾數，而連續

$30$ 次都戳不中絕對眾數的機率略小於

${10}^{-9}$，基本上可以忽略這微小的機率，假裝一定會戳中。

因此單筆詢問的正確率為

$1-{10}^{-9}$，連續

$Q$ 筆詢問都正確的機率為

$(1-{10}^{-9}{)}^Q$，若

$Q=5\times {10}^5$，則 AC 的機率約為

$99.95\mathrm{\%}$，幾乎可以一發 AC，一次不過第二次也會過。如果有人可以連續兩次都 WA 的，請截圖 + 傳 code 私訊我，請你吃三碗拉麵。

現在還有一個問題要解決：要怎麼快速知道一個數字在某個區間內是不是絕對眾數？或者，要怎麼快速知道一個數字在某個區間內出現幾次？

有個比較直覺的作法，先開一個大小

$5\times {10}^5$ 的 vector 陣列

$pos$，

$pos[a]$ 存

$a$ 這個數字在原序列中依序出現的位置。

.

舉例如下：

$i$	1	2	3	4	5	6
$a_i$	1	2	1	1	2	2

則 pos 陣列如下：

$a$	$pos[a]$
1	1, 3, 4
2	2, 5, 6

要詢問一個數字

$a$ 的在區間

$[l,r]$ 的出現次數，可以換個角度，改成詢問

$pos[a]$ 中有幾個數字介於

$l\sim r$ 之間。

由於

$pos[a]$ 嚴格遞增，因此對

$pos[a]$ 做二分搜，搜尋 「第一個大於等於

$l$ 的數字」的位置，以及 「第一個大於

$r$ 的數字」的位置。兩個搜到的答案相減，就是

$a$ 在該區間出現的次數。

.

舉例如下：

沿用上例的 pos 陣列，假設詢問 1 在區間

$[2,5]$ 出現幾次，

則可以反過來問

$pos[1]$ 中，有幾個數字介於

$2\sim 5$ 之間。而符合條件的數字以紅色標示：

$a$	$pos[a]$
1	1, 3, 4
2	2, 5, 6

這件事情可以用二分搜做到。

懶的寫二分搜的話可以用 lower_bound 函式，我是怪人我每次二分搜都還是會自己刻。

.

這個做法的總複雜度為

$O(N+kQ\log N)$，

$k$ 是每次詢問挑的數字個數（上面的作法

$k=30$）。

如果會 TLE 的話可以把

$k$ 改小一點，會 WA 的話就改大一點。

.

另解

這題還有另外一個非隨機做法，不僅速度更快（經實測時間是隨機的一半），而且正確率

$100\mathrm{\%}$，有興趣的可以上網搜尋「戰鬥線段樹」，也是一個超酷的作法。

或是參考台中一中 x 資奧二階大佬 abc864197532 的文章：
https://abc864197532.github.io/2021/02/07/tioj-2140/

更多隨機

隨機有趣的題目遠不止這些，甚至經典分治題 —最近點對— 也有隨機演算法。

想要更多有趣的題目請點我

真的想要更多有趣的題目請再次點我

真的真的想要解鎖更多有趣的題目拜託再次點我

使用電資圈接力的 tag 以解鎖更多