0%

演算法競賽入門三階段

  1. 從零到一:演算法競賽會用到的基礎語法

    • 介紹競賽必定要會的語法,讓你不再困擾該學什麼!
    • 對應程度:APCS 實作三級
    • 預計學習時數:25 小時
  2. 從一到十:演算法競賽會用到的基礎算法

    • AP325 講義 by 吳邦一教授
    • 到底演算法競賽的演算法,指的是哪些呢?
    • 對應程度:APCS 實作五級
    • 預計學習時數:100 小時
  3. 十以後的世界:演算法競賽無止盡的追尋

    • 板中講義 by 蔡旻諺學長
    • 什麼,你說上面你都學會了,你確定嗎?
    • 對應程度:TOI 一階以上
    • 預計學習時數:250 小時 up

這邊會有什麼?

我幸運的拿到了 IOI(國際資訊奧林匹亞) 2020 的銀牌,但在選訓營中,發現能進入選訓的高中生,大多都來自那些資訊社團發達的學校,如建中、實中、南一中、附中、成功等,在資訊社不活躍的學校,則幾乎沒有人進入奧林匹亞選訓營。回想起自己的學習過程,我認為關鍵在於新手入門難度。

包含 TOI(台灣資訊奧林匹亞) 在內的 OI 競賽入門門檻不低,於初期若沒有好的引導人(通常為高中資訊社團),常會多走許多歪路,或者根本不知道應該要學什麼、什麼不必學,若買了一本 C++ 的書,然後一味的啃,會發現其實演算法競賽其實不需要對語法那麼熟悉。網路搜尋演算法競賽,第一本出現的書籍:打下好基礎:程式設計與演算法競賽入門經典,對新手來說也過於艱澀,且題目與台灣目前的命題趨勢並不相同。

這裡將會整理自己兩年來的演算法學習經驗,目標成為一本好懂、實用的演算法競賽書籍,期待能帶領更多年輕高中生,踏入這個正在台灣發展中的有趣領域!

演算法競賽,重要的是思考,而不是過多不必要的語法

目標受眾

  • 完全沒寫過程式,但對數學有興趣,想嘗試演算法競賽
  • 略有程式基礎,但不了解演算法競賽,或不知道競賽上有哪些常出現的演算法
  • 非大校資訊社員,卻也想參加演算法競賽、進入全國賽以及選訓營

完結啦!

你已經學會了拿下 IOI 金牌所需要的所有語法了!是不是很簡單呢?

不知道看到例題的感想,是覺得超級簡單、或是難到完全想不到、或是剛剛好呢?

在後段的 STL 章節裡,我增加了例題的難度,四星的題目約是全國賽門檻等級,也就是說,如果你能不依靠詳解解出四星的題目,而你又幸運的不住台北,那你可能已經有參與全國賽的實力了喔!

五星以上的題目們,就真的非常難了。其中在 set 中一題被我標為 8 顆星的直升機抓寶,雖然程式只有十餘行,不過這題在當年的全國賽上,可是只有五個人解出來的大難題呢!

當然,如果你是初學者,寫不出太難的題目不用灰心。擺放高級題目的目的,僅僅是在說明,只需要如此簡單的語法,就能解決這麼多問題而已,對於初學者而言,能了解教學中的概念,並寫出三顆星以下的題目,就算是相當不錯的了!

接下來

你已經有了基礎的知識,可能也對於演算法有了初步的了解,之後要做什麼呢?

參加一場 Codeforces Div.3 或者是 AtCoder 的 Beginner Contest 吧!如果可以,請試著在結束後查看出題者提供的題解。

也可以試著參加一場免費的 APCS 考試,反正免費,考爛了也不虧。

可以去刷一些題目,檢驗自己的學習成果。如果不知道從何寫起,可以參考一下 TOJ 上的高一生程式競技排名賽歷屆試題。

如果覺得簡單的話,恭喜你,你已經能挑戰下一階段的 AP325 了!

礙於時間關係(大學真的太忙了),以及之後的教學已有完善資源,我的教學就在這裡畫上句號,希望讀完這份講義的你能有所收穫!

bool 陣列

1
bool arr[1000005];

bitset

bitset 是特別優化過的 bool 陣列,時間與空間均較 bool 陣列少,其中以時間的影響最為顯著。

bitset 的語法如下:

1
bitset<1000005> b;

特別的地方是,<> 內放的是大小。

語法

跟 bool 陣列一樣

1
2
b[5] = 0;
b[4] = 1;

有一些特別的函式

1
cout << b.count() << '\n';

.count() 回傳 bitset 中 1 的個數。

1
2
3
4
b.set();
cout << b[1] << '\n';
b.reset();
cout << b[1] << '\n';

.set() 將所有 bit 設為 1,.reset() 將所有 bit 設為 0。

比 bool 陣列快的地方

bitset 可以進行位元運算!

位元運算的速度極快,大約可視為正常的 1/32 倍。因此 bitset 能做到一些沒有其他方法能做到的神奇事情。

但… 這些事情超少的,我也只在比賽中看過一題,然而就是那一題,讓我進了二階。那題稍微有點難,可能放在這不太適合,就先放其他題目吧!

TOJ 126

這題的重點是,要如何知道一個數是不是合理的。

假設現在合理的分數是(-2, -1, 0, 1, 2),有一題 2 分的題目,那麼在作答完這題後,可能的分數就是這題答對與這題答錯的聯集。

這題答對的話,可能的分數會變成(0, 1, 2, 3, 4),答錯的話,可能的分數會變成(-4, -3, -2, -1, 0),所以考慮答對跟答錯的情況,可能的分數是兩者的聯集,也就是(-4, -3, -2, -1, 0, 1, 2, 3, 4)。

假設把可不可能用 bitset 表示,bitset 中若第 i 項是 1,表示 i 是可能的分數,反之 0 是不可能,那麼,若原來的 bitset 是 b,答了一題分數為 2 的題目後,這個 bitset 就會變成 (b >> 2) | (b << 2)。

b >> 2 表示答錯的狀況,可能的分數右移兩格(-2, -1, 0, 1, 2) -> (-4, -3, -2, -1, 0), b << 2 表示答對的狀況,可能的分數左移兩格(-2, -1, 0, 1, 2) -> (0, 1, 2, 3, 4)。| 將兩者聯集起來。這樣的話,本來需要 N 次的操作,在 bitset 的使用下,變成只需要 N / 32 次了!

