Kuo's Blog

競程筆記|個人網站

前言

其實面試不用緊張,照你們平常跟老師的講話方式就好。目前我面的學校,教授們都很 Nice,我本人就慢熟,但我的高中有模擬面試,有模擬面試就去試試看,體驗一下那種感覺,然後說實話不用太壓抑自己,把想說的說出來即可,教授特喜歡這種有想法的人。

閱讀全文 »

簡介

發明 DP 的真是個天才注意看,這個會 DP 的男人太狠了

0/1 背包問題的題目在於物品的放或不放,並且在有限重量的背包中,獲得最高價值。

通常可以想到用暴力(就是數學 n 個物品取或不取的兩種可能),但是 O(2n)O(2^n) 真的很恐怖,資料一多,馬上 TLE。

因此利用陣列紀錄每個物品在某重量該放與不放,可以紀錄之前的資料又不會重新計算。

閱讀全文 »

簡介

  • 使用前,需引入 <set> 標頭檔。
  • 通常是用紅黑樹實作的。
  • set 容器內的元素是唯一的(不重複)。
  • set 容器具有排序性。
  • set 容器內的值不可被修改。
閱讀全文 »

TOI 2024 四月新手組解答,一維陣列的應用。幾乎暴力解,但第三題不知道可不可以再簡化。

閱讀全文 »

說明

第 4 題還在研究~

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
27
28
29
30
31
32
#include <bits/stdc++.h>
#define ouo ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define db double
using namespace std;

int n;

struct p {
int a;
int d;
int ability;
};

bool cmp(p a, p b) {
return a.ability > b.ability;
}

int main() {
ouo;

cin >> n;
p player[n];
for (int i = 0; i < n; i++) {
cin >> player[i].a >> player[i].d;
player[i].ability = player[i].a * player[i].a + player[i].d * player[i].d;
}
sort(player, player + n, cmp);
cout << player[1].a << " " << player[1].d;

return 0;
}

2. 蜜蜂觀察

展開程式碼

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
#include <bits/stdc++.h>
#define ouo ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define db double
using namespace std;

int m, n, k;
int amount = 0;

int main() {
cin >> m >> n >> k;

string arr[m];
for (int i = 0; i < m; i++) {
cin >> arr[i];
}

int p_x = m - 1, p_y = 0;

bool alpha[2][26] = {false};
for (int t = 0; t < k; t++) {
int d = -1;
cin >> d;
int d_x = 0, d_y = 0;
switch (d) {
case 0:
d_x -= 1;
break;
case 1:
d_y += 1;
break;
case 2:
d_x += 1;
d_y += 1;
break;
case 3:
d_x += 1;
break;
case 4:
d_y -= 1;
break;
case 5:
d_x -= 1;
d_y -= 1;
break;
default:
break;
}
if (p_x + d_x < m && p_x + d_x >= 0 && p_y + d_y < n && p_y + d_y >= 0) {
p_x += d_x;
p_y += d_y;
}
cout << arr[p_x][p_y];

if (arr[p_x][p_y] >= 'a' && arr[p_x][p_y] <= 'z') {
alpha[0][arr[p_x][p_y] - 'a'] = true;
} else if (arr[p_x][p_y] >= 'A' && arr[p_x][p_y] <= 'Z') {
alpha[1][arr[p_x][p_y] - 'A'] = true;
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 26; j++) {
if (alpha[i][j] == true) amount++;
}
}
cout << "\n"
<< amount;
return 0;
}

3. 邏輯電路

參考 @Youtong0826 的思路,原本只有做 DFS 的部分但會超時,所以改成用 DP 紀錄已經跑過的邏輯閘。

展開程式碼

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
#include <bits/stdc++.h>
#define ouo ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define db double
using namespace std;

struct node {
int type; // 1: AND, 2: OR, 3: XOR, 4: NOT
int result;
};

int p, q, r, m;
vector<node> vc;
vector<bool> visited;
vector<int> ans;
vector<vector<int>> g;
vector<pair<int, int>> dp;

// pair<int, int> = {result, delay}
pair<int, int> dfs(int idx) {
if (idx <= p) {
visited[idx] = true;
return dp[idx] = {vc[idx].result, 0};
}

// 輸出節點必只有一個輸入端
if (idx > p + q && idx <= p + q + r) return dfs(g[idx][0]);

if (visited[idx]) return dp[idx];

// do
visited[idx] = true;
auto a = dfs(g[idx][0]); // 先取得第一個輸入端

if (vc[idx].type == 4) return dp[idx] = {!a.first, a.second + 1};

auto b = dfs(g[idx][1]);

if (vc[idx].type == 1) return dp[idx] = {(a.first && b.first), max(a.second, b.second) + 1};
if (vc[idx].type == 2) return dp[idx] = {(a.first || b.first), max(a.second, b.second) + 1};
if (vc[idx].type == 3) return dp[idx] = {(a.first != b.first), max(a.second, b.second) + 1};
return {vc[idx].result, 0};
}

int main() {
ouo;
cin >> p >> q >> r >> m;

// init
vc.resize(p + q + r + 1);
visited.assign(p + q + r + 1, false);
g.assign(p + q + r + 1, {});
dp.resize(p + q + r + 1);
for (int i = 1; i <= p + q; i++) {
vc[i].result = 0;
vc[i].type = -1;
}

// in
for (int i = 1; i <= p; i++) {
cin >> vc[i].result;
}

// logic
for (int i = 1; i <= q; i++) {
cin >> vc[p + i].type;
}

// graph
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
g[b].push_back(a);
}

int delay = -1;
for (int i = p + q + 1; i <= p + q + r; i++) {
auto f = dfs(i);
ans.push_back(f.first);
delay = max(delay, f.second);
}

cout << delay << "\n";
for (auto i : ans) cout << i << " ";
}