Before all
這是我第二次考APCS，上次已經是去年了（中間一直有其他事情orz）
但這次不論是上午的觀念題還是下午的實作感覺都比去年還要順手很多，應該跟我暑假練很多有關吧，所以希望這次可以撈到 5/5…
底下是我考後打得code，題目在zerojudge上面應該都有
Write Up
Problem 1
機械鼠
用一個for迴圈讀取，再創造兩組變數分別記錄大於原始座標、小於原始座標的最遠距離和數量，比較大小後再輸出即可。
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>
using namespace std;
#define int long long
#define F first
#define S second
#define phb push_back
#define ppb pop_back
#define pii pair<int, int>
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define INF (long long) 1e18
#define mod 1e9+7
#define maxn 2000010
signed main(){
wh_ale;
int x, n, i, a, cnt1=0, cnt2=0, l1, l2;
cin >> x >> n;
l1=x;
l2=x;
for(i=0;i<n;i++){
cin >> a;
if(a>x){
cnt1++;
l1=max(l1, a);
}
else{
cnt2++;
l2=min(l2, a);
}
}
if(cnt1>cnt2){
cout << cnt1 << ' ' << l1 << '\n';
}
else cout << cnt2 << ' ' << l2 << '\n';
return 0;
}
|
Problem 2
卡牌遊戲
我是用while迴圈不斷去重複動作直到已經沒有牌之間可以消去，然後移走的則在陣列中以-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
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
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define phb push_back
#define ppb pop_back
#define pii pair<int, int>
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define INF (long long) 1e18
#define mod 1e9+7
#define maxn 2000010
signed main(){
wh_ale;
int n, m, i, j, a[100][100], k, cnt=0, cur=0;
bool t=true;
cin >> n >> m;
for(i=0;i<n;i++)for(j=0;j<m;j++) cin >> a[i][j];
while(t){
cur=0;
for(i=0;i<n;i++)for(j=0;j<m-1;j++){
if(a[i][j]!=-1){
for(k=1;k<m-j;k++){
if(a[i][j+k]!=-1){
if(a[i][j+k]==a[i][j]){
cur+=a[i][j];
a[i][j]=-1;
a[i][j+k]=-1;
}
break;
}
}
}
}
for(i=0;i<m;i++)for(j=0;j<n-1;j++){
if(a[j][i]!=-1){
for(k=1;k<n-j;k++){
if(a[j+k][i]!=-1){
if(a[j+k][i]==a[j][i]){
cur+=a[j][i];
a[j][i]=-1;
a[j+k][i]=-1;
}
break;
}
}
}
}
if(cur==0){
t=false;
break;
}
else cnt+=cur;
}
cout << cnt << '\n';
return 0;
}
|
Problem 3
搬家
建圖有點麻煩，剩下就是DSU算連通塊數量就好。
p.s.一開始海牛測資是錯的整個把我嚇死owo（只有十分）
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>
using namespace std;
#define int long long
#define F first
#define S second
#define phb push_back
#define ppb pop_back
#define pii pair<int, int>
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define INF (long long) 1e18
#define mod 1e9+7
#define maxn 200010
int p[510510]={}, n, m;
set<int> s[510510];
int findp(int x){
if(p[x]<0) return x;
else return findp(p[x]);
}
void combine(int x, int y){
x=findp(x);
y=findp(y);
if(x==y) exit;
else{
if(p[x]>p[y]) swap(x, y);
p[x]+=p[y];
p[y]=x;
}
}
signed main(){
wh_ale;
int i, j, ans=0;
char c;
cin >> n >> m;
for(i=0;i<n;i++)for(j=0;j<m;j++){
cin >> c;
p[1000*i+j]=-1;
if(c=='X'){
if(i+1>=0 and i+1<n) s[1000*i+j].insert((i+1)*1000+j);
if(i-1>=0 and i-1<n) s[1000*i+j].insert((i-1)*1000+j);
if(j+1>=0 and j+1<m) s[1000*i+j].insert(i*1000+j+1);
if(j-1>=0 and j-1<m) s[1000*i+j].insert(i*1000+j-1);
}
else if(c=='F'){
if(j+1>=0 and j+1<m) s[1000*i+j].insert(i*1000+j+1);
if(i+1>=0 and i+1<n) s[1000*i+j].insert((i+1)*1000+j);
}
else if(c=='H'){
if(j+1>=0 and j+1<m) s[1000*i+j].insert(i*1000+j+1);
if(j-1>=0 and j-1<m) s[1000*i+j].insert(i*1000+j-1);
}
else if(c=='7'){
if(j-1>=0 and j-1<m) s[1000*i+j].insert(i*1000+j-1);
if(i+1>=0 and i+1<n) s[1000*i+j].insert((i+1)*1000+j);
}
else if(c=='I'){
if(i+1>=0 and i+1<n) s[1000*i+j].insert((i+1)*1000+j);
if(i-1>=0 and i-1<n) s[1000*i+j].insert((i-1)*1000+j);
}
else if(c=='L'){
if(i-1>=0 and i-1<n) s[1000*i+j].insert((i-1)*1000+j);
if(j+1>=0 and j+1<m) s[1000*i+j].insert(i*1000+j+1);
}
else if(c=='J'){
if(j-1>=0 and j-1<m) s[1000*i+j].insert(i*1000+j-1);
if(i-1>=0 and i-1<n) s[1000*i+j].insert((i-1)*1000+j);
}
else p[1000*i+j]=0;
}
for(i=0;i<n;i++)for(j=0;j<m;j++){
if(s[i*1000+j].count((i+1)*1000+j) and s[(i+1)*1000+j].count(i*1000+j)){
combine((i+1)*1000+j, i*1000+j);
}
if(s[i*1000+j].count(i*1000+j+1) and s[i*1000+j+1].count(i*1000+j)){
combine(i*1000+j+1, i*1000+j);
}
}
for(i=0;i<n;i++)for(j=0;j<m;j++){
if(p[i*1000+j]<0)ans=max(ans, p[i*1000+j]*-1);
}
cout << ans << '\n';
return 0;
}
|
Problem 4
投資遊戲
線段樹
dp，紀錄現在用了幾張金牌以及從哪一天退場，於是會有：
1
| dp[j][1]=max(dp[j-1][1]+a[j]-a[j-1], dp[j-1][0]+max(0LL, a[j]-a[j-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
33
34
35
36
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define phb push_back
#define ppb pop_back
#define pii pair<int, int>
#define wh_ale ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define INF (long long) 1e18
#define mod 1e9+7
#define maxn 200010
signed main(){
wh_ale;
int n, k, a[maxn]={}, dp[maxn][2]={}, i, j, x, cur=0, ans=0;
cin >> n >> k;
for(i=1;i<=n;i++){
cin >> x;
a[i]=a[i-1]+x;
cur=min(cur, a[i]);
dp[i][0]=a[i]-cur;
ans=max(ans, dp[i][0]);
}
for(i=1;i<=k;i++){
for(j=1;j<=n;j++){
dp[j][1]=max(dp[j-1][1]+a[j]-a[j-1], dp[j-1][0]+max(0LL, a[j]-a[j-1]));
ans=max(ans, dp[j][1]);
}
for(j=1;j<=n;j++) dp[j][0]=dp[j][1];
}
cout << ans << '\n';
return 0;
}
|
After all
實作順利五級分啦~~~
最後觀念差一題五級分小可惜但沒關係owob