在位元運算時,bitset也不用擔心會 RE,超過的部分都會自動捨去,沒有問題!(但是可能會WA就是了)

另外,這題其實是一題經典問題:背包(knapsack)問題的一種變形,有興趣的話可以針對這個主題進行學習。之後應該也會有一篇專門的文章來介紹我所知道的背包問題們。

bitset 的使用時機非常少,但無可替代。

練習

TOJ 126

Hackerrank Acyclic Graph

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
// TOJ 126
// 因為index沒有負數,因此全部加上 10000 處理。
#include<bits/stdc++.h>
using namespace std;

int n, q, ans[20005];
bitset<20005> b;

int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
b[10000] = 1; // b[0] = 1
for(int i=1,x;i<=n;i++){
cin >> x;
b = (b >> x) | (b << x);
}
for(int i=20000,pre=i;i>=0;i--){
if(b[i]) pre = i;
ans[i] = pre;
}
for(int i=1,x;i<=q;i++){
cin >> x;
cout << ans[x+10000] - 10000 << '\n'; // cout << ans[x] << '\n';
}
}

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
// Acyclic graph
// 建議先了解 dfs 與 vector 存圖 以及 DAG
// 先備知識有點多 可以跳過 之後再回來
#include <bits/stdc++.h>
using namespace std;

bitset<50005> b[50005], vis;
int n, m, in[50005];
vector<int> E[50005];

void dfs(int x){
vis[x] = 1;
b[x][x] = 1;
for(auto i:E[x]){
if(!vis[i]) dfs(i);
b[x] |= b[i];
}
}

int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for(int i=1,a,b;i<=m;i++){
cin >> a >> b;
E[a].emplace_back(b);
in[b]++;
}
for(int i=1;i<=n;i++){
if(!in[i]) dfs(i);
}
int ans = 0;
for(int i=1;i<=n;i++){
if(b[i].count()*2>=n) ans++;
}
cout << ans << '\n';
}

從中間刪除?

如果我要刪除陣列最前最後的元素,可以用 deque 解決。

那,如果我今天要刪除陣列中間某個元素,或是在陣列中間插入某個元素,該怎麼做呢?

我們可以紀錄一個點的前、後方是誰,這樣的話,假設現在是1 -> 2 -> 3,如果我要刪除 2,我只要將 1 的後方指向 3、3 的前方指向 1,就能夠在 $O(1)$ 時間內完成刪除動作。

缺點

無法隨機存取,也就是說,無法快速知道當前的第 k 項是誰。只能知道頭、尾。

即使刪除一個元素只需要 $O(1)$,但是光是找到那個元素就要花 $O(N)$ 了啊。我要刪掉 2,但我不知道 2 在裡面的位置在哪裡,於是我只好從頭一個一個開始找,直到我找到 2,這也是非常慢的做法。

因此,linked-list 不太常被使用,雖然 STL 有 list 這個結構,但我還沒用過它。

唯一的用處

來看看這題:

ZJ 938

很明顯的,需要利用 linked-list 的概念來解決,只需要很簡單的刪除一個人後面的人就好。

那這題的瓶頸就在於,要如何維護一個人後面的人是誰。

一開始,每個人的後面都是自己的編號 + 1,當我刪除 1 後面的數 2 時,1 的後面就變成了原本 2 的後面 3,而其他人後面的數都不會被改變。

1
2
3
1 -> 2 -> 3 -> 4
1 -> X -> 3 -> 4 (2被殺)
1 ------> 3 -> 4 (1後面的人變成了原來2後面的人:3)

所以,我們開個陣列紀錄每個人現在後面是誰就好啦!完全不需要 STL 的 list 呢!事實上,list 根本沒有辦法做這題,因為找到一個人的位置需要 $O(N)$。

練習

ZJ b938

ZJ d718

★★★★ TIOJ 1225

★★★★ TIOJ 1930

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
// ZJ b938
#include<bits/stdc++.h>
using namespace std;

int n, m;
int nxt[1000005], dead[1000005];

int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++) nxt[i] = i+1;

