# APCS 20231022 題解
## 前言
我不會指標
## [機械鼠](https://zerojudge.tw/ShowProblem?problemid=m370)
### 想法
先排序,然後看往左走往右走哪邊比較好。
### 時間複雜度
$O(NlgN)$
### code
```cpp=
#include <bits/stdc++.h>
using namespace std;
array<int, 24> F;
signed main(){
int n, pos, l = 0, r = 0;
cin >> pos >> n;
for(int i = 0; i < n; i++){
cin >> F[i];
}
sort(F.begin(), F.begin() + n);
for(int i = 0; i < n; i++){
if(F[i] <= pos) l++;
if(F[i] >= pos) r++;
}
if(l > r) cout << l << " " << F[0];
else cout << r << " " << F[n - 1];
return 0;
}
```
## [卡牌遊戲](https://zerojudge.tw/ShowProblem?problemid=m371)
### 想法
對每個牌找他的另一半是不是在隔壁,然後一直消直到沒東西消。
用 linked list 實做就不用管 $N\ M$ 多大了。
### 時間複雜度
$O(C^2)$
### code
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct linki{
int v;
linki *pre, *nex;
linki(){
v = -1;
pre = nex = nullptr;
}
linki(int x){
v = x;
pre = nex = nullptr;
}
linki* push(int x){
nex = new linki(x), nex->pre = this;
return nex;
}
};
array<linki*, 44> I, J;
array<array<linki*, 2>, 1004> H, V;
array<int, 1004> vis;
void del(linki *l){
l->pre->nex = l->nex;
if(l->nex) l->nex->pre = l->pre;
delete l;
}
int match(){
int p = -1;
for(int i = 0; i <= 1000; i++){
if(vis[i]) continue;
if(H[i][0]->pre == H[i][1] || V[i][0]->pre == V[i][1]){
del(H[i][0]), del(H[i][1]), del(V[i][0]), del(V[i][1]);
p = max(p + i, i);
vis[i] = 1;
}
}
return p;
}
signed main(){
int n, m, sum = 0, p;
cin >> n >> m;
for(int i = 1; i <= n; i++) I[i] = new linki;
for(int j = 1; j <= m; j++) J[j] = new linki;
for(int i = 0; i <= 1000; i++) vis[i] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> p;
H[p][vis[p]] = I[i] = I[i]->push(p);
V[p][vis[p]] = J[j] = J[j]->push(p);
vis[p] = 0;
}
}
while(1){
if((p = match()) < 0) break;
sum += p;
}
cout << sum;
return 0;
}
```
## [搬家](https://zerojudge.tw/ShowProblem?problemid=m372)
### 想法
把全部字母都換成對應的形狀建圖,再砸 D/BFS 跑連通塊大小。
### 時間複雜度
$O(NM)$
聽說 DFS 會被 zerojudge 卡 stack limit
### code
```cpp=
#include <bits/stdc++.h>
using namespace std;
array<int, 4> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
array<array<int, 1504>, 1504> G, vis;
array<array<char, 504>, 504> O;
int a(int x){return 3 * x + 1;}
int b(int x){return 3 * x + 2;}
int c(int x){return 3 * x + 3;}
void build(int x, int y, char p){
if(p == '0') return;
G[b(x)][b(y)] = 1;
if(p == 'X') G[a(x)][b(y)] = G[b(x)][a(y)] = G[b(x)][c(y)] = G[c(x)][b(y)] = 1;
else if(p == 'I') G[a(x)][b(y)] = G[c(x)][b(y)] = 1;
else if(p == 'H') G[b(x)][a(y)] = G[b(x)][c(y)] = 1;
else if(p == 'L') G[a(x)][b(y)] = G[b(x)][c(y)] = 1;
else if(p == 'F') G[c(x)][b(y)] = G[b(x)][c(y)] = 1;
else if(p == '7') G[b(x)][a(y)] = G[c(x)][b(y)] = 1;
else G[b(x)][a(y)] = G[a(x)][b(y)] = 1;
}
int DFS(int x, int y){
if(vis[x][y] || !G[x][y]) return 0;
vis[x][y] = 1;
int sum = 1;
for(int i = 0; i < 4; i++){
sum += DFS(x + dx[i], y + dy[i]);
}
if(x % 3 == 2 && y % 3 == 2) sum -= O[x / 3][y / 3] == 'X'? 4 : 2;
return sum;
}
int BFS(int x, int y){
int sum = 0;
queue<pair<int, int>> Q;
Q.push({x, y});
while(!Q.empty()){
auto [i, j] = Q.front();
Q.pop();
if(vis[i][j] || !G[i][j]) continue;
vis[i][j] = 1;
sum++;
if(i % 3 == 2 && j % 3 == 2) sum -= O[i / 3][j / 3] == 'X'? 4 : 2;
for(int k = 0; k < 4; k++){
Q.push({i + dx[k], j + dy[k]});
}
}
return sum;
}
signed main(){
int n, m, com = 0;
cin >> n >> m;
getchar();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
O[i][j] = getchar();
build(i, j, O[i][j]);
}
getchar();
}
for(int i = 1; i <= 3 * n; i++){
for(int j = 1; j <= 3 * m; j++){
com = max(com, BFS(i, j));
}
}
cout << com;
return 0;
}
```
## [投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373)
### 想法
正常人看到一個 DP 題,有 $N$ 有 $K$ 都會想要砸 aliens。
![](https://hackmd.io/_uploads/SyyPBjXza.jpg)
![](https://hackmd.io/_uploads/HJnPSjmfa.jpg)
砸不了 aliens 我破防了
$DP_{i, j} =$ 第 $i$ 天,用過 $j$ 張金牌。
$DP_{i, 0}$ 就最大連續和
$DP_{i, j} = max(DP_{i - 1, j} + P_i, \ DP_{i - 1, j - 1})$
### 時間複雜度
$O(NK)$
### code
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
array<int, 150004> P;
array<array<int, 24>, 150004> dp;
int DP(int n, int k){
int ans = 0;
for(int i = 1; i <= n; i++){
dp[i][0] = max(dp[i - 1][0], 0ll) + P[i];
ans = max(ans, dp[i][0]);
}
for(int j = 1; j <= k; j++){
for(int i = 1; i <= n; i++){
dp[i][j] = max(dp[i - 1][j] + P[i], dp[i - 1][j - 1]);
ans = max(ans, dp[i][j]);
}
}
return ans;
}
signed main(){
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> P[i];
cout << DP(n, k);
return 0;
}
```