APCS 2019/06/15

p1

見輸入輸出說明

Input

總共四行,每行包含四個不大於 100 的非負整數
前兩行依序為主客場第一場比賽四節之得分狀況
後兩行為第二場之數據

Output

輸出三行
前兩行分別為兩場比賽之主客場比分
第三行輸出:

  1. 若主場兩場皆勝,輸出 Win
  2. 若主場兩場皆負,輸出 Lose
  3. 否則輸出 Tie

Solution

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>
#define IO ios::sync_with_stdio(0);cin.tie(0)
#define endl '\n'

using namespace std;

int s[4];

signed main()
{
IO;
for (int i = 0, t; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cin >> t;
s[i] += t;
}
}
cout << s[0] << ":" << s[1] << endl;
cout << s[2] << ":" << s[3] << endl;
if (s[0] > s[1] && s[2] > s[3])
cout << "Win" << endl;
else if (s[0] < s[1] && s[2] < s[3])
cout << "Lose" << endl;
else
cout << "Tie" << endl;
return 0;
}

p2

有一 $m \times n$ 之地圖,每格上都會有一個值
要求從值最小的格子開始每次往四個方向中值最小的格子走,不能走重複的格子
求路徑上所有值之和

Input

第 1 行有兩個正整數 $m, n$ $(m, n \leq 100)$
第 2 ~ $m$ + 1 行,每行 $n$ 個整數

Output

輸出路徑上所有值之和

Solution

DFS 直接暴力求解即可
此處用的是類似 BFS 的解法

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
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define MAXN 105

using namespace std;

int m, n;
int a[MAXN][MAXN];
int sum;
int x, y, nxt_x, nxt_y, mn = INT_MAX;
bool vis[MAXN][MAXN];
int dx[] = { -1, 0, 1, 0};
int dy[] = { 0, 1, 0, -1};

signed main()
{
IO;
cin >> m >> n;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
if (a[i][j] < mn) {
mn = a[i][j];
nxt_x = i;
nxt_y = j;
}
}
}
while (true) {
if (nxt_x == -1 && nxt_y == -1)
break;
x = nxt_x, y = nxt_y;
vis[x][y] = true;
sum += a[x][y];
nxt_x = -1, nxt_y = -1, mn = INT_MAX;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (0 <= nx && nx < m && 0 <= ny && ny < n && !vis[nx][ny] && a[nx][ny] < mn)
mn = a[nx][ny], nxt_x = nx, nxt_y = ny;
}
}
cout << sum << endl;
return 0;
}

p3

給你 $n$ 個由字母 A-Z 所組成的集合,集合兩兩互不相同
求互補集合數

Input

第 1 行有一個整數 $n$ $(n \leq 5 \times 10^4)$
第 2 ~ $n$ + 1 行,每行一個由 A-Z 所構成的字串

Output

輸出互補集合數

Solution

在存集合的方式可以使用 bitset 的技巧
不只可以壓時間,程式的複雜度也減少許多

另外在找互補集合的部分其實用 set 就可以了
我在賽中是因為沒發現集合兩兩互不相同才用 map 的

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
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define MAXN 50005

using namespace std;

int m, n;
string s;
int a[MAXN];
map<int, int> cnt;
int res;

signed main()
{
IO;
cin >> m >> n;
for (int i = 0; i < n; i++) {
getline(cin, s);
int len = s.length();
for (int j = 0; j < len; j++)
a[i] |= 1 << (s[j] - 'A');
cnt[a[i]]++;
}
for (int i = n - 1; i >= 0; i--) {
res += cnt[((1 << m) - 1) ^ a[i]];
cnt[a[i]]--;
}
cout << res << endl;
return 0;
}

p4

給一大小為 $m$ 的陣列,其元素集合大小為 $n$
求長度為 $n$ 且包含所有元素之子區間數量

Input

第一行有兩個整數 $m, n$ ($m, n \leq 5 \times 10^4$)
第二行為一長度 $m$ 的陣列

Output

輸出符合題目敘述之子區間數量

Solution

因為其元素並非從 $1$ ~ $n$ ,故我們可以先對陣列做一次離散化
不過我在這邊的做法不是離散化,而是將每個元素利用 map 映射到一個新的 id 而已

利用 Sliding Window (Two Pointers) 的作法可以保證時間複雜度是線性的
又或者可以直接使用 STL 的 deque 做,寫法可以參考 吳邦一教授的FB

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
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define MAXN 50005

using namespace std;

int m, n;
int a[MAXN];
map<int, int> id;
int cnt[MAXN];
int res;

signed main()
{
IO;
cin >> m >> n;
for (int i = 0, tmp = 0; i < n; i++) {
cin >> a[i];
if (!id[a[i]])
id[a[i]] = tmp++;
}
int l = 0, r = 0;
while (r < n) {
while (cnt[id[a[r]]] && l <= r) {
cnt[id[a[l]]]--;
l++;
}
while (!cnt[id[a[r]]] && r < n) {
cnt[id[a[r]]]++;
r++;
}
if (r - l == m)
res++;
}
cout << res << endl;
return 0;
}