for(int i=1,x;i<=m;i++){
cin >> x;
if(dead[x] || nxt[x] == n+1){
cout << "0u0 ...... ?\n";
continue;
}
cout << nxt[x] << '\n';
dead[nxt[x]] = 1;
nxt[x] = nxt[nxt[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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// ZJ d718
// 將沒有組別的人的編號設為 x + 10000,以避免與組混淆
// 題目沒說清楚,沒有組的人也有可能入列,例如範測 1 的 8
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n, team[1000005];
bool inq[10005];
queue<ll> q;
queue<ll> cur[10005];
string s;

void solve(){
fill(inq, inq+10001, 0);
fill(team, team+1000001, 0);
while(!q.empty()) q.pop();
for(int i=1;i<=10000;i++) while(!cur[i].empty()) cur[i].pop();
for(int i=1,x;i<=n;i++){
cin >> x;
for(int j=1,y;j<=x;j++){
cin >> y;
team[y] = i;
}
}
while(1){
cin >> s;
if(s[0] == 'E'){
int x;
cin >> x;
if(x > 1000000 || team[x] == 0){
q.push(10000+x);
}
else{
if(!inq[team[x]]) q.push(team[x]), inq[team[x]] = 1;
cur[team[x]].push(x);
}
}
else if(s[0] == 'D'){
if(q.front() >= 10000){
cout << q.front() - 10000 << '\n';
q.pop();
}
else{
cout << cur[q.front()].front() << '\n';
cur[q.front()].pop();
if(cur[q.front()].empty()){
inq[q.front()] = 0;
q.pop();
}
}
}
else break;
}
}

int main(){
ios::sync_with_stdio(0), cin.tie(0);
int t = 0;
while(cin >> n){
cout << "Line #" << ++t << '\n';
solve();
}
}
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
// TIOJ 1225
// 由小到大刪除元素
// 會使得結果變差的原因是,明明 b 能消掉 a,但 b 卻在 a 前就被消掉了。
// 為了不發生上述狀況,只要由小到大刪除元素就沒問題啦!
// 這題有 stack 的解,複雜度相同,但較好寫,可以試試想看看。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>

ll n, arr[1000005], fr[1000005], bk[1000005];

vector<pii> v;

int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=1;i<=n;i++) cin >> arr[i], fr[i] = i-1, bk[i] = i+1;
fr[n+1] = n;
bk[0] = 1;
arr[0] = arr[n+1] = 1e12;

for(int i=1;i<=n;i++) v.emplace_back(arr[i], i);
sort(v.begin(), v.end());

ll ans = 0;
for(int i=0;i<n-1;i++){
int idx = v[i].second;
if(arr[fr[idx]] > arr[bk[idx]]) ans += arr[bk[idx]];
else ans += arr[fr[idx]];

bk[fr[idx]] = bk[idx];
fr[bk[idx]] = fr[idx];
}

cout << ans << '\n';
}
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
89
90
91
92
93
// TIOJ 1930
// 麻煩的實作題,好好維護前面跟後面是誰
// 為什麼distribute操作不會 TLE 呢?
// 因為總共可能離開隊伍的人數 = 進入隊伍的人數 = N
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int n, m, a1, fr[2000005], bk[2000005];

ll dump;
vector<int> ans;

void insert(int a, int b, int c){
if(c == 1){
bk[fr[b]] = a;
fr[a] = fr[b];
fr[b] = a;
bk[a] = b;
}
else{
fr[bk[b]] = a;
bk[a] = bk[b];
bk[b] = a;
fr[a] = b;
}
}

void rebuild(int a, int b, int c){
bk[fr[a]] = bk[b];
fr[bk[b]] = fr[a];

bk[fr[c]] = a;
fr[a] = fr[c];
fr[c] = b;
bk[b] = c;
}

void distribute(int a, ll b, int c){
if(c == 1){
int now = a;
for(int i=1;i<=b;i++){
if(now == 0){
dump += b-i+1;
break;
}
ans.emplace_back(now);
bk[fr[now]] = bk[now];
fr[bk[now]] = fr[now];
now = fr[now];
}
}
else{
int now = a;
for(int i=1;i<=b;i++){
if(now == n+1){
dump += b-i+1;
break;
}
ans.emplace_back(now);
bk[fr[now]] = bk[now];
fr[bk[now]] = fr[now];
now = bk[now];
}
}
}

void solve(){
dump = 0;
ans.clear();
fill(fr, fr+2000005, 0);
fill(bk, bk+2000005, 0);

cin >> n >> m >> a1;
bk[0] = a1, bk[a1] = n+1, fr[a1] = 0, fr[n+1] = a1;


for(int i=1,k,a,b,c;i<=m;i++){
cin >> k >> a >> b >> c;
if(k == 1) insert(a, b, c);
else if(k == 2) rebuild(a, b, c);
else distribute(a, b, c);
}
cout << dump << '\n';
for(auto i:ans) cout << i << '\n';
}

int main(){
ios::sync_with_stdio(0), cin.tie(0);
int t; cin >> t;
while(t--) solve();
}

有 stack,有 queue

那理論上,應該要有一個 STL,同時具有 stack 跟 queue 的功能啊?

也就是說,要可以從前面跟後面拿東西、刪東西。

先介紹這個比較厲害的!

它不只可以從前面跟後面拿東西、刪東西,還可以隨時知道第 k 項是什麼!

也就是說,它其實更像是可以從前方插入移除的 vector。

語法

宣告:

1
deque<int> dq;

加入元素:

1
2
dq.push_back(1);
dq.push_front(5);

刪除元素:

1
2
dq.pop_back();
dq.pop_front();

此外,由於支援隨機存取,因此如 sort、lower_bound 等在 vector 可以用的函式,在 deque 中當然也可以用!

缺點

慢。

雖然各操作仍是 $O(1)$,但大約比 vector 慢 3 倍。

沒事不會用到它,沒事不要用到它。

對了,stack 跟 queue 其實是基於 deque 上的結構,也就是說,當你以為你在用 stack,其實程式幫你宣告的是 deque,即使你並不需要那些 deque 的功能。

因此,stack 跟 queue 跟 deque 一樣慢。

練習

★★★★TIOJ 1618

★★★★TIOJ 1566

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
// TIOJ 1618
// 搜尋 單調隊列
// 在任何時刻能看到的大樓,其高度必定由左往右遞減
// 用pop_front維護視力、pop_back維護高度遞減
// 可參考https://koios1143.github.io/2020/09/12/TOJ169/
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;

ll n, k, h[500005], b[500005];

int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
for(int i=1;i<=n;i++) cin >> h[i];
for(int i=1;i<=n;i++) cin >> b[i];

deque<pii> dq;
ll cur = 0, ans = -1e18, ansid = 0;
for(ll i=1;i<=n;i++){
while(!dq.empty() && dq[0].first <= i-k){
cur -= b[dq[0].first];
dq.pop_front();
}
while(!dq.empty() && dq[dq.size()-1].second <= h[i]){
cur -= b[dq[dq.size()-1].first];
dq.pop_back();
}
cur += b[i];
dq.emplace_back(i, h[i]);
if(cur > ans){
ans = cur;
ansid = i;
}
}

cout << ansid << " " << ans << '\n';
}
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
// TIOJ 1566
// 搜尋 單調隊列
// 維護區間最大值與最小值
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;

ll n, m, k, h[10000005];
deque<pii> mx, mn;
vector<pii> ans;

int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> k;
for(int i=1;i<=n;i++) cin >> h[i];

for(int i=1;i<=n;i++){
while(!mx.empty() && mx[0].first <= i-m) mx.pop_front();
while(!mn.empty() && mn[0].first <= i-m) mn.pop_front();
while(!mx.empty() && mx[mx.size()-1].second <= h[i]) mx.pop_back();
while(!mn.empty() && mn[mn.size()-1].second >= h[i]) mn.pop_back();
mx.emplace_back(i, h[i]);
mn.emplace_back(i, h[i]);
if(mx[0].second - mn[0].second == k){
if(i <= m) ans.emplace_back(1, i);
else ans.emplace_back(i-m+1, i);
}
}

for(int i=n+1;i<n+m;i++){
while(!mx.empty() && mx[0].first <= i-m) mx.pop_front();
while(!mn.empty() && mn[0].first <= i-m) mn.pop_front();
if(mx[0].second - mn[0].second == k){
if(i-m > 0) ans.emplace_back(i-m+1, n);
}
}

cout << ans.size() << '\n';
for(auto i:ans){
cout << i.first << " " << i.second << '\n';
}

}

堆(heap)

在 set 的章節中我們學過,set 可以隨時維護一個排序好的集合。但這相當難以實作,並且雖然複雜度是 $O(logN)$,但有著較大的常數。

