圖論測資生成器

最近寫了一個 GRAPH_GEN.h 檔,想說可以方便生成測資。

簡介

  • 4~5 行是防禦性程式設計,避免多次引用標頭檔時發生編譯錯誤
  • 7~19 行用來生成隨機數
  • 21~32 行是帶有建構式的 edge 物件
  • 底下就是生成測資的物件

具體使用

  • GenTree(n) -> 生成一個有 n 個點,且無邊權的無根樹
  • GenConnectedGraph(n,m) -> 生成一個有 n 個點, m 條邊,且無邊權的連通圖
  • GenGraph(n,m) -> 生成一個有 n 個點, m 條邊,且無邊權的不保證連通圖
  • GenTree(n,k) -> 生成一個有 n 個點,且邊權介於 1~k 的無根樹
  • GenConnectedGraph(n,m,k) -> 生成一個有 n 個點, m 條邊,且邊權介於 1~k 的連通圖
  • GenGraph(n,m,k) -> 生成一個有 n 個點, m 條邊,且邊權介於 1~k 的不保證連通圖

前三個會回傳 vector<pair<int,int>> 每個皆有保證沒有自環,後三個則會回傳 vector<edge> ,以節省重複打 firstsecond 的時間

程式碼

#include<bits/stdc++.h>
using namespace std;

#ifndef GRAPH_GEN
#define GRAPH_GEN

unsigned seed=chrono::steady_clock().now().time_since_epoch().count();
mt19937_64 rng(seed);

using ll=long long;

ll Rand(ll a,ll b){
    uniform_int_distribution<ll> dis(a,b);
    return dis(rng);
}

ll Rand(ll a){
    return Rand(1,a);
}

struct edge{
    int from,to;
    long long dis;

    edge(){}

    edge(int f,int t,long long d){
        from=f;
        to=t;
        dis=d;
    }
};

class GraphGen{
    private :
        struct DSU{
            vector<int> dsu,rk;

            DSU(int n){
                dsu.resize(n+10);
                rk.resize(n+10);
                init();
            }

            void init(){
                for(int i=0;i<dsu.size();++i){
                    dsu[i]=i;
                }
            }

            int find(int a){
                if(dsu[a]==a){
                    return a;
                }else{
                    return dsu[a]=find(dsu[a]);
                }
            }

            bool same(int a,int b){
                return find(a)==find(b);
            }

            void uni(int a,int b){
                if(same(a,b)){
                    return;
                }

                if(rk[find(a)]==rk[find(b)]){
                    dsu[find(b)]=find(a);
                    rk[a]++;
                }else if(rk[find(a)]>rk[find(b)]){
                    dsu[find(b)]=find(a);
                }else{
                    dsu[find(a)]=find(b);
                }
            }
        };
    public :
//      nodes 1~n
        static vector<pair<int,int>> GenTree(int n){
            DSU dsu(n);
            vector<pair<int,int>> result;

            while(result.size()<n-1){
                int a=Rand(n),b=Rand(n);
                if(!dsu.same(a,b)){
                    result.emplace_back(a,b);
                    dsu.uni(a,b);
                }
            }

            return result;
        }
//      n nodes m edges, m need to bigger than n-1
        static vector<pair<int,int>> GenConnectedGraph(int n,int m){
            vector<pair<int,int>> result=GenTree(n);

            for(int i=0;i<m-n+1;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                result.emplace_back(a,b);
            }

            return result;
        }
//      n nodes m edges, m need to bigger than n-1
        static vector<pair<int,int>> GenGraph(int n,int m){
            vector<pair<int,int>> result;

            for(int i=0;i<m;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                result.emplace_back(a,b);
            }

            return result;
        }
//      nodes 1~n, and weight in 1~k
        static vector<edge> GenTree(int n,int k){
            DSU dsu(n);
            vector<edge> result;

            while(result.size()<n-1){
                int a=Rand(n),b=Rand(n),c=Rand(k);
                if(!dsu.same(a,b)){
                    result.emplace_back(a,b,c);
                    dsu.uni(a,b);
                }
            }

            return result;
        }

