[APCS] 2023年十月場實作題詳解
前言
久違的寫一下題解，最近因為家教的學生有去考所以最近來寫一下題目 因為沒有實際去考，也沒有實際的成績，這邊的測試都是丟到 ZJ 上面的題目
Problem 1: 機械鼠
基本上有兩種做法：
- 把所有位置讀進來，sort 之後做 lower_bound 掃比他大的跟比他小的有幾個，輸出比較大的順便輸出最前/最後的位置
- 讀位置的同時取最大最小值，並且分別紀錄比他大/小的數字有幾個，同時輸出最大/小值
作法一
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio ( false );
cin.tie ( 0 );
cout.tie ( 0 );
int n, x;
cin >> x >> n;
vector < int > lib ( n );
for ( auto &i: lib )
cin >> i;
sort ( lib.begin(), lib.end() );
int lb = lower_bound ( lib.begin(), lib.end(), x ) - lib.begin();
if ( lb < n - lb )
cout << n - lb << ' ' << lib.back() << endl;
else
cout << lb << ' ' << lib[0] << endl;
}
作法二
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio ( false );
cin.tie ( 0 );
cout.tie ( 0 );
int n, x, ma = -105, mi = 105, cnt1 = 0, cnt2 = 0;
cin >> x >> n;
for ( int i = 0, in ; i < n ; i++ ) {
cin >> in;
ma = max ( ma, in );
mi = min ( mi, in );
if ( in >= x )
cnt1++;
if ( in <= x )
cnt2++;
}
if ( cnt1 > cnt2 )
cout << cnt1 << ' ' << ma << endl;
else
cout << cnt2 << ' ' << mi << endl;
}
Problem 2: 卡牌遊戲
基本上就是暴力匹配，直到沒有新匹配成立的時候就結束 while 迴圈 每次匹配都往四個方向檢查，要注意的是可能有一個方向檢查到匹配了、把 lib[i][j] 改成 -1 了，就不要再繼續檢查，我為了方便起見寫在後面三個 for 迴圈的條件裡
#include<bits/stdc++.h>
using namespace std;
#define maxN 55
int lib[maxN][maxN];
int main() {
ios::sync_with_stdio ( false );
cin.tie ( 0 );
cout.tie ( 0 );
int n, m, ans = 0;
bool flag = true;
cin >> n >> m;
for ( int i = 0 ; i < n ; i++ )
for ( int j = 0 ; j < m ; j++ )
cin >> lib[i][j];
while ( flag ) {
flag = false;
for ( int i = 0 ; i < n ; i++ )
for ( int j = 0 ; j < m ; j++ ) {
if ( lib[i][j] == -1 )
continue;
for ( int k = 1 ; i + k < n ; k++ )
if ( lib[i][j] == lib[i + k][j] ) {
flag = true;
ans += lib[i][j];
lib[i][j] = lib[i + k][j] = -1;
break;
}
else if ( lib[i + k][j] != -1 )
break;
for ( int k = 1 ; 0 <= i - k && lib[i][j] != -1 ; k++ )
if ( lib[i][j] == lib[i - k][j] ) {
flag = true;
ans += lib[i][j];
lib[i][j] = lib[i - k][j] = -1;
break;
}
else if ( lib[i - k][j] != -1 )
break;
for ( int k = 1 ; j + k < m && lib[i][j] != -1 ; k++ )
if ( lib[i][j] == lib[i][j + k] ) {
flag = true;
ans += lib[i][j];
lib[i][j] = lib[i][j + k] = -1;
break;
}
else if ( lib[i][j + k] != -1 )
break;
for ( int k = 1 ; 0 <= j - k && lib[i][j] != -1 ; k++ )
if ( lib[i][j] == lib[i][j - k] ) {
flag = true;
ans += lib[i][j];
lib[i][j] = lib[i][j - k] = -1;
break;
}
else if ( lib[i][j - k] != -1 )
break;
}
}
cout << ans << endl;
}
Problem 3: 搬家
簡單來說就是檢查最大的水管聯通塊，所以寫一個 dfs 或 bfs 掃過去就好 不過要注意兩個相鄰的水管中間有沒有聯通，可能有其中一個方向不對就不聯通了
這邊我是用兩個 function check_d 和 check_next，分別檢查當前節點可以轉移的位置、和下一個位置能接受的轉移方向
另外這邊我使用轉移矩陣來檢查，所以這兩個 functino 中的 d 是對照到轉移矩陣的 index
#include<bits/stdc++.h>
using namespace std;
#define maxN 505
char lib[maxN][maxN];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 };
bool vis[maxN][maxN];
bool check_d ( int x, int y, int d ) {
if ( lib[x][y] == 'X' )
return true;
if ( lib[x][y] == 'I' && d % 2 == 1 )
return true;
if ( lib[x][y] == 'H' && d % 2 == 0 )
return true;
if ( lib[x][y] == 'L' && ( d == 0 || d == 3 ) )
return true;
if ( lib[x][y] == '7' && ( d == 1 || d == 2 ) )
return true;
if ( lib[x][y] == 'F' && ( d == 0 || d == 1 ) )
return true;
if ( lib[x][y] == 'J' && ( d == 3 || d == 2 ) )
return true;
return false;
}
bool check_next ( int x, int y, int d ) {
if ( lib[x][y] == 'X' )
return true;
if ( lib[x][y] == 'I' && d % 2 == 1 )
return true;
if ( lib[x][y] == 'H' && d % 2 == 0 )
return true;
if ( lib[x][y] == 'L' && ( d == 1 || d == 2 ) )
return true;
if ( lib[x][y] == '7' && ( d == 0 || d == 3 ) )
return true;
if ( lib[x][y] == 'F' && ( d == 2 || d == 3 ) )
return true;
if ( lib[x][y] == 'J' && ( d == 0 || d == 1 ) )
return true;
return false;
}
int bfs ( int x, int y ) {
int nx, ny, res = 1;
queue < pair < int, int > > q;
q.push ( make_pair ( x, y ) );
vis[x][y] = true;
while ( !q.empty() ) {
x = q.front().first, y = q.front().second;
q.pop();
for ( int d = 0 ; d < 4 ; d++ ) {
if ( !check_d ( x, y, d ) )
continue;
nx = x + dx[d], ny = y + dy[d];
if ( !check_next ( nx, ny, d ) )
continue;
if ( vis[nx][ny] )
continue;
vis[nx][ny] = true;
res++;
q.push ( make_pair ( nx, ny ) );
}
}
return res;
}
int main() {
ios::sync_with_stdio ( false );
cin.tie ( 0 );
cout.tie ( 0 );
int n, m, ma = 0;
cin >> n >> m;
for ( int i = 0 ; i <= n + 1 ; i++ )
for ( int j = 0 ; j <= m + 1 ; j++ )
lib[i][j] = '0';
for ( int i = 1 ; i <= n ; i++ )
for ( int j = 1 ; j <= m ; j++ )
cin >> lib[i][j];
for ( int i = 1 ; i <= n ; i++ ) {
for ( int j = 1 ; j <= m ; j++ ) {
if ( vis[i][j] || lib[i][j] == '0' )
continue;
ma = max ( bfs ( i, j ), ma );
}
}
cout << ma << endl;
}
Problem 4: 投資遊戲
基本上就是裸 dp
#include<bits/stdc++.h>
using namespace std;
#define maxN 150005
#define maxK 25
long long dp[maxN][maxK], lib[maxN];
int main() {
ios::sync_with_stdio ( false );
cin.tie ( 0 );
cout.tie ( 0 );
int n, k;
long long ans;
cin >> n >> k;
for ( int i = 0 ; i < n ; i++ )
cin >> lib[i];
dp[0][0] = lib[0];
ans = max ( 0ll, lib[0] );
for ( int i = 0 ; i < n ; i++ ) {
ans = max ( ans, dp[i][0] = max ( 0ll, dp[i - 1][0] ) + lib[i] );
for ( int j = 1 ; j <= k ; j++ ) {
ans = max ( ans, dp[i][j] = max ( dp[i - 1][j] + lib[i], dp[i - 1][j - 1] ) );
}
}
cout << ans << endl;
}
大概就是這樣，久違的寫個題目，如果有去考應該是可以順利五級分（吧