如果,我不需要那麼多功能,只需要支援:加入一個元素、查詢最大元素、刪除最大元素這幾個操作,其實有個比較快的方法:heap

heap 介紹

查詢最大值

直接回傳 1 號節點數字。

刪除最大值

將 N 號移到 1 號位置,接著不停與其兒子比較,將其與較大的兒子交換,直到其無法再交換為止。

插入值

將新的值加入 N+1 號位置,不停與其父親比較,直到其值小於父親為止。

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
int heap[1000005], N = 0;

int mx(){
return heap[1];
}

void del(){
assert(N > 0);
heap[1] = heap[N];
N--;
for(int i=1,to;i*2<=N;i=to){
if(i*2+1 > N || heap[i*2] > heap[i*2+1]) to = i*2;
else to = i*2+1;
if(heap[i] > heap[to]) break;
swap(heap[i], heap[to]);
}
}

void ins(int x){
N++;
heap[N] = x;
for(int i=N;i>1;i>>=1){
if(heap[i/2] > heap[i]) break;
swap(heap[i/2], heap[i]);
}
}

而在 STL 中,有個名為 priority_queue 的結構,其內部便是以 heap 實作。它能夠做到 $O(1)$ 查詢最大值、$O(logN)$ 加入元素、$O(logN)$ 刪除最大值。

由於功能完全是 set 的子集,set 能任意刪而 priority_queue 只能刪除最大值,因此大多數時候使用 set,只有在 set 被卡時間以及特定演算法上會使用到 priority_queue。

priority_queue

宣告

1
priority_queue<int> pq;

加入元素

1
pq.push(1);

查詢最大

1
cout << pq.top() << '\n';

刪除最大

1
pq.pop();

更改比較函式

與 set 不同的是,priority_queue 其實有三個參數,分別為型態、底層容器、以及比較函式。若不需更改比較函式,宣告時只需第一參數即可,但若需要自訂比較函式,則需三個都寫出來:

1
priority_queue<int, vector<int>, greater<int>> pq;

另一個比較反直覺的東西,則是排在 priority_queue 頂的元素,其實是跟比較函式相反的。例如說,預設的 less<> 函式,排在最上方的反而是最大的元素。若要得到最小的元素,則須使用 greater<> 比較函式。

例題

把之前 set 題裡的拿來用

TIOJ 1161

★★★★TIOJ 1231

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
// 枚舉其中一個點數
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

priority_queue<int> pq;
int n, k;
pii arr[1000005];

void solve(){
while(!pq.empty()) pq.pop();
cin >> n >> k;
for(int i=1;i<=n;i++) cin >> arr[i].first >> arr[i].second;
sort(arr+1, arr+n+1);
int ans = 1e9;
for(int i=1;i<=n;i++){
pq.push(arr[i].second);
if(pq.size() > k) pq.pop();
if(pq.size() == k) ans = min(ans, arr[i].first + pq.top());
}
cout << ans << '\n';
}

int main(){
int t; cin >> t; while(t--) solve();
}
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
//TIOJ 1231
//從後面考慮回來
//最後一分鐘該放什麼呢?
//那倒數第二分鐘呢?
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;

priority_queue<ll> pq;

pii arr[100005];

int n, k;

int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=1;i<=n;i++) cin >> arr[i].second >> arr[i].first;
sort(arr+1, arr+1+n, greater<pii>());

cin >> k;
ll t = k, idx = 1, ans = 0;
priority_queue<int> pq;

while(t > 0){
while(idx <= n && arr[idx].first >= t){
pq.push(arr[idx].second);
idx++;
}
if(pq.empty()){
ans -= t - arr[idx].first;
t = arr[idx].first;
}
else{
ans += pq.top();
pq.pop();
t--;
}
}
cout << ans << '\n';
}

map 是什麼?

之前我們在陣列章節時,介紹了這樣一個語法:

1
2
a[5] = 1;
cout << a[5] << '\n';

這個的意思,是將 a 的第五項改變為 1,並將其輸出。當我們執行時,程式就去找: a 的第五項是什麼?再從索引(5)對到值(1),這是一種一對一的對應關係。

但是,能作為索引的東西,一定只有整數嗎?或者更進一步說,只有從 0 開始到陣列大小 - 1 嗎?能不能自訂?

是可以的,map 在做的,就是這件事情。map 能夠將一個鍵(key),對應到一個值(value)。

假設今天,我們想查詢一本書的資料,於是輸入了書名,我希望書的作者、出版社等等資訊就出現在眼前。在 C++ 裡,可以這樣寫:

1
2
3
4
map<string, string> author, publisher;
author["Le Petit Prince"] = "Antoine de Saint-Exupéry";
publisher["Le Petit Prince"] = "Gallimard";
cout << author["Le Petit Prince"] << " " << publisher["Le Petit Prince"] << '\n';

將書名作為 key,對應到一個作者與一個出版社。

map 的語法

新增與指派:

1
2
map<int, int> mp;
mp[5] = 45;

如果 key 不存在,則這是一個新增操作。如果 key 已存在,則是會將原來的值改掉,為一個指派操作。

查詢:

1
2
cout << mp[5] << '\n';
cout << mp[0] << '\n';

如果 key 已存在,會輸出索引所對應的值。如果索引不存在,則會先新增一個值為預設值的索引,再將其輸出。

刪除:

1
mp.erase(5);

與 set 相同。

遍歷:

1
2
3
4
5
6
map<int, int> mp;
mp[5] = 45;
cout << mp[0] << '\n';
for(auto i:mp){
cout << i.first << " " << i.second << '\n';
}

輸出結果:

1
2
0 0
5 45

遍歷時,會照著 key 大小由小到大輸出,型態是一個 pair,first 是 key,second 是 value。

map 的底層結構

與 set 一樣使用紅黑樹實作,插入、查詢、刪除的複雜度均為$O(log N)$,其中 N 是 map 的大小。

key 不需要排序?

跟 set 一樣,在前面加上 unordered,實作方式改為 hash,失去照順序功能,但插入、查詢、刪除的複雜度降為 $O(1)$。

練習

TOJ 55

ZJ d518

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// TOJ 55
#include<bits/stdc++.h>
using namespace std;

unordered_map<int, int> mp;
int n, q;

int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=1,x;i<=n;i++) cin >> x, mp[x]++;
cin >> q;
for(int i=1,x;i<=q;i++) cin >> x, cout << mp[x] << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ZJ d518
#include<bits/stdc++.h>
using namespace std;

