APCS. 2019/02/16

2019/02/19 APCS實作題詳解及範例程式

pA

無確切題目敘述及輸入格式。

pB

Description

給定一個長度為$n(1<n\le10^5)$的01字串,計算最長與最短的連續1長度。
接著有$k(1 \le k \le 2*10^4)$次操作,每次將一個0改成1。
對於每次操作,輸出當前最長與最短的連續1長度(包括一開始輸入的)。

Solution

題目中有特別說到保證連續1的長度不超過$10^4$,所以可以用線性做法,不過這裡是考慮到當沒有這個限制時,應該怎麼做。

使用Disjoint Set(並查集)紀錄連通塊(相鄰的1為同一塊),接著用multiset紀錄每個連通塊的大小。
對於每次輸入,把該點的兩邊(注意要考慮到可能只有一邊是1的可能)的大小在multiset中去掉,然後用Disjoint Set合併,再將新的大小插入到multiset裡面。
輸出的時候輸出set中最大最小值即可。

時間複雜度:$O(n + klogn)$

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

const int maxn = 10010;
int n, k;
int in[maxn];
multiset<int> s;
struct disjoint_set {
int parent[maxn];
int size[maxn];
void init() {
for (int i = 0; i <= maxn; i++) {
parent[i] = i;
size[i] = 1;
}
}
int find(int i) {
if (i == parent[i])
return i;
return parent[i] = find(parent[i]);
}
void connect(int a, int b) {
int pa = find(a);
int pb = find(b);
s.erase(s.find(size[pa]));
s.erase(s.find(size[pb]));
size[pa] += size[pb];
parent[pb] = pa;
s.insert(size[pa]);
}
}ds;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
ds.init();
for (int i = 1; i <= n; i++) {
cin >> in[i];
if (in[i])
s.insert(1);
}
for (int i = 2; i <= n; i++) {
if (in[i - 1] && in[i]) {
ds.connect(i - 1, i);
}
}
cout << *s.begin() << ' ' << *s.rbegin() << '\n';
while (k--) {
int i;
cin >> i;
ds.size[i] = 1;
s.insert(1);
if (i > 1 && in[i - 1])
ds.connect(i - 1, i);
if (i < n && in[i + 1])
ds.connect(i, i + 1);
in[i] = 1;
cout << *s.begin() << ' ' << *s.rbegin() << '\n';
}
return 0;
}

pC

Description

給你三個數值函數f,g,h的定義,變數數目各為1,2,3,且保證均為一次函數。輸入一個三者的合成函數但所有括號與逗點都被空白取代,計算該合成函數的值。題目中提示可以用遞迴,並保證不必使用大數運算。

Solution

遞迴做下去。
由於我沒有f,g,h的係數,所以在程式中會標示為$f0, g0, g1, h0, h1, h2$代表各個係數。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f0, g[2], h[3];
ll toll(string &s) {
ll re = 0;
for (char &i : s) {
re *= 10;
re += i - '0';
}
return re;
}
ll calc(char cmd) {
string s;
ll re = 0;
if (cmd == 'f') {
cin >> s;
if (isdigit(s[0]))
re = f0 * toll(s);
else
re = f0 * calc(s[0]);
}else if (cmd == 'g') {
for (int i = 0; i < 2; i++) {
cin >> s;
if (isdigit(s[0]))
re += g[i] * toll(s);
else
re += g[i] * calc(s[0]);
}
}else
for (int i = 0; i < 3; i++) {
cin >> s;
if (isdigit(s[0]))
re += h[i] * toll(s);
else
re += h[i] * calc(s[0]);
}
return re;
}
void init() {
// 測試用係數
f0 = 2;
g[0] = 1, g[1] = 2;
h[0] = 1, h[1] = 3, h[2] = 4;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// init();
char cmd;
cin >> cmd;
cout << calc(cmd) << '\n';
return 0;
}

pD

Description

給定$n(1<n<2*10^5)$,及長度為$n$的陣列ab$(0 \le a[i], b[i] \le 10^7)$。
$S(i)=i-max(j)-1 使得 a[i]+b[i]<a[j] 且 j<i (若j不存在,則j=0)$。
求$\sum_{i=1}^n S(i)$為何。

Solution

從前面做到後面,假設當前index為$i$,則可以刪掉一些在$i$之前「不可能為答案」的數字。
這樣講解有點抽象,從下面的圖片比較容易懂:
考慮$a[1]\text{~}a[5]$,可以發現$a[2]和a[4]$不可能為答案,因為$a[5]$比這兩個數字都還大。
所以可以把灰色部分砍掉,維護一個「遞減陣列」。
而有了這個遞減陣列,就可以利用$a[6]+b[6]$去二分搜,找出最大的j滿足條件。

不過到這裡還沒完,假設$S(i)$算完了,那應該要想辦法把$a[i]$加入該陣列。對於一個現成的遞減陣列,要怎麼加入新的元素?
一直檢查該陣列的後面,如果小於$a[i]$,則pop掉,否則就把$a[i]$加到最後面即可。

時間複雜度:$O(nlogn)$

注意:因為upper_bound預設是用在「遞增陣列」,並非遞減。所以我這裡在upper_bound時使用rbeginrend,是因為我是維護一個遞減數列,但是upper_bound只適用遞增數列,所以就用反向的iterator來處理。

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

typedef long long ll;
const int maxn = 200010;
int a[maxn], b[maxn];
int n;
ll ans;
struct node {
int num, index;
node() {}
node (int a, int b) {
num = a, index = b;
}
bool operator< (const node &b) const {
return num < b.num;
}
};
vector<node> arr;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
for (int i = 1; i <= n; i++) {
auto ptr = upper_bound(arr.rbegin(), arr.rend(), node(a[i] + b[i], 0));
if (ptr == arr.rend())
ans += i - 1;
else
ans += i - ptr->index - 1;
while (!arr.empty() && arr.back().num < a[i])
arr.pop_back();
arr.push_back({a[i], i});
}
cout << ans << '\n';
return 0;
}