        static vector<edge> GenConnectedGraph(int n,int m,int k){
            vector<edge> result=GenTree(n,k);

            for(int i=0;i<m-n+1;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                int c=Rand(k);

                result.emplace_back(a,b,c);
            }

            return result;
        }

        static vector<edge> GenGraph(int n,int m,int k){
            vector<edge> result;

            for(int i=0;i<m;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                int c=Rand(k);

                result.emplace_back(a,b,c);
            }

            return result;
        }
};

#endif

使用範例 :

#include<bits/stdc++.h>
#include "GRAPH_GEN.h"
using namespace std;

int main(){
    vector<pair<int,int>> edges=GraphGen::GenTree(100000);
}

iPhone SE 第 3 代

前言

2022 年蘋果春季發表會,iPhone SE 第 3 代如期問世,這一篇,就來哈啦一下我對這支手機的看法。
iPhoneSE3rdGenEp1
Screenshot of iPhone SE – Apple (台灣)


iPhone SE 第 3 代比較不足的部分

  1. 經典的外觀設計:蘋果提到第 3 代的 iPhone SE 所使用的玻璃更厲害了,但…外表幾乎長得一模一樣,另外,蘋果操作得還不錯的顏色梗,也沒有放在這一代的 iPhone SE 上。附帶一提的是我自己購買 iPhone SE 第 2 代的經驗並不好,鋁殼的刮傷總讓我認為我拿到的是回收且沒有處理好的 iPhone,以一部經典的手機而言,我認為有點可惜,也可以再加強。
    iPhoneSE3rdGenEp2
    Screenshot of iPhone SE – Apple (台灣)

  2. 4.7 吋的螢幕:以我個人而言,一方面,我已經有老花;一方面,我也會玩遊戲,4.7 吋的螢幕對於目前市面上大部分的遊戲而言,已經不是那麼足夠。感覺,這一點是硬傷,但是,如果釋出大一點的螢幕尺吋,又似乎會打到自家主線的機種。

iPhone SE 第 3 代的優點?

  1. 處理器與上網速度:A15 與 5G 加持,對於有速度要求的人而言,iPhone SE 第 3 代在這方面的規格上是沒有讓人失望。
  2. 提升的續航力表現:官方提到 iPhone SE 第 3 代與前代相比,又有一些進步,如果這個訊息的參考度夠高,那麼,確實會讓人感到滿開心的。
    iPhoneSE3rdGenEp3
    Screenshot of iPhone SE (第 3 代) vs iPhone SE (第 2 代) vs iPhone SE (第 1 代) – Apple (台灣)

結論

  1. 雙主修入門機:蘋果至今應該並沒有直接表達,iPhone SE 的問世,主要是想要拉攏一些 Android 陣營的伙伴,我也認為這支手機還是有一定的市場,如果真的如消息指出的那般,就我個人的角度來說,我是一個第 1 代、第 2 代都有入手的使用者,幾代的觀察下來,會認為對於一個常年都是 Android 陣營的人而言,或許會是一個成為系統雙主修的入門機,也可以是 iOS 備用機,或是實體的 App 程式設計 Demo 機。
  2. 也可以是孩子們使用的手機:高 CP 比較能夠與 iPhone SE 搭上點邊,如果不想讓孩子們拿一支要價 2 萬元以上的手機,又想讓孩子們一起在 iOS 的圈子裡,那麼,除了二手機之外,iPhone SE 會是很好的選擇。只是…,我還滿常看到手拿 Pro Max 的孩子們。

[版本更新] 快速回顧 微軟發布 KB5011493 (Windows 11 作業系統組建 22000.556)

前言

時間過得很快,3 月份的 Windows 11 品質更新已經釋出:KB5011493 (作業系統組建 22000.556)。
Windows11UpdateKB5011493(OSBuild22000.556)Ep1
Windows11UpdateKB5011493(OSBuild22000.556)Ep2


