總有一天會用到的筆記

本站為減緩筆者下列疑難雜症誕生：記性很差，學過就忘；智商低落，囫圇吞棗。

0%

發表於 分類於

JOI18. Commuter Pass

有 \(n\) 點 \(m\) 邊的帶權無向圖（\(n\le 10^5; m \le 2\times10^5\)）。你可以指定一條 \(s-t\) 的最短路使其邊權歸零，求 \(u-v\) 的最短路徑。

作法

考慮將無向圖拆成有向圖。存在 \(stDAG\) 的任何完整路徑（從入度為零的點開始，走到出度為零的點為止）都是 \(s-t\) 最短路。

答案有三種可能：

  1. 不經過 \(s-t\) 最短路，\(ans = dis(u,v)\)
  2. \(u\) 從 \(x\) 接入 \(stDAG\)，從 \(y\) 離開 \(stDAG\) 前往 \(v\)，\(ans = dis(u,x)+dis(y,v)\)
  3. \(v\) 從 \(x\) 接入 \(stDAG\)，從 \(y\) 離開 \(stDAG\) 前往 \(u\)，\(ans = dis(v,x)+dis(y,u)\)

想找出 \(dis(v,x)\) 和 \(dis(y,u)\) 只要從 \(u,v\) 分別作 Dijkstra 即可。

如何找到 \(x, y\) ?

考慮在 \(stDAG\) 上 DP：

  • \(dpu[i]\) 代表 \(path(s,i)\) 上最小的 \(dis(u,i)\)
  • \(dpv[i]\) 代表 \(path(s,i)\) 上最小的 \(dis(v,i)\)

則將 \(i\) 作為 \(y\) 的答案即為 \(min(dpu[prev]+dis(v,i), dpv[prev]+dis(u,i))\)。

如何在 \(stDAG\) 上 DP？

對於正邊權圖，只要維護 \(vis\) 使得每個點只會被拿出來一次，Dijkstra 拿出來的順序就是在單源最短路 DAG 上的拓樸排序。

因此我們可以從 \(s\) 做一次 Dijkstra ，在 \(sDAG\) 上得到 \(dpu\) 和 \(dpv\)。