unordered_map<string, int> mp;
string str;
int n, id;

int main(){
ios::sync_with_stdio(0), cin.tie(0);
while(cin>>n){
mp.clear();
id = 0;
for(int i=1;i<=n;i++){
cin >> str;
if(!mp[str]) cout << "New! ", mp[str] = ++id;
else cout << "Old! ";
cout << mp[str] << '\n';
}
}
}

問題

如果今天,我需要支援以下兩種操作:

  1. 插入一個數字
  2. 查詢比一個數字大的最小元素是什麼

一個簡單的想法是,就用一個陣列通通存起來,然後查詢時一個一個找。這樣對於第一種插入操作是 $O(1)$ ,第二種是 $O(N)$。

另一個是,插入時使用 insertion sort 方法,讓整個陣列維持排序好的狀態。搜尋時就能直接使用 upper_bound 函式。這樣對於第一種插入操作是 $O(N)$ ,第二種是 $O(logN)$。

在插入與查詢次數差不多的情況下,這兩種方法都無法快速的解決問題。

二元搜尋樹

雖然現在大家可能還沒有樹的概念,還是請大家看看這個教學。

二元搜尋樹

二元搜尋樹保證,一個節點左邊一定全部都比它小,右邊一定全部比它大。

可以發現,以上兩種操作都可以透過二元搜尋樹來完成。而複雜度則是以樹的深度(從一開始走到沒路可走時的最長距離)來決定。

在一般的二元搜尋樹中,深度並沒有保證(想像插入的數字一直遞增),最高與元素數量 $N$ 相等。

但,若現在有一種二元搜尋樹,可以透過旋轉、換根等操作,保證在任何時刻,深度都是 $O(logN)$,這個題目就可以很好的解決了。

而 set 就可以做到這樣的事情!set 的內部,正是平衡二元搜尋樹之一的紅黑樹

不同於之前的 queue 與 stack,這超難實作的,所以就直接進用法。

set 語法

set,意為集合,集合內不會存在兩個相同元素。

宣告一個 set 名為 s。

1
set<int> s;

插入元素,若 set 內部已存在該元素,則無任何動作。

1
s.insert(5);

移除元素,若 set 內部無該元素,則無任何動作。也可以移除一個 iterator 所指向的元素,程式會自動判斷傳入型態。

1
2
s.erase(5);
s.erase(s.begin())

回傳該元素的 iterator,若 set 內部無該元素,則回傳 end()。

1
s.find(5);

依照順序輸出內部所有元素,複雜度 $O(N)$。

1
for(int i:s) cout << i << '\n';

問一個元素在不在 set 裡。可透過 find 的 return 值,或使用 s.count。

1
2
if(s.find(10) != s.end()) cout << "In!\n";
if(s.count(10)) cout << "In!\n";

得到 set 的第一項,可使用 *s.begin(),最後一項使用 *s.rbegin()。

1
2
cout << *s.begin() << '\n';
cout << *s.rbegin() << '\n';

那,可以輸出 set 中第 K 小的數字嗎?答案是不行的,set 沒有辦法做到這點。因此,set 中是沒有 s[k] 這樣的語法的。

但是,set 的 iterator,可以支援 ++, – 的運算,而且是 $O(1)$ 的。所以,若能以一個變數將 begin() 存下來,之後將其 ++,便可以得到第 2 大的數字。

要怎麼儲存呢?用變數。那型態是什麼?是:

1
set<int>::iterator iter = s.begin();

這名稱實在太長,因此我們使用 C++11 後出現的新功能:自動判斷型態!

1
2
auto iter = s.begin();
cout << *(++iter) << '\n';

因此,遍歷 set 也可以寫成:

1
2
3
for(auto iter = s.begin(); iter != s.end(); iter++){
cout << *iter << '\n';
}

此外,若要得到一個 iterator 的前/後一項,可以使用 prev/next,這樣不會改到本身,常見於得到 set 中最大的數。

1
cout << *prev(s.end()) << '\n';

回來看看

原來的問題,要如何用 set 去做呢?

操作一很簡單,就是 insert 而已。

操作二呢?恩…好像還是沒辦法,如果 set 中存在要被查詢的那個數,可以寫:

1
2
auto iter = s.find(x);
cout << *(++iter) << '\n';

但若不存在,find 函式回傳 end,就沒辦法了。

若是有一個類似 upper_bound 的函式就好了…

對,沒錯,set 的成員函式有 upper_bound()!

1
cout << *s.upper_bound(5) << '\n';

順帶一提,upper_bound(s.begin(), s.end(), 5)這種寫法也能輸出正確答案,但是複雜度是糟糕的 $O(size)$。請忘記這種用法,記住 s.upper_bound() 就好!

連續刪除 a 到 b 區間內元素

1
2
3
for(auto iter = s.find(5); iter != s.end() && *iter < 10; iter++){
s.erase(iter);
}

這是對的嗎?看起來好像是,但其實不是,而且會導致 RE。為什麼呢?

當 iter 被 erase 後,它就不存在了,因此將其++後會發生什麼事?沒有人知道。

怎麼辦呢?

s.erase() 這個函式,其實不是 void,它會回傳被刪除的元素的下一個 iterator。

因此可以利用這個性質:

1
for(auto iter = s.find(5); iter != s.end() && *iter < 10; iter = s.erase(iter));

我需要有多個相同元素的 set

set 在 insert 時,遇到相同元素會忽略,常常會因為這樣產生許多 bug。比如,插入 5 個 1 後刪除 1 個 1,在 set 中就不存在 1 了,但你真正想做的事,可能是跟剩下的 4 個 4 有關。

那要怎麼讓 set 中有多個元素呢?

第一個辦法是,多紀錄一個變數 cnt,代表每個元素的個數。只在 cnt 從 0 變為 1 時將其加入 set,從 1 變為 0 時將其移除。

但是,其實,STL 中有個東西叫 multiset,可以同時存在多個相同元素!

語法大致與 set 相同,但有一些東西要注意:

  1. 可用 .count() 函式回傳 multiset 中元素數量。
  2. s.erase(10) 代表的意思是:刪除 multiset 中所有的 10,若只刪除一個要用 s.erase(s.find(10))

我不需要排序,我只需要知道哪些東西在裡面

STL 中,有個東西叫 unordered_set,底層以 hash 實作。插入與刪除的複雜度皆為常數稍大的 $O(1)$,一般來說會比 set 的 $O(logN)$ 快。