更新前內容概覽

我先大致讀了一下 2022 年 3 月 8 日 —KB5011493 (OS Build 22000.556) 裡的說明。

更新重點是「更新您作業系統Windows安全性」,但更新內容,我自己覺得讀起來有點吃力,反而切換到英文版說明(如下,也可以點傳送門(↗)去官網瞧瞧),讀起來會好些(僅管我的英文閱讀弱弱的)。

Addresses a known issue that occurs when you attempt to reset a Windows device and its apps have folders that contain reparse data, such as Microsoft OneDrive or Microsoft OneDrive for Business. When you select Remove everything, files that have been downloaded or synced locally from Microsoft OneDrive might not be deleted. Some devices might take up to seven (7) days after you install this update to fully address the issue and prevent files from persisting after a reset.

確實不太容易翻譯,而且,文中以 OneDrive 的狀況為例,可以想見,如果是比較大量使用 OneDrive 的 End User,這支補丁勢必是打上去比較妥。

…是說,我的貼文也是會有錯字、漏字之類的狀況,只是,總覺得以微軟官方的角度而言,這樣的翻譯或說明文的品質,似乎還是有加強的空間。(下圖)
Windows11UpdateKB5011493(OSBuild22000.556)Ep4


更新後的觀察

這支更新補丁,網路上也有一些文章,等待幾天,沒有看到什麼災情,我目前的決定就是先打上去,使用起來並沒有太大的感覺,系統也沒有因此變慢或變快。
Windows11UpdateKB5011493(OSBuild22000.556)Ep3


後記

我個人的推測是隨機出貨的系統都已經搭載 Windows 11,狀況太多應該有點說不過去,幾年來的觀察,發現無論是什麼樣的平台,每一次的系統更新,其實都有一定的風險,至少今年,我會持續注意 Windows 11 的更新補丁。

維琴河 | Virgin River (Netflix)

前言


Photo on Squamish Neighbourhoods | Move to Squamish

2022 年的農曆新年前,老婆決定用 Netflix 追「華燈初上」,而我也滿讚成這項決定的。一方面,老婆要出錢(嘿嘿);一方面,我想看「獵魔士」、「后翼棄兵」已經超久的。

但,追劇有幾個缺點不得不說,一個是花費不少時間,我在這個時間裡,邊看邊吃邊當看劇的傻子,持續耍廢讓我胖了不少;一個是追完之後,總會有一種空虛感。

Netflix 上面的片量算大,但我卻不知道如何著手,「維琴河」就在我盲目瀏覽時開啟追劇之旅的。


目前的感想

我之所以用「目前的感想」下標題,是因為我還沒有把目前已播出的 3 季都追完(現階段走到第 2 季第 8 集)。

以現在的進度而言,我認為「維琴河」非常值得一看,我想分享的幾點大致如下。

  1. 鄉下地方:有別於以往看劇的角度,我現在看到的是美國鄉下地方,其實也跟我們國內很像,尤其我也算是鄉下地方長大的孩子,「維琴河」裡面的點點滴滴,都滿能夠引起我的共鳴的。
  2. 對話:我喜歡劇裡面,每個角色幾乎都是大剌剌、直接地表達自己的想法、感受,這些對話,也滿值得玩味。
  3. 美景:劇中不時會有不同時間、角度的「維琴河」,有時會讓我覺得「哇喔!好美!」,有時則是會讓我覺得「一條河那麼的巨,人跟人之間所發生的點點滴滴都顯得好渺小呀!」

後記

雖然,我沒有完整追完第 3 季,但我已經先點看第 3 季的結局,…想不到男女主角還沒有結束,而且第 3 季最後 1 集埋了不少梗,我心裡頭有點急著想知道結局,網搜並且再加上自己做功課之後,得知男女主角的結局,就寫在 Virgin River – RobynCarr 這一本裡面,走一趟 Play Store,花費 15 元搭配我還堪用的英文閱讀能力,直接得知結局。即便如此,我還是回過頭來繼續追劇,因為,我認為有別於原版小說,Netflix 上頭呈現出來的劇況仍讓我著迷。