若我們在 \(sDAG\) 的反圖 \(sDAG'\) 上從 \(t\) 做 BFS 相當於在 \(tsDAG\) BFS。此時任一節點 \(i\)，後繼節點為 \(j\)，則將 \(i\) 作為 \(y\) 的答案是 \(min(dpu[j]+dis(v,i), dpv[j]+dis(u,i))\)

BFS 不用另外寫，直接重複使用 Dijkstra 即可（被拿出來的順序不重要）。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
#define int long long
#define rep(i,j,k) for (int i=j; i<=k; i++)
#define pb push_back
#define lyx_my_wife ios::sync_with_stdio(0), cin.tie(0);
using namespace std;
typedef pair<int,int> pii;
 
const int N = 1e5+10, M = 2e5+10;
 
int n, m, s, t, u, v;
vector<pii> G[N];
 
int disu[N], disv[N], diss[N], dist[N], vis[N];
int dpu[N], dpv[N], ans;
 
void dijks(int rt, int dis[N], int fordp=0, int forans=0)
{
    memset(dis, 0x3f, sizeof(disu));
    memset(vis, 0, sizeof(vis));
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dis[rt] = 0;
    pq.push({0, rt});
 
    if (fordp)
    {
        memset(dpu, 0x3f, sizeof(dpu));
        memset(dpv, 0x3f, sizeof(dpv));
    }
    
    while(pq.size())
    {
        int i = pq.top().ss, d = pq.top().ff;
        pq.pop(); 
 
        if (vis[i]) continue;
        vis[i] = 1;
 
        if (fordp)
        {
            dpu[i] = min(dpu[i], disu[i]);
            dpv[i] = min(dpv[i], disv[i]);            
        }
 
        for (auto e: G[i])
        {
            int j = e.ss, w = e.ff;
 
            if (forans)
            {
                if (diss[j] != diss[i]-w) continue;
                ans = min(ans, dpu[j]+disv[i]);
                ans = min(ans, dpv[j]+disu[i]);
            }
 
            if (dis[j] > d+w)
            {
                dis[j] = d+w;
                pq.push({dis[j], j});
                if (fordp) dpu[j] = dpu[i], dpv[j] = dpv[i];
            }
            else if (dis[j] == d+w)
            {
                if (fordp) dpu[j] = min(dpu[j], dpu[i]), dpv[j] = min(dpv[j], dpv[i]);
            }
        }
    }
}
 
signed main()
{
    lyx_my_wife
    cin >> n >> m >> s >> t >> u >> v;
    rep(_,1,m)
    {
        int i, j, w;
        cin >> i >> j >> w;
        G[i].pb({w,j});
        G[j].pb({w,i});
    }
 
    dijks(u,disu);
    dijks(v,disv);
    dijks(s,diss,1);
    ans = disu[v];
    dijks(t,dist,0,1);
    cout << ans << '\n';
}

發表於 分類於

Tkinter 是一個可以用 Python 寫出 GUI，並輕鬆串到自己寫的 Python API 的套件。

Tkinter、ttkbootstrap

tkinter.ttk 是風格化的 tk 元件。而 ttkbootstrap 是風格參考至 CSS 框架 bootstrap 的 tkinter 主題插件。ttkbootstrap 提供了許多現代化的主題、簡便的主題設置方式及額外的元件。安裝和使用可參考至官方文件。

製造主視窗

1
2
import tkinter as tk
import ttkbootstrap as ttk
1
2
3
style = ttk.Style(theme='lumen')
root: tk.Tk = style.master
root.geometry(f'600x400')

產生元件

我們需要實例化一個元件出來，並在建構子中指定父元件。利用 elm.grid 或 elm.pack 等方法可以將 elm 顯示於父元件中。

一些基本的元件有：

  • Frame：一塊空白的容器，通常用來放入其他元件做分類、排版用。如果要有框框可以用 LabelFrame。
  • Button：按鈕。在 comand 參數放入函式，可以在按下按鈕時執行。
  • Label：文字
1
2
3
4
frm_elm = ttk.Labelframe(root)
frm_elm.grid()

ttk.Button(frm_elm, text='owo').grid()

在所有元件的最後，使用 root.mainloop() 顯示主視窗。

1
root.mainloop()

可以看到，LableFrame 緊貼在視窗左上角，然後 Button 填滿了 LableFrame。

佈局方法

grid 是常用的佈局方法。預先在父元件中分配好每個欄、列的比例，並指定該物件位於父元件的位置、所佔欄列數即可。

rowconfigure/columnconfigure可以配置每個欄列的比例。 rowconfigure/columnconfigure 的參數：

  • index：第一個參數。指定要配置哪些列（可塞 int、list 或 tuple）。
  • weight：指定這些列的比例。weight=1 為單位比例。

grid 的常用參數：

  • row/column：指定該元件的左上角要放在父元件的哪個網格
  • rowspan/columnspan：該元件要跨幾個欄／列
  • padx/pady：填充外部，增加與其他元件的空隙
  • ipadx/ipady：填充內部，增加邊界與文字、圖片內容的空隙
  • sticky：對齊方式。'n' 會靠上，'ns' 會上下延伸，'nswe' 會填滿四邊，以此類推。
1
2
3
4
5
6
7
8
9
10
11
12
13
style = ttk.Style(theme='lumen')
root: tk.Tk = style.master
root.geometry(f'600x400')
root.rowconfigure(0,weight=1)
root.columnconfigure(0,weight=1)


frm_elm = ttk.Labelframe(root)
frm_elm.grid(sticky='nswe', padx=5, pady=5)
frm_elm.rowconfigure(0,weight=1)
frm_elm.columnconfigure(0,weight=1)

ttk.Button(frm_elm, text='owo').grid(sticky='we', padx=5, pady=5)

風格

ttkbootstrap 提供了非常方便的風格設置方式。只要在實例化元件時指定 bootstrap 參數即可，並且 ttkbootstrap 還提供了常數使用。

1
ttk.Button(frm_elm, text='owo', bootstyle=(ttk.DARK,ttk.OUTLINE)).grid(sticky='we', padx=5, pady=5)

Control variables

control variables 是一種特殊的物件，提供 get() 和 set() 來存取值，就像變數一樣。元件們可以共享同一個 control variables，並在它改變時自動更新顯示。如果將 control variables 指派給輸入元件（如：Radio Buttons、Entry）時，元件也可以改變 control variables 的值。

control variables 有： DoubleVar、IntVar、 StringVar、BooleanVar。

1
2
3
name = ttk.StringVar()
ttk.Entry(frm_elm, textvariable=name).grid()
ttk.Label(frm_elm, textvariable=name).grid()

RadioButton 則是透過共享 control variables 來達成只能選一個的效果。

1
2
3
4
5
name = ttk.StringVar()
ttk.Radiobutton(frm_elm, text='err', variable=name, value='err').grid()
ttk.Radiobutton(frm_elm, text='utaha', variable=name, value='utaha').grid()
ttk.Radiobutton(frm_elm, text='megumi', variable=name, value='megumi').grid()
ttk.Label(frm_elm, textvariable=name).grid()

更多資料可以參考至：

MVC

MVC 是一種軟體架構，代表 Model、View、Controller。

  • Model：資料庫、演算法，不依賴 View 和 Controller，透過 API 就能正常使用。
  • View：圖形界面，不含邏輯。
  • Controller：界面邏輯、轉發 View 層的請求到 Model、更新 View 層的顯示。

我的日麻點數計算器參考了 MVC 概念並用 Python 和 tkinter 實作。

主要概念是在 view 層裡將按鈕的 command 參數指定為 controller 層中的 handler。當按下按鈕，執行 handler 時 controller 會去查看 view 中的 control variables，把輸入資料打包後傳給 model 層。從 model 層獲得計算結果後，則呼叫 view 層的函數更新顯示。

由於 controller 和 view 會互相參考，我又想把它們寫在不同檔案裡，為了避免循環 import 的問題，我將 controller 和 view 分別打包成 class。當實例化一個 controller 物件時，它也會實例化 view 物件，並將該 view 物件的 contoller 設為 self。

架構如下：

  • view.py：
1
2
3
4
5
6
7
8
9
10
11
12
13
import tkinter as tk
import ttkbootstrap as ttk

class View:

    def __init__(self, _ctrl):
        self.ctrl = _ctrl
    
    def setup_ui(self):
        pass

    def display_result(self, result):
        pass
  • controller.py：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import tkinter as tk
import ttkbootstrap as ttk
from .view import View

class Controller:

    def __init__(self):
        self.view: View = View(self)

    def btn_handler(self):
        pass

    def runApp(self):
        self.view.setup_ui()
        self.view.root.mainloop()


if __name__ == '__main__':
    ctrl = Controller()
    ctrl.runApp()

這個專案一開始在寫 API 時一開始完全沒有考慮 GUI 的需求，好像恰好的符合了 MVC 中 Model 的獨立性......

發表於 更新於 分類於

由於 Python 中的函數也是物件，因此常常會出現在函數內定義函數、回傳函數的情形。若此時內部函數引用外部函數的區域變數，情況就會變得些微複雜，我們稱之為「閉包（Closure）」。

但只要理解以下 Python 的原理，閉包也能很好理解。

四個原理及示例

一、函數結束時區域變數不會直接被回收，而是等到無人參考。

實際上，被參考的外層變數會被綁到內層變數的 __closure__ 上。這個特性讓我們可以有閉包這種酷酷的操作。

二、呼叫函式時，會創造出一個命名空間

執行 outer 而產生一個命名空間。而因為 inner 參考至它，所以 outer 的命名空間不會被回收掉。 

1
2
3
4
5
6
7
8
9
>>> def outer():
...     owo = 1
...     def inner():
...         print(owo)
...     return inner
...
>>> func = outer()
>>> func()
1

每次執行函式，都會創造出一個全新的命名空間。這裡要用 nonlocal 是因為，除非加上 nonlocal 關鍵字，外部名稱是唯讀的。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
>>> def outer():
...     cnt = 0
...     def inner():
...         nonlocal cnt
...         cnt += 1
...         print(cnt)
...     return inner
...
>>> f1 = outer()
>>> f2 = outer()
>>> f1(), f1(), f1(), f2(), f2(), f2()
1
2
3
1
2
3

三、作用域是在哪裡 def 決定的，而非在哪裡被呼叫

作用域和搜尋順序關乎於寫在哪裡，而非在哪裡被呼叫：

1
2
3
4
5
6
7
8
9
10
>>> owo = 'starbuststream'
>>> def outer():
...     owo = 'mothersrosario'
...     def inner():
...         print(owo)
...     return inner
...
>>> func = outer()
>>> func()
mothersrosario

四、呼叫函數時，會參考至當前時間的命名空間，和宣告時沒關係。

呼叫 f() 時，該函數會以當前的命名空間狀態為主。此時執行完 for 迴圈，名稱 i 在全域中指向 2，因此函數參考外部名稱 i 時會讀取到 2。

注意，Python 的迴圈沒有獨立的命名空間，for i in range(3) 在全域新增了名稱 i。

1
2
3
4
5
6
7
8
9
10
11
12
13
>>> func_list = []
>>>
>>> for i in range(3):
...     def show():
...         print(i)
...     func_list.append(show)
...
>>> for f in func_list:
...     f()
...
2
2
2

解決辦法是在外部再包一層函數。利用迴圈執行 outer，製造出許多獨立的命名空間。每個命名空間裡都會有自己的名稱 j，分別指向物件 0、1、2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>>> func_list = []
>>> for i in range(3):
...     def outer():
...         j = i
...         def show():
...             print(j)
...         return show
...     func_list.append(outer())
...
>>> for f in func_list:
...     f()
...
0
1
2

寫成參數有相同療效：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> func_list = []
>>> for i in range(3):
...     def outer(j):
...         def show():
...             print(j)
...         return show
...     func_list.append(outer(i))
...
>>> for f in func_list:
...     f()
...
0
1
2

另外這裡有一個雷點，以下的程式碼看似可以正常的運作，其實是誤打誤撞：

1
2
3
4
5
6
7
8
9
10
11
12
>>> func_list = []
>>> for i in range(3):
...     def show():
...             print(i)
...     func_list.append(show)
...
>>> for i in range(3):
...     func_list[i]()
...
0
1
2

由於使用了 for，i 在每次迴圈被指向 0、1、2，而執行 func_list[i]() 時，函數又會參考至當前的命名空間，造成了這樣的笑話。若把下面的迴圈改成 j，就會印出 2 2 2 了。

應用

這項技巧經常用在

  • 批量產生函數，如按鈕的 handler
  • 裝飾器（Decorator）

以帶參數的裝飾器做示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>>> def deco_fac(message):
...     def deco(func):
...         def res():
...             print(message)
...             func()
...         return res
...     return deco
... 
>>> @deco_fac("starbuststream")     # 呼叫 deco_fac 會回傳 decorator
... def owo():
...     print("kirito")
... 
>>> owo()
starbuststream
kirito

發表於 更新於 分類於

剛接觸到 Python 時，很可能會遇到類似靈異現象： 

1
2
3
4
5
6
7
8
9
10
>>> a = []
>>> b = a
>>> b.append(1)
>>> a
[1]
>>> a = 1
>>> b = a
>>> b += 1
>>> a
1

又或者，對於 Python 時而 pass by reference，時而 pass by value 有所疑惑。如果嘗試搜尋，可能會發現它們皆與今天的主題有關。

Python 的變數是什麼？

首先來談最基本的問題：Python 的變數是什麼？這個問題並非你想像的理所當然。

在我們熟悉的語言如 C++ 裡，宣告變數，等同配置了一段記憶體，用以儲存資訊。在引用該段變數時，不管是讀取、修改、賦值，相當於在操作這段記憶體內的資料。也就是說在 C++ 裡，變數是某段記憶體的別名；這也說明了為什麼 C++ 需要你給出型別才能宣告，否則電腦根本不知道該配置多少記憶體給這個變數。

在 Python 裡，任何東西都是物件，而變數僅是從「名稱」到「物件」的映射。在 Python 裡對一個變數賦值，代表了你將這個名稱「指向」到某個物件上。因此，在 Python 裡變數沒有型別。你可以隨時隨地將一個名稱指向至另一個物件。

為了方便示例，這裡介紹 id 和 is。id(foo) 會將傳入變數所指向的物件的 id （可當作記憶體位址）印出來。而 a is b 會比較兩者所指向的物件，是否為同一實體，也就是 id(a) == id(b)。

1
2
3
4
5
>>> a = 'starbuststream'
>>> id(a)
4351113008
>>> a is a
True

對一個變數，你可以做的事情包含：

1. 引用它

讀取和修改的行為，都算是引用。

1
2
3
4
5
6
a = 2
b = 3
print(a+b)  # 引用 a 和 b

owo = []
owo.append(1)   # 引用 owo

2. 指向至一個物件上（賦值）

= 運算子做的就是賦值。= 將一個名稱指向一個物件。如果指定的命名空間不存在這個名稱，那 Python 會創建一個新的。（命名空間為名稱的集合）

1
2
3
4
5
6
owo = []    # 將 owo 賦值
owo.append(1)

a = 2   # 將 a 賦值
a = a+2 # 將 a 賦值，右邊 a+2 引用 a
print(a)

如果用變數將另一個變數賦值，則兩個變數會指向同一個物件：

1
2
3
4
>>> a = 'starbuststream'
>>> b = a
>>> a is b
True

3. 將其從命名空間刪除

我們可以在指定的命名空間新增名稱，反之我們也可以透過 del 關鍵字把它刪除。

1
2
3
4
5
6
>>> a = 'starbuststream'
>>> del a
>>> print(a)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'a' is not defined

要注意的是：變數僅僅是一個名稱。我們將這個名稱刪除，實際上不會影響到記憶體裡的物件。對於字串物件 'starbuststream' 來說，僅僅是少了一個參考至它自己的變數而已。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> b = a = 'starbuststream'
>>> id(a)
4351113008
>>> id(b)
4351113008
>>> del a
>>> a
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'a' is not defined
>>> b
'starbuststream'
>>> id(b)
4351113008

題外話：Python 的回收機制中，當參考至某物件的數量等於零，也就是再也不可能透過任何方式引用它，它就有可能被刪除。

關於物件的值：Immutable vs Mutable

根據官方文件，每個物件都由 id, type, 和 value 組成。有些物件的值是可變的，有些則否。這引出了今天的主題：Immutable vs Mutable。

immutable 不像 mutable 物件，提供了可以修改成員屬性的方法。這代表 immutable 是唯讀的。immutable object 有：int, str, float, bool, tuple, frozenset 等。而常見的 mutable object 有 list, dict, 以及自訂 class 等。

這不符合我們的經驗，int 怎麼可能不可修改？

1
2
3
4
5
6
>>> a = 1
>>> id(a)
4348150000
>>> a += 1
>>> id(a)
4348150032

如果理解上個小節所說的，應該可以想到：a += 1 實際上做的事，是 a = a+1。其中 a+1 是對 a 的引用，並且生成了一個新物件 int(2)；= 則是把 a 重新指向到右側生成的新物件。

對於引言例子的原理就豁然開朗了。當我們使用 my_lis？t.append() 時，我們僅是引用；而使用 my_int += 1 時，我們其實進行了隱性的賦值。

1
2
3
4
5
6
7
8
9
10
>>> a = []
>>> b = a
>>> b.append(1)
>>> a
[1]
>>> a = 1
>>> b = a
>>> b = 2
>>> a
1

若我們將兩者都做賦值，mutable 跟 immutable 的表現是完全一樣的：

1
2
3
4
5
6
7
8
9
10
>>> a = []
>>> b = a
>>> b = ['owo']     # 將 b 指定至另一個物件
>>> a is b
False
>>> a = 1
>>> b = a
>>> b = 2      # 將 b 指定至另一個物件
>>> a is b
False

作用域和 Mutablility 的關係

1
a = 1

引用某個變數時，Python 會先查找當前命名空間 local 裡是否有這個名稱，如果沒有則一層一層往外找，直到 global，接著是 builtin。賦值時，若 local 有這個名稱沒事；若沒有，Python 也不會往外找，而是直接新增一個名稱在 local。換句話說，外層的名稱是唯讀的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> a = 0
>>> def show():
...     print(a)
... 
>>> show()
0
>>> def add():
...     a += 1
... 
>>> add()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in add
UnboundLocalError: local variable 'a' referenced before assignment

執行 a += 1，也就是 a = a+1 時，a 首先被新增到 local 命名空間，接著 a+1 引用剛被新增的名稱 a。此時會發現 a 尚未被指定到任何一個物件！反之，若改為 list 並在函式內執行 append，因為是引用，不會在 local 裡新增名稱，也就可以直接修改到外面的 list 了。

global 和 nonlocal 關鍵字。

解法很簡單。global 語句宣告了該名稱位於全域，Python 不需要在苦苦搜尋該名稱。

1
2
3
4
5
6
7
>>> def add():
...     global a
...     a = 1
... 
>>> add()
>>> a
1

nonlocal 語句宣告該名稱不在 local 和 global 裡。由於作用域覆蓋當前的 nonlocal 命名空間可能有很多個，使用 nonlocal 需要明確的指出該名稱位於哪一個命名空間，只能對預先存在的名稱做 nonlocal 宣告。

1
2
3
4
5
6
7
8
9
10
11
>>> a = 1
>>> def outer():
...     a = 2
...     def inner():
...             nonlocal a
...             a += 1
...     inner()
...     print(a)
... 
>>> outer()
3
1
2
3
4
5
6
>>> def outer():
...     def inner():
...             nonlocal qwq    # 只能對預先存在的名稱做 nonlocal 宣告
... 
  File "<stdin>", line 3
SyntaxError: no binding for nonlocal 'qwq' found

Python 的參數傳遞

Python 的參數傳遞，相當於做了一次賦值。將變數作為容器的語言中，有 call by reference 或 call by value 的概念，在 Python 中則沒有。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> a = 1
>>> def add(x):
...     x += 1      # 賦值
... 
>>> add(a)   # 相當於 x = a
>>> a
1
>>> b = []
>>> def ap(x):
...     x.append(1)     # 引用
... 
>>> ap(b)   # 相當於 x = b
>>> b
[1]

為什麼需要有 Immutable Objects?

Immutable Objects 有以下優點，但我現在還沒體會必要性：

  • 保證一但被創建出來 hash 值就不會改變，才能做為 hash table 的 key

  • 唯讀保證了多線程安全

  • Python 的機制使多個變數會指向同一個物件，不變性保證了每個變數參考到的物件始終相同

發表於 更新於 分類於

本篇尚在施工中...

本篇以時間順序呈現特殊選才的準備、面試過程（流水帳）。內容以單純紀錄過程和感想為主。

書審

我大概從十月開始寫備審資料，最早繳件的是清大，截止前幾天才真正把備審做完交件。 每間學校都有自己的格式，但都大同小異，我是先做一份完整的備審，再根據每個學校修改。 大綱參考自 Koios1143 學長的樣式，連美編風格都差不多。

我沒有做特別的美術、放 icon 之類的，後來觀察也確實可以得知資工系教授不太在意這個。誇張地說，我覺得做備審可以不用太認真，因為書審成績絕大部分會反應自競賽經歷。拿省下來的時間去讀《Introduction to Algorithm》，然後祈禱教授會問到，可能會更划算。

面試

面試的準備分成自我介紹、問答兩個方向。

自我介紹我一開始沒有特別準備，是兩手空空去找輔導室模擬面試時 free style 出來的。後來最先面試的清大資工開放使用簡報做自我介紹，因此才特別準備了簡報和講稿。內容以“競賽經歷”和“個人特質”為兩個方向。但後來清大資工的學長告訴我們，自我介紹應該以“未來”為主，而不是條列過去的經歷。

另外我看著自己的備審資料，寫下大約五十個可能被問的問題，另外也記錄下一些網路上找到學長分享的面試問題。寫完之後就

面試服裝，一件看起來版型和材質比較休閒的深灰色西裝外套，一件灰色的襯衫；下面是黑色的九分褲。這樣的穿著應該算蠻正式了，去清大面試時看到有人穿帽Ｔ加牛仔褲、制服等。

成大資工

成大資工甲組為競程取向，今年二階沒有面試，只有上機考佔 50% 成績。 題目偏裸、經典：

  • pA：差分序列
  • pB：Sliding window 極值
  • pC：查詢連通塊最大值，支援拔邊，可離線
  • pD：線性基
  • pE：給定幾個邊一定要用上的次小生成樹，還要查詢樹上點對路徑

第一名 369 分，我 181 分第六，燒超慘。

pA AC 之後，因為 pC 有看過，所以直接刻滿分解，結果 0 分。

接下來開 pB。根據 pC 的經驗，雖然知道是 Sliding Windows，但我先寫了一個 \(O(n)\) 查詢最極值的版本。 pD 很順利的寫了位元 DP，但另一子題 \(2^n\) 刻爛了。

又回去 pB 寫了一顆 TLE 的線段樹。我不信邪再次帶 log，用 priority_queue 再次 TLE。最後一個小時，就在處理 pB 極值、de pC 的 bug、解決 pD RE 的問題中渡過了。臨死前刻的 Sliding Window，是在比賽快結束時 judge 死掉後上傳的。結果最後也沒 AC。

心得

上機考就是全憑個人實力了，但只要經過一定程度的訓練其實都很有機會。以今年來看，參加複試者其實實力參差不齊。也是這個原因，讓我在大失常後依然名次保持得很前面。

清大資工

報到之後就在考生休息室等工作人員叫名字。考生休息室很適合補眠，雖然休息室裡的人大部分都是熟面孔，但聽不到談話的聲音。正好昨天風太大只睡了三個小時，精神不是很好。

大家穿著風格各異，最樸素的是襯衫長褲，也看到有人穿帽Ｔ跟牛仔褲。我原本西裝外套裡只有 T-shirt，但看到前面兩個換上全套西裝後，我也去把備用的灰色襯衫換上了。

叫到名字之後，會被工作人員領去相鄰的兩間面試教室走廊稍加等待。坐在那裡有種待宰羔羊的感覺。那裡有兩個學姊駐點，她們會找你聊天，或聊天給你聽。我有跟她們講一點話，對舒緩情緒的幫助還是很大的，非常感謝她們。

第一間教室

第一間教室配置如下：你會站在投影幕旁，前方是圍成ㄇ字型的桌子，且有兩個教授手上拿著資料坐在ㄇ字的一側。投影幕上已經放好你的簡報了，跟教授問好後隨即拿起桌上準備好的簡報筆開始五分鐘自我介紹。過程意外的並不緊張，其中一個教授比較認真看你報告，另一個就是邊聽邊認真看資料了。

自我介紹結束後教授會輪流問你一些問題：

教授Ａ：你的奧林匹亞表現得比能力競賽還要好，這兩個對你來說有什麼差別嗎？

我：奧林匹亞，尤其是入營考，子任務除了分數給的很甜，也具有很強的引導效果。這對我來說是幫助我發揮的更好的特性。

教授Ａ：如果加入 APCS 做比較呢？

我：APCS 的題目考的核心觀念都非常經典，也不需要太多拆包裝的過程

教授Ａ：你剛剛分析的 APCS 題型，對你來說是優勢還是劣勢？

我：我認為是。相對於想法，我認為我更擅長實作

教授Ｂ：南區第五有進全國嗎？那發生什麼事，為什麼沒有進全國？

我：南區賽前四才進全國，蠻可惜的。其中一題題序說要用 \r 來做分隔符，我就跳過了。一題我們懷疑測資有誤。另一題我有想出解法，但看錯測資範圍，將 \(7!N^2\) 估成 \(N!N^2\)。

教授Ｂ：那題 \(N!N^2\) 的題目你後來有想出更好的方法嗎？

我：沒有，後來我也因為沒有部份分就沒有丟這題了。

教授Ａ：你們學校的資訊社有悠久的競賽風氣，你怎麼把他傳承給下一屆？

我：要先給剛進入社團的學弟們一個願景和目標，讓她們了解她們有哪些競賽、活動可以選擇參與。另外跟學長培養良好的感情也很重要，每年我們透過舉辦寒暑訓都可以讓學弟和學長們交流

第一階段結束後，會在外面坐，再進入第二間教室。

第二間教室

第二間教室會讓你站在白板面前，兩位教授就在白板前的長桌後（一位是在選訓營看過的韓永楷教授，全程面帶大大的笑容）。且桌上放著許多信封袋。接著他們會要你抽一份，作為你的專業問題。我抽到的問題是：

請提出可以依字典序輸出 \(N!\) 種排列的演算法。

當下看到題目就知道涼了。題目紙上標註著基礎，還要求你把握時間作答，以作答第二題，但這題目一看就注定燒雞。

在教授確認完你清楚題意後，就會要你解答。首先我提出了以 vis[N] 配合 dfs 的方法，複雜度 \(O(N \cdot N!)\)。教授問我有沒有更好的方法，可以去掉 \(N\)。

然後我就燒雞了，只說可以用 set<int> 查找剩餘元素之類的東西。

教授問了我下個問題，打算引導我解答：

教授Ｂ：next_permutation 要怎麼實作？

接下來燒的更慘。教授不停的舉 case ，然後協助我模擬 next_permutation（我還寫錯好幾次）讓我觀察規律。最後才在教授的幫助下，得出結論：由後往前，找到第一個 \(a[i]<a[i+1]\)，接著在 \([i+1,n]\) 中找到大於 \(a[i]\) 中最小的，把它移到 \(i\)，後面就從小排到大。

我得出結論後時間也差不多了，教授讓我問他們問題：

問：清大在合併竹教大之後，與其他學校相比在師培資源有什麼優勢呢？

教授很認真的給出答覆，我原本以為資工系的教授對這個可能不會了解的太詳細，會被認為我問了怪問題：

教授Ｂ：最顯著的差距是老師數量。在清大要選到師培課程會簡單許多，不用擔心修不到課。另外清大本身的多元性也是很大的優點，你會在課程裡遇到其他來自不同領域的同學，這是其他學校比較沒有的。你未來想當正職的老師嗎？

我：可能不是首選，但是一個優先度很高的選項。

心得

清大資工整體的面試體驗很棒，面試教授中沒有黑臉。第一教室的教授並不會問刁難你的問題，問題都蠻切中你備審的。第二間教授在你卡住時會很耐心的引導你。但如果你表現像我一樣差到還會特別感嘆教授的耐心，那面試大概也沒了......

師大資工

我們在報到前，在師大校園中的椅子上等。報到後就坐在考生休息室裡，不大，但有一些大沙發可以坐。

工作人員叫名字後帶上二樓，流程和配置跟清大大同小異：兩間教室、走廊上有椅子，但學姊少了一個。

師大學姊也會找你聊天，但聊的就比較刻意了，感覺像專門來緩解情緒的。相較之下，那兩個清大學姊本來就講得很開心，才順便邀你加入話題，自然許多。

第一間教室

第一間教室有兩位教授，表情非常和藹可親，還特別告訴你不要緊張。

以簡報自我介紹完後，他們會請你接著坐到頭影幕前的椅子，到他們來問問題：

教授Ａ：你可以詳細說明妳是怎麼準備 TOI 初選的嗎？

我：略（我照著備審講了一段，提到如何準備初選）

教授Ｂ：你有打過 MyFirstCTF，那有進 AIS3 Summer Camp 嗎?

我：沒有，他總共取 20 名進 AIS3，我是 28 名

教授Ｂ：HITCON Education Defense 時，你有什麼貢獻嗎？

我：沒有，因為我們隊友社內網管專長，所以大部分的工作是他做的

教授Ｂ：那紅隊採取了哪些攻擊手法？你們拿到第三名相當不錯

我：我們其實運用了比賽的漏洞，因為他有給出管理虛擬機的界面，因此當紅隊打進來的時候只要把她重新開機就好了

教授Ｂ：你們是寫程式讓他開機嗎？

我：我們在管理界面上快照之後，手動復原

教授Ａ：有什麼問題要問我們的嗎？

問：師大舉辦了很多程式競賽，例如全國賽、TOI、APCS。如果有幸就讀師大，不知道有沒有機會擔任出題、驗題等工作人員？

教授Ａ：我想第二間教授的問題可以詳細的回答你，這是他負責的，若你能參與他會很高興。那還沒有其他問題？

我：暫時沒有

第二間教室

第二間的兩位教授不是和藹可親類型的，但看得出來是抱著蠻愉悅的心情當考官。

一進來他就問你，上一間有沒有問題沒有得到解答的。所以我又問了一次。

教授Ａ：上一間都把問題丟給我們欸....當然，我們在 TOI 也有需要輔導員，都很歡迎

接著是噩夢的開始，由於缺乏事前的準備，也可能是清大面試讓我放下戒心了，我的表現非常糟糕。平常練習沒有的症狀都出現了，身體變得非常僵硬，反應呆滯，還會前後搖晃身體，看地板。

教授Ａ：你在這裡待過兩個禮拜，應該對師大很了解，不需要我多做介紹吧？

我：我只對上課的教室跟學餐比較熟而已......

教授Ｂ：要進 TOI 非常不容易，你的練習時間是怎樣？

我：一天大約三小時以上

教授Ｂ：那課業怎麼辦？

我：我平時的時間分配以練習演算法競賽為主，到段考前一週才會翻開書

教授Ｂ：那你成績怎樣？

我：我的段考成績都在班排中間偏上，但算上平時成績之後就比較低了

教授Ｂ：在南一中中間偏上也還不錯了

教授Ａ：如果特選落榜，你有考慮過備案嗎？

我：我應該會去考 APCS 組

教授Ａ：那你預估的成績大概會上哪些學校？

我：應該是中字輩吧

教授Ａ：師大對你來說有什麼特別的意義？也就是說，跟其他學校比起來，為什麼你選擇師大?

這個最基礎的問題我雖然有稍微想過，但講出來才發現問題大了。

我：清交資源豐富，但我覺得希望渺茫......(陷入一段很長的沈思，我發現我說錯話了，不知道該怎麼接下去)。因為師大是師培體系...我又對教育蠻有興趣的....我覺得教學是很快樂的事情.....

教授Ｂ：你有說到你對影像處理有興趣，為什麼？

我：攝影是我的興趣之一，所以會很常接觸 Photshop、Lightroom 之類的軟體。選擇影像處理可以結合我兩個興趣。

教授Ｂ：你對影像處理的了解，對你拍照時有沒有產生影響？

我：有。在拍照時就要考慮到在後期時可能會怎樣調整他，例如動態範圍。攝影有點像做菜，拍照其實只是在搜集食材，後期的部分還是更重要

教授Ｂ：關於影像處理，大學之後，會有一些實作的東西。有什麼功能是你目前需要，但市面上的產品沒有辦法滿足你的？

我：我可能要想一下（沈思.....。我覺得下個方向應該是結合人工智慧，去補足在物理上受到限制沒有辦法捕捉到的細節。拍照時的有些資訊其實在光學跟感光元件發展到極限之後沒辦法捕捉到，用人工智慧就可以把這些細節算出來。

教授Ａ：你有什麼問題要問的嗎？

我：師大的程式競賽成績很亮眼，我有問過清大其實沒有在這塊投入很多資源，不知道師大有沒有提供相關課程之類的？

教授Ａ：我們其實沒有特別開相關的課，最重要的還是風氣。師大打競程的人非常多，我們一年只收幾十個人，但比賽能派十隊出去。演算法競賽也是很花時間的，如果你投入很多時間在打比賽，身邊的人卻都在唸書，很難堅持的下去。

心得

這場面試完完全全只是我缺乏準備，讓我的回答既猶豫，看起來也沒有很想讀師大。

師大面試體驗也很棒，除了教授和工作人員人很好，面試完後系主任還一直跟我們聊天邊推銷師大，而且過程她好激動。

另外，有一個疑點：教授沒有問我演算法的專業問題。並且，其他人據說有被瘋狂推銷師大，但是我沒有QQ。不過我有聽到幾次『你如果能就讀師大對我們來說會很有幫助』，希望還是有機會能上師大。

中央資工

開始面試前會坐在考生休息室裡，就像一般教室的座位一樣，一格一格的。工作人員一次從考生休息室裡帶兩名上去二樓面試。據我所知，今年和去年的面試順序都是按照初試成績排的。

面試過程

面試只有一間教室，並且得先站在門口等前一個人結束。因為隔音不是很好，所以能稍微聽到前一個人在報告的聲音。在我前面一位的講話語調跟國文朗讀有同個味道，是經過幾十次練習的味道，讓我特別緊張。

接著輪到我。敲門進去、跟教授打招呼、走到講台前電腦開簡報、自我介紹。中央沒有提供簡報筆，而是自己把前一天以電子郵件提供的簡報開起來，又我提供的是 pdf，沒辦法全螢幕放映，只好在筆電上捲動。這影響到了自我介紹時的流暢度。自我介紹長度為三分鐘。在我報告時，兩位教授在看資料，另一位攤在椅子上，目光多放在我的簡報。

報告結束，接著輪到教授問問題：

教授Ａ：你可以講一題令你印象深刻的 APCS 題目嗎？

我：我最有印象的是上上次的 APCS 第三題。題目要求查詢區間極值和位置，不帶修改，並且查詢範圍只會變小。印象深刻的原因是我聽到的大多數人都是用資料結構解決的，但 APCS 的第三題應該不需要複雜的資料結構才對。這題我使用全國賽出現過的概念，只要事先將答案排序好，後來在判斷這個解有沒有過期就好了。

教授Ａ：你的 APCS 是觀念五實作四嗎？

我：我是觀念四實作五

教授Ａ：通常都是觀念比實作高吧？

我：透過長期的練習我的實作能力相對會比較強，並且熟悉自己風格的程式碼。相對的我對於不同邏輯的程式閱讀就會比較困難，這也是我想解決的事，因為他在教學和閱讀資料上會帶來許多不便。

教授Ｂ：你有還有報名其他的學校嗎？

我：有

教授Ｂ：你有報名成大嗎

我：有

教授Ｂ：成大是不是要考八小時的程式？

成大有分成甲組跟乙組，甲組是演算法競賽的考試，時長三小時；乙組考的是開發，時長八小時。我參加的是甲組。

教授Ｂ：那你機會應該蠻大的吧，畢竟演算法是你的專長。

我：我不太確定，因為成大的上機考我認為我表現不是令自己很滿意。

教授Ａ：成績看起來還不錯，資訊也都接近滿分。感覺你自我介紹就講的很完整了，那就先到這裡。

我：謝謝教授

心得

中央的面試教授感覺不是很上心。我認為這些問題並不能讓我感受到，他們想透過面試更好的評斷要不要收這個學生（當然也可能因為我是被拿來充數的炮灰）。聽說有其他同學被問更沒有深度的問題。

台南到桃園的通勤費其實也不少，讓我感覺很不值得。唯一可以慶幸的是，有拿到免洗餐具作為紀念品。

發表於 更新於 分類於

Default Code

1
2
3
4
5
6
7
8
9
10
typedef pair<int,int> vec;
vec operator - (vec p){ return {-p.ff, -p.ss}; }
vec operator + (vec p, vec q){ return {p.ff+q.ff, p.ss+q.ss}; }
vec operator - (vec p, vec q){ return {p.ff+q.ff, p.ss+q.ss}; }
vec operator * (vec p, int q){ return {p.ff*q, p.ss*q}; }
vec operator / (vec p, int q){ return {p.ff/q, p.ss/q}; }
int cross (vec p, vec q){ return p.ff*q.ss - p.ss*q.ff; }
int dot   (vec p, vec q){ return p.ff*q.ff + p.ss*q.ss; }
int abs2 (vec p){ return dot(p,p); }
double abs (vec p){ return hypot(p.ff,p.ss); }

常用

內積定義、正弦定理、夾角

1
2
cross(v1,v2) = abs(v1)*abs(v2)*sinθ
dot(v1,v2) = abs(v1)*abs(v2)*cosθ
  • 用 asin 可以 acos 算出弳度
1
2
3
4
5
6
7
dot(v1,v2) < 0, θ < 90
dot(v1,v2) = 0, θ = 90
dot(v1,v2)  > 0, θ > 90

cross(v1,v2) > 0, v1 到 v2 逆時針
cross(v1,v2) = 0, v1 平行 v2
cross(v1,v2) < 0, v1 到 v2 順時針
  • 粗估順逆時針、夾角大小

點到直線距離

1
點到直線距離 = cross(v1,v2)/abs(v2)

發表於 更新於 分類於

差分約束模板題

Solution

  1. \(x_i - x_j \leq w\)
1
2
3
4
xi - xj <= w
xi <= xj+w
若 xj 已知，則 xi 必須要被縮小至至少 xj+w 以符合不等式
可以視作最短路中 relax 的過程
  1. \(x_i-x_j \geq w\)
1
2
3
xi - xj >= w
xi >= xj + w
如果 xi < xj+w 則 relax (最長路)
  1. 同時存在 \(x_i - x_j \leq w\) 和 \(x_p - x_q \geq w\)
1
2
xp - xq >= w
xq - xp <= -w
  1. \(x_i - x_j = w\)
1
2
3
同時符合
xi-xj <= w
xi-xj >= w
  1. 初始假設
1
2
1. xi-xj <= w, 得到最大解，假設 xi <= 0, 得到 xi-0<=0，由原點 0 連向 xi 邊權為 0
2. xi-xj >= w, 得到最小解，假設 xi >= 0, 得到 xi-0>=0，由原點 0 連向 xi 邊權為 0
  1. 無解
1
建出來的圖存在負環，會重複更新 (永遠無法滿足條件)

性質

1
xi-xj <= w 做最短路，並且得到最大解 (xi 太大時才會變小)
1
xi-xj >= w 做最長路，並且得到最小解 (xi 太小時才會變大)
  1. 確認不等式方向 xi-xj >= w or xi-xj <= w
  2. 得出初始條件

發表於

本篇尚在施工中...

實作細節

負還會影響其他地方 必須不斷往回走 n 次，才會是在環上的點

發表於 分類於

作法一：兩個 multiset

以兩個動態排序的資料結構 \(L\) \(R\)，分別維護前半小、後半大的，查詢時輸出中間切開的地方就行。 仔細地說，有奇數個元素時，中位數是 \(\lceil \frac n 2 \rceil\)，偶數個時，中位數是 \(\frac n 2\)。 使 \(L\) 在 \(n\) 為奇數時，比 \(R\) 多一個，查詢時輸出 \(L\) 的最後一個元素。

這裏我踩到一個坑，就是 S.erase(x) 會把所有 x 刪除掉。 若只要刪除一個 x，使用 erase(S.lower_bound(x))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int n, k, a[N];

multiset<int> L, R;

void era (int x)
{
    if (L.find(x) != L.end())
        L.erase(L.lower_bound(x));
    else
        R.erase(R.lower_bound(x));
}
void ins (int x)
{
    if (L.empty() || x<=*last(L))
        L.insert(x);
    else
        R.insert(x);
}
void bal ()
{
    while (R.size()>L.size())
    {
        L.insert(*R.begin());
        R.erase(R.begin());
    }
    while (L.size()-1>R.size())
    {
        R.insert(*last(L));
        L.erase(last(L));
    }
}

signed main()
{
    cin >> n >> k;
    rep(i,1,n) cin >> a[i];
    rep(i,1,n)
    {
        ins(a[i]);
        if (i>k) era(a[i-k]);
        bal();
        if (i>=k) cout << *last(L) << "\n "[i+1<=n];
    }
}

作法二：在值域線段樹上二分搜

  • 找到最小的 \(x\) 使 \(cnt[1]+ \dots +cnt[x] \le \lceil \frac n 2 \rceil\)

以 \(cnt[x]\) 代表目前 \(x\) 出現幾次。 當 \(n\) 為奇數，取 \(n/2+1\)。當 \(n\) 為偶數，取第 \(n/2\) 個，因此找到第一個包含 \(\lceil \frac n 2 \rceil\) 的 \(cnt[1]+ \dots + cnt[x]\)

  • 在線段樹上二分搜：\(query(u,k)\) 所代表區間 \([l,r]\) 中，最左的 \(i\) 使得前綴至少為 \(k\)
1
2
3
4
if (sum[l[u]] >= k)
    return query(l[u],k)
else
    return query(r[u],k-sum[l[u]])
  • 離散化

因為值域達 \(10^9\)，並且只關心數字間大小關係，所以離散化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int n, k, a[N];

int v[N], m;
void lisan()
{
    rep(i,1,n) v[i] = a[i];
    sort(v+1,v+1+n);
    m = unique(v+1,v+1+n)-v-1;
    rep(i,1,n) a[i] = lower_bound(v+1,v+1+m,a[i])-v;
}

struct Seg
{
    int tr[N<<2];
    void modify (int p, int x, int u=1, int l=1, int r=m)
    {
        if (l==p && p==r)
        {
            tr[u] += x;
            return;
        }
        int mid = (l+r)/2;
        if (p<=mid) modify(p,x,u*2,l,mid);
        else modify(p,x,u*2+1,mid+1,r);
        tr[u] = tr[u*2] + tr[u*2+1];
    }
    int query (int x, int u=1, int l=1, int r=m)
    {
        if (l == r)
            return l;
        int mid = (l+r)/2;
        if (tr[u*2] >= x) return query(x,u*2,l,mid);
        else return query(x-tr[u*2],u*2+1,mid+1,r);
    }
} seg;

signed main()
{
    cin >> n >> k;
    rep(i,1,n) cin >> a[i];
    lisan();
    rep(i,1,n)
    {
        seg.modify(a[i],1);
        if (i > k)
            seg.modify(a[i-k],-1);
        if (i>=k)
            cout << v[seg.query((k-1)/2+1)] << "\n "[i+1<=n];
    }
}

作法三：支援 find_by_order 的資料結構

可以自己刻一顆 treap，或是使用 pbds。

食用 pbds 前：

1
2
#include <ext/extc++.h>
using namespace __gnu_pbds;

然後快樂的 AC 他：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef tree<
    pii,
    null_type,
    less<pii>,
    rb_tree_tag,
    tree_order_statistics_node_update
> trii;

int a[N], n, k;
trii tr;

signed main()
{
    cin >> n >> k;
    rep(i,1,n) cin >> a[i];
    rep(i,1,n)
    {
        tr.insert({a[i],i});
        if (i > k)
            tr.erase(tr.lower_bound({a[i-k],0}));
        if (i>=k)
            cout << tr.find_by_order((k-1)/2)->ff << "\n "[i+1<=n];
    }
}