unordered_set 失去 lower_bound 與 upper_bound 功能,遍歷時也不會照大小輸出,其餘功能與 set 相同。

自訂比較函式

這裡的比較函式跟 sort 的不一樣,是一個 struct,裡面有一個 operator(),所以要這樣寫:

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
#include<bits/stdc++.h>
using namespace std;

int sum_of_digits(int x){
int ans = 0;
while(x){
ans += x%10;
x/=10;
}
return ans;
}

struct cmp{
bool operator()(int a, int b){
return sum_of_digits(a) < sum_of_digits(b);
}
};

set<int, cmp> s;

int main(){
ios::sync_with_stdio(0), cin.tie(0);
s.insert(56);
s.insert(11);
s.insert(7);
for(auto i:s) cout << i << '\n';
}

預設的比較函式是 less<>,有另一個定義好的比較函式是 greater<>,所以如果要從大排到小,可以這樣寫。

1
set<int, greater<int>> s;

練習

TIOJ 1911

85 分解:
ZJ b938

★★★ TOJ 275

★★★★ TIOJ 1161

★★★★★ TOJ 512

★★★★★★★★ TIOJ 1941

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
// TIOJ 1911
#include<bits/stdc++.h>
using namespace std;
#define ll long long
multiset<ll> m;
int n;

int main() {
ios::sync_with_stdio(0), cin.tie(0);
while(cin >> n){
if(n == 0) break;
if(n > 0) m.insert(n);
else{
if(m.empty()) continue;
if(n == -1){
cout << *m.begin() << ' ';
m.erase(m.begin());
}
else{
auto iter = m.end();
iter--; // end 的前一個才是真正最大的
cout << *iter << ' ';
m.erase(iter);
}
}
}
cout << '\n';
}
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
// ZJ b938 85 分解
#include<bits/stdc++.h>
using namespace std;
int n, m;
set<int> s;
bool dead[1000005];

int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++) s.insert(i);
for(int i=1,x;i<=m;i++){
cin >> x;
if(dead[x]) cout << "0u0 ...... ?\n";
else{
auto iter = s.upper_bound(x);
if(iter == s.end()) cout << "0u0 ...... ?\n";
else{
cout << *iter << '\n';
dead[*iter] = 1;
s.erase(iter);
}
}
}
}
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
// TOJ 275
// 分成小的堆跟大的堆,保持兩邊的個數差異在1以內。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
multiset<ll> small, big;

void pop_big(){
ll x = *big.begin();
small.insert(x);
big.erase(big.begin());
}

void pop_small(){
ll x = *small.rbegin();
big.insert(x);
small.erase(prev(small.end()));
}

int main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(6);
cin >> n;
for(int i=1,x;i<=n;i++){
cin >> x;

if(i == 1 || x < *small.rbegin()) small.insert(x);
else big.insert(x);

while(big.size() > i/2) pop_big();
while(big.size() < i/2) pop_small();

double ans;
if(i&1) ans = *small.rbegin();
else ans = (*small.rbegin() + *big.begin()) * 1.0 / 2;
cout << ans << '\n';
}
}
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
// 枚舉其中一個點數
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

multiset<int,greater<int>> s;
int n, k;
pii arr[1000005];

void solve(){
s.clear();
cin >> n >> k;
for(int i=1;i<=n;i++) cin >> arr[i].first >> arr[i].second;
sort(arr+1, arr+n+1);
int ans = 1e9;
for(int i=1;i<=n;i++){
s.insert(arr[i].second);
if(s.size() > k) s.erase(s.begin());
if(s.size() == k) ans = min(ans, arr[i].first + *s.begin());
}
cout << ans << '\n';
}

int main(){
int t; cin >> t; while(t--) solve();
}
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
// TOJ 512
// 每次操作 1 最多增加 2 個錯誤位置,以 set 維護錯誤位置,使你在 log 時間內能夠刪除 1 個錯誤位置
#include<bits/stdc++.h>
using namespace std;

set<int> s;
int n, q;
int arr[1000005], pos[1000005];

void change(int x, int y){
s.erase(x);
s.erase(y);
swap(arr[x], arr[y]);
pos[arr[x]] = x;
pos[arr[y]] = y;
//cout << x << " " << y << " " << arr[x] << " " << arr[y] << '\n';
if(arr[x] != x) s.insert(x);
if(arr[y] != y) s.insert(y);
}

int recover(int x, int y){
int ans = 0;
while(1){
auto iter = s.lower_bound(x);
if(iter == s.end() || *iter > y) break;
ans++;
change(pos[*iter], *iter);
}
return ans;
}

int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
for(int i=1;i<=n;i++) pos[i] = arr[i] = i;
for(int i=1,ope,a,b;i<=q;i++){
cin >> ope >> a >> b;
if(ope == 1) change(a, b);
else cout << recover(a, b) << '\n';
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// TIOJ 1941
// 建議先了解 LIS 以後再來
// 注意加入一隻寶可夢時,LIS表格的變化
// 以set儲存LIS改變的位置即可
#include<bits/stdc++.h>
using namespace std;
multiset<int> s;
int n;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=1,l,r;i<=n;i++){
cin >> l >> r;
s.insert(l);
auto iter = s.upper_bound(r);
if(iter != s.end()) s.erase(iter);
}
cout << s.size() << '\n';
}

隊列(queue)

想像有一天,你來到了師大最熱門的 TOI 拉麵店,店內空間不大,只有三十個左右,因此門外的人排成了長長的隊伍。你加入到了隊列的尾端,等待老闆叫號。隨著時間過去,前面的人依序進入店裡,也看到不少人帶著滿足的笑容走出。終於,就快輪到你了!

只能從後方加入,並且只能從前方取出,這就稱作 queue!

實作

知道了概念,但要怎麼實作 queue 呢?

我們可以先開一個足夠大的陣列,並且記錄當前隊伍最前方位置與最後方位置。

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
#include<bits/stdc++.h>
using namespace std;
int arr[1000005], l=0, r=-1; // 想想為什麼 r = -1

void push(int x){
r++;
arr[r] = x;
}

void pop(){
assert(l<=r); // 還有東西
l++;
}

int front(){
assert(l<=r);
return arr[l];
}

int siz(){
return r-l+1;
}