延伸閱讀

  1. Virgin River – RobynCarr
  2. Where is Virgin River filmed? All the locations for Netflix series | Radio Times

關於「蝦米鍵盤2」(iOS & iPadOS) 的設定

前言

延續 智慧型手機上的嘸蝦米使用心得 這一篇,本篇貼文主要是以截圖搭配文字的方式,紀錄 在 App Store 上的「蝦米鍵盤2」 的設定介面等。


付費功能

1. 有別於嘸蝦米輸入法 PRO (Android 版),「蝦米鍵盤2」並沒有所謂的試用,而是直接就能夠使用嘸蝦米的輸入功能,如果要將整套的功能都買下來,會比嘸蝦米輸入法 PRO (Android 版)稍貴個新台幣 33 元,以我來說,我就只買自己需要用到的功能,雖然是所有付費功能最貴的,但數算起來反而比購買正式版的嘸蝦米輸入法 PRO (Android 版)來得便宜。
boshiamyKeyboard2foriOSEp (2)

2. 下列截圖,就是我沒有買的功能:【自定按鍵字體與鍵盤高度】(左圖)、【自定鍵盤顏色與素材】(右圖)。
boshiamyKeyboard2foriOSEp (4) boshiamyKeyboard2foriOSEp (5)

3. 承上,下圖的紅色圓角框圈起來的地方,正好就是我沒有花錢購買的部分。附帶一提的是我自己認為【鍵盤直立高度】與【鍵盤橫立高度】所提供的設定數值並不直覺,如果用螢幕佔比或是圖示的方式就更加完美,…雖然我不太會去動這個設定就是。
boshiamyKeyboard2foriOSEp (3)


功能設定

1. 從 App Store 把「蝦米鍵盤2」載到 iPhone 或 iPad 後,可以找到一個名為「蝦米鍵盤2」的 App (下圖所示是我已經把「蝦米鍵盤2」丟到一個夾子裡)。
boshiamyKeyboard2foriOSEp (1)

2. 付費功能的設定部分,必須先開啟【允許完整取用】,有 2 條路可以走到這個設定的位置,分別是:
(1)開啟 iOS(iPadOS) 上的【設定】→【一般】→【鍵盤】→【鍵盤】→【蝦米鍵盤2】。
(2)開啟【蝦米鍵盤2】這支 App,點右上角的【系統設定】→【鍵盤】,就會走到下面截圖所示的設定。
boshiamyKeyboard2foriOSEp (6)

3. 開啟【觸覺回饋設定】,我還滿習慣用觸覺回饋的,…僅管可能會比較耗電。
boshiamyKeyboard2foriOSEp (7)

4. 開啟【中文鍵盤設定】之【屏蔽無效鍵】,開啟後,可以自動把無效字碼屏蔽掉,減少輸入錯誤。
boshiamyKeyboard2foriOSEp (8)

以下圖為例,我打算輸入「嘸」這個字,解到第 2 個字碼時,有不少無效字碼就會自動被屏蔽掉。
boshiamyKeyboard2foriOSEp (9)


後記

  1. 本次截圖上的「蝦米鍵盤2」,是在 iOS 15 上運行。
  2. 滿希望「蝦米鍵盤2」的開發者能夠調整一個部分:「付費購買【功能組合包】後,能不能把廣告關掉?」
    boshiamyImeProfessionaliOSEp1

    因為,開啟設定才會看到廣告,到目前也還算能夠接受,但,付費購買後,還要再看到廣告,總讓人覺得哪裡怪怪的。
    boshiamyImeProfessionaliOSEp2

  3. Android 版本的傳送門:關於嘸蝦米輸入法 PRO (Android 版)的設定