官方試題本
第一題為語言認知題，第二三題基本上都算是實作偏重的題目，第四題是經典greedy題目。
c461: apcs 邏輯運算子 (Logic Operators)
題目連結
基本位元運算題
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
|
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
a = a > 0 ? 1 : 0;
b = b > 0 ? 1 : 0;
c = c > 0 ? 1 : 0;
bool ok = false;
if((a & b) == c) {
printf("AND\n");
ok = true;
}
if((a | b) == c) {
printf("OR\n");
ok = true;
}
if((a ^ b) == c) {
printf("XOR\n");
ok = true;
}
if(!ok)
printf("IMPOSSIBLE\n");
return 0;
}
|
c462: apcs 交錯字串 (Alternating Strings)
題目連結
可以先對大小寫進行01編碼後，壓縮一下 (run-length encoding)
之後就是找 頭尾 $\ge k$ 且 中間均 $=k$ 的 最長子字串即可
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
|
#include <bits/stdc++.h>
using namespace std;
int k;
char inp[111111];
int main()
{
scanf("%d %s", &k, inp);
int len = strlen(inp);
int data[len];
for(int i = 0; i < len; i++) {
if('a' <= inp[i] && inp[i] <= 'z') {
data[i] = 0;
} else {
data[i] = 1;
}
}
int cnt = 1;
vector<int> compressed;
for(int i = 1; i < len; i++) {
if(data[i] == data[i - 1]) {
cnt++;
} else {
compressed.push_back(cnt);
cnt = 1;
}
}
compressed.push_back(cnt);
/*
for(auto i : compressed)
printf("%d ", i);
printf("\n");
*/
bool active = false;
int ans = 0;
int tmp = 0;
// head tail is ok to be >= k, other must be == k
for(int i = 0; i < (int)compressed.size(); i++) {
if(active == false) {
if(compressed[i] >= k) {
active = true;
tmp++;
}
} else {
if(compressed[i] == k) {
tmp++;
} else {
if(compressed[i] >= k)
tmp++;
tmp *= k;
ans = max(ans, tmp);
tmp = 0;
i--; // current one might be the start for another one
active = false;
}
}
}
tmp *= k;
ans = max(ans, tmp);
printf("%d\n", ans);
return 0;
}
|
c463: apcs 樹狀圖分析 (Tree Analyses)
題目連結
Bottom up DP
從 leaf 開始拔，並且一路更新 parent 的解即可。
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n;
scanf("%d", &n);
if(n == 1) {
printf("1\n0\n");
return 0;
}
int dp[n];
int par[n];
int deg[n];
memset(par, -1, sizeof(par));
memset(dp, 0, sizeof(dp));
queue<int> q;
for(int p = 0; p < n; p++) {
int k;
scanf("%d", &k);
if(k == 0)
q.push(p);
deg[p] = k;
for(int j = 0; j < k; j++) {
int child;
scanf("%d", &child);
child--;
par[child] = p;
}
}
while(q.size() > 0) {
int cur = q.front();
q.pop();
if(par[cur] != -1) {
dp[par[cur]] = max(dp[par[cur]], dp[cur] + 1);
deg[par[cur]]--;
if(deg[par[cur]] == 0)
q.push(par[cur]);
}
}
ll ans = 0;
for(int i = 0; i < n; i++) {
if(par[i] == -1)
printf("%d\n", i + 1);
ans += dp[i];
}
printf("%lld\n", ans);
return 0;
}
|
c471: apcs 物品堆疊 (Stacking)
題目連結
Hint
Greedy！
推看看，如果我們只交換某兩物品的位置，他的影響範圍大概如何？
Solution
假設目前的堆疊狀態從上到下為
$$ w_1, w_2, …, w_i, w_{i + 1}, …, w_n$$
$$ f_1, f_2, …, f_i, f_{i + 1}, …, f_n$$
如果我們交換 $i$ 跟 $i + 1$，堆疊狀態從上到下會變成
$$ w_1, w_2, …, w_{i + 1}, w_i, …, w_n$$
$$ f_1, f_2, …, f_{i + 1}, f_i, …, f_n$$
令
$$ A = w_1 + w_2 + … + w_{i - 1} $$
$$ B = f_{i + 2} + f_{i + 3} + … + f_n $$
交換之前（只列出會變動的部分），我們的 cost 是
$$ … + (A + w_i) (f_{i + 1}) + … $$
交換之後（只列出會變動的部分），我們的 cost 是
$$ … + (A + w_{i + 1}) (f_i)+ … $$
相減可以得到 $$w_i f_{i + 1} - w_{i + 1} f_i$$
所以，我們透過 sorting 時將 compare function 寫成
$$w_i f_{i + 1} < w_{i + 1} f_i$$
就可以讓 cost 小的堆疊方式被逐漸產生。
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Data {
int w, f;
};
bool cmp(const Data& a, const Data &b)
{
return a.w * b.f < b.w * a.f;
}
int main()
{
int n;
scanf("%d", &n);
Data data[n];
for(int i = 0; i < n; i++) {
scanf("%d", &data[i].w);
}
for(int i = 0; i < n; i++) {
scanf("%d", &data[i].f);
}
sort(data, data + n, cmp);
ll ans = 0, accum = 0;
for(int i = 0; i < n - 1; i++) {
accum += data[i].w;
ans += accum * data[i + 1].f;
}
printf("%lld\n", ans);
return 0;
}
|