int main(){
push(1); // 從後方加入元素
push(2);
push(5);
cout << front() <<'\n'; // 查看最前方元素
cout << siz() <<'\n'; // 查看queue大小
pop(); // 從前方移除元素
cout << front() <<'\n'; // 查看最前方元素
cout << siz() <<'\n'; // 查看queue大小
}

這樣雖然可以得到正確的答案,但不免會有浪費空間(pop 後前方空間就浪費了)或記憶體不夠大的問題,因此,可將 r mod 陣列長度,當元素存到底時,就再回到第一格,以避免浪費空間,當然,陣列還是要開得夠大,至少必須超過同時存在的元素數量。

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1000000;
int arr[N+5], l=0, r=-1; // 想想為什麼 r = -1

void push(int x){
r++;
arr[r%N] = x;
}

void pop(){
assert(l<=r); // 還有東西
l++;
}

int front(){
assert(l<=r);
return arr[l%N];
}

int siz(){
return r-l+1;
}

int main(){
push(1); // 從後方加入元素
push(2);
push(5);
cout << front() <<'\n'; // 查看最前方元素
cout << siz() <<'\n'; // 查看queue大小
pop(); // 從前方移除元素
cout << front() <<'\n'; // 查看最前方元素
cout << siz() <<'\n'; // 查看queue大小
}

更好的方法

放在這個章節,想必可以想到,這東西其實是有 STL 的!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
queue<int> q;

int main(){
q.push(1); // 從後方加入元素
q.push(2);
q.push(5);
cout << q.front() << '\n'; // 查看最前方元素
cout << q.size() << '\n'; // 查看queue大小
q.pop(); // 從前方移除元素
cout << q.front() << '\n'; // 查看最前方元素
cout << q.size() << '\n'; // 查看queue大小
q.pop();
q.pop();
if(q.empty()) cout << "Empty!\n";
}

這樣就完成了一個長度會自己變化的 queue 了!(當然,開太大還是會 RE)

要注意的一點是,如果在 queue 為空時,呼叫了 pop() 或 front() 等函式,都是會導致 RE 的!

stack

吃完了拉麵,要付錢時,你居然發現,錢包不知道為什麼不見了!沒有付錢的你只好乖乖留下來洗碗。

你每次會從最上方拿出一個碗來洗,有新的髒碗要洗時也會放在最上面。

只能從上方加入,並且只能從上方取出,這就稱作 stack!

實作

如何實作 stack 呢?

只需要一個陣列,以及一個紀錄目前位置的變數就可以了!比 queue 簡單很多。

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1000000;
int arr[N+5], r=-1; // 想想為什麼 r = -1

void push(int x){
r++;
arr[r] = x;
}

void pop(){
assert(r>=0);
r--;
}

int top(){
assert(r>=0);
return arr[r];
}

int siz(){
return r+1;
}

int main(){
push(1); // 從後方加入元素
push(2);
push(5);
cout << top() <<'\n'; // 查看最前方元素
cout << siz() <<'\n'; // 查看queue大小
pop(); // 從前方移除元素
cout << top() <<'\n'; // 查看最前方元素
cout << siz() <<'\n'; // 查看queue大小
}

事實上,也完全可以使用能動態改變長度,並且能從後方加入刪除的 vector 來實作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
const int N = 1000000;
vector<int> arr;


int main(){
arr.push_back(1); // 從後方加入元素
arr.push_back(2);
arr.push_back(5);
cout << arr.back() <<'\n'; // 查看最前方元素
cout << arr.size() <<'\n'; // 查看queue大小
arr.pop_back(); // 從前方移除元素
cout << arr.back() <<'\n'; // 查看最前方元素
cout << arr.size() <<'\n'; // 查看queue大小
}

不過,還是有一個名為 stack 的 STL,它是這樣用的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
const int N = 1000000;
stack<int> stk;


int main(){
stk.push(1); // 從後方加入元素
stk.push(2);
stk.push(5);
cout << stk.top() <<'\n'; // 查看最前方元素
cout << stk.size() <<'\n'; // 查看queue大小
stk.pop(); // 從前方移除元素
cout << stk.top() <<'\n'; // 查看最前方元素
cout << stk.size() <<'\n'; // 查看queue大小
}

功用

queue 與 stack 與其說是一種工具,更像是一種概念。queue 代表著的是,先進去的元素一定先出來(FIFO),而 stack 則是剛好相反。

STL 的 queue 與 stack 本身,都能夠輕易被其他工具代替。我們使用它們的原因,是因為它們所表達出來的概念,能夠讓程式可讀性更高。

你可能第一時間看不懂一個 vector 一直 push_back() 又 pop_back(),但只要看到 stack,就可確信這裡用到了先進後出的概念,從而更快理解整段程式碼。

練習

ZJ b923

ZJ e155

★★ ZJ c123

★★ ZJ a565

★★★★ ZJ a813

★★★★★ ZJ a664

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
// b923
#include<bits/stdc++.h>
using namespace std;
int n, ope, x;
stack<int> s;

int main(){
cin >> n;
while(n--){
cin >> ope;
if(ope == 1){
s.pop();
}
else if(ope == 2){
cout << s.top() << '\n';
}
else{
cin >> x;
s.push(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
// ZJ e155
#include<bits/stdc++.h>
using namespace std;
int n;
queue<int> q;
vector<int> dis;

int main(){
while(cin>>n){
if(n==0) break;
dis.clear();
while(!q.empty()) q.pop();
for(int i=1;i<=n;i++) q.push(i);
while(q.size() > 1){
dis.push_back(q.front());
q.pop();
q.push(q.front());
q.pop();
}
cout << "Discarded cards: ";
for(int i=0;i<dis.size();i++){
if(i>0) cout << ", ";
cout << dis[i];
}
cout << '\n';
cout << "Remaining card: " << q.front() << "\n";
}
}
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
// ZJ c123
#include<bits/stdc++.h>
using namespace std;
int n;
stack<int> station;
queue<int> train;

int main(){
while(cin>>n){
if(n == 0) break;
while(1){
bool ok = 1, out = 0;
while(!station.empty()) station.pop();
while(!train.empty()) train.pop();

for(int i=1;i<=n;i++){
train.push(i);
}

for(int i=1,x;i<=n;i++){
cin >> x;
if(x == 0){
out = 1;
break;
}
while(station.empty() || station.top() != x){
if(train.empty()){
ok = 0;
break;
}
else{
station.push(train.front());
train.pop();
}
}
if(ok) station.pop();
}
if(out) break;
else if(ok) cout << "Yes\n";
else cout << "No\n";
}
cout << '\n';
}
}

我們分別計算往左與往右能夠看到多少大樓,對於一個大樓,如果右邊出現比他高的大樓,那這座大樓就永遠不會再被右邊的其他人看到了。這題用到了單調隊列這個有趣的東西,有興趣的可以自行查詢,未來有機會也會單獨開一個章節介紹。

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
// ZJ a813
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
ll arr[1000005], n;

int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=1;i<=n;i++){
cin >> arr[i];
}
ll ans = 0;
for(int t=0;t<2;t++){
stack<pii> s;
for(int i=1;i<=n;i++){
while(!s.empty() && s.top().first < arr[i]){
ans += s.top().second;
s.pop();
}
if(!s.empty() && s.top().first == arr[i]){
pii tmp = s.top();
s.pop();
if(!s.empty()) ans++;
ans += tmp.second;
s.emplace(tmp.first, tmp.second+1);
}
else{
if(!s.empty()) ans++;
s.emplace(arr[i], 1);
}
}
reverse(arr+1, arr+1+n);
}
cout << ans << '\n';
}

將中序算式轉為後序運算式後,進行運算。
中序轉後序

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
// ZJ a664
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int pri[128];

stack<ll> stk;
stack<char> op;

ll calc(ll a1, ll a2, char ope){
//cout << a1 << " " << a2 << " " << ope << '\n';
if(ope == '+') return a1+a2;
if(ope == '-') return a1-a2;
if(ope == '*') return a1*a2;
if(ope == '/') return a1/a2;
return -1;
}

string s;
void solve(){
cin >> s;
bool is_num = 0;
int num = 0;
for(auto &c:s){
if(isdigit(c)) num = num * 10 + c - '0', is_num = 1;
else{
if(is_num) stk.push(num), num = 0, is_num = 0;
if(c == ')'){
while(op.top() != '('){
ll a2 = stk.top();
stk.pop();
ll a1 = stk.top();
stk.pop();
char ope = op.top();
op.pop();
stk.push(calc(a1, a2, ope));
}
op.pop();
}
else if(c == '(') op.push(c);
else{
while(!op.empty() && op.top() != '(' && pri[op.top()] > pri[c]){
ll a2 = stk.top();
stk.pop();
ll a1 = stk.top();
stk.pop();
char ope = op.top();
op.pop();
stk.push(calc(a1, a2, ope));
}
op.push(c);
}
}
}
if(is_num) stk.push(num);

while(stk.size() > 1){
ll a2 = stk.top();
stk.pop();
ll a1 = stk.top();
stk.pop();
char ope = op.top();
op.pop();
stk.push(calc(a1, a2, ope));
}
cout << stk.top() << '\n';
stk.pop();
}

int main(){
ios::sync_with_stdio(0), cin.tie(0);
pri['*'] = pri['/'] = 1;
pri['+'] = pri['-'] = 0;

int t;
cin >> t;
while(t--) solve();
}

什麼是pair

還記得嗎?如果我們需要儲存二維平面上的一個點,需要同時儲存 x, y 兩個整數,但又需要進行 sort 之類會改變位置的操作,要怎麼做呢?

在前面的章節裡,有提到struct的做法,宣告一個含兩個變數 x, y 的 struct,再自定義比較函式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
struct Point{
int x, y;
bool operator<(Point b){
if(x != b.x) return x < b.x;
else return y < b.y;
}
}p[1005];

int main(){
for(int i=0;i<10;i++){
cin >> p[i].x >> p[i].y;
}
sort(p, p+10);
}

雖然可以理解運作原理,但是,上面那一串感覺好長好麻煩喔…

pair 的出現,可以簡化這一切!

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
pair<int,int> p[1005];

int main(){
for(int i=0;i<10;i++){
cin >> p[i].first >> p[i].second;
}
sort(p, p+10);
}

pair可以將兩個變數,綁在一起儲存。可以看成一種新的型態,大幅簡化了儲存兩項東西的難度。

更強的是,能儲存的東西,不只是變數。

1
2
3
pair<int, pair<int,int>> p1
pair<int, vector<int>> p2;
pair<int, vector<pair<int, vector>>> ..... // (X)

想放什麼就放!

宣告與指派

1
2
3
4
5
pair<int, int> p;
// p = 5, 4 WRONG
p = make_pair(5, 4);
p = {8, 9};
cout << p.first << " " << p.second << "\n";

以 pair<型態, 型態> 進行宣告。

要指派的話,需先將要指派過去的兩個變數做成一個 pair,有 make_pair() 以及 {} 兩種方法。

將兩個變數綁在一起後,就可以進行指派了!

pair 中的第一個元素為 first,第二個為 second。以 p.first、p.second 進行存取,因為不是函式,所以不同於 push_back() 等等也需要加 . 的東西,並不需在後面加上()。

大小比較

pair 的比較原則是:先比前面,一樣的話再比後面。當然,pair<int, int> 是不能跟 pair<string, int> 比較的。只有相同的型態才能進行比較。

這個性質可以幫助我們省下一些時間,例如之前的例題。這題要求我們先照 x 座標,再照 y 座標排序,神奇的事發生了!這剛好就是 pair 的比較方法,因此,不用自訂比較函式,使用 pair<int, int> 儲存資料後直接 sort 就可以了!

如果今天是麻煩的比較,就自訂 pair 的比較規則吧!

1
2
3
4
bool operator <(pair<int, int> a, pair<int, int> b){
if(a.first != b.first) return a.first < b.first;
else return a.second > b.second;
}

與 vector 的連用

1
2
3
4
5
6
7
8
vector<pair<int, int>> vp;
vp.push_back(make_pair(1,2));
vp.push_back({1,2});
vp.emplace_back(1,2);
for(pair<int, int> i: vp){
//cout << i << "\n";
cout << i.first << " " << i.second << '\n';
}

要注意的點大概是這些:

  1. push_back() 裡面要放 pair,因此要記得 make_pair() 或 {} 。
  2. emplace_back() 不需要 make_pair(),直接 emplace_back(a,b) 就可以了。
  3. pair 無法直接輸出,需分開輸出 first 以及 second。

練習

ZJ a915

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

pair<int,int> arr[1005];
int n;

int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> arr[i].first >> arr[i].second;
}
sort(arr+1, arr+1+n);
for(int i=1;i<=n;i++){
cout << arr[i].first << " " << arr[i].second << '\n';
}
}