# 111 / 6 / 12 APCS 實作題題解 (C++)
註：因為已經有 Judge 了，這裡不再附上題敘跟測資範圍
## [第一題 數字遊戲](https://zerojudge.tw/ShowProblem?problemid=i399)
這題可能很多人會想要用排序函式，筆者在考試的時候也是利用排序函式 + 陣列完成，但是在這邊我們利用 3 個 swap 完成 bubble sort，且其實枚舉可能性的話會更好寫一些 !
複雜度 $O(1)$ (?
### 解法
```cpp=
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int a, b, c;
cin >> a >> b >> c;
// bubble sort
if(a < b) swap(a, b);
if(b < c) swap(b, c);
if(a < b) swap(a, b);
if(a == b and b == c) cout << 3 << ' ' << a << endl;
else if(a == b or b == c) cout << 2 << ' ' << a << ' ' << c << endl;
else cout << 1 << ' ' << a << ' ' << b << ' ' << c << endl;
// 枚舉可能性
}
```
## [第二題 字串解碼](https://zerojudge.tw/ShowProblem?problemid=i400)
這題跟上次一樣，第二題皆不是二維陣列相關題，且利用 C++ STL 會很方便。
可以知道題目要求正向的操作為：
1. 我們每次需要先確認字串中 1 的數量，確認是否要進行字串調換
2. 利用字串中的 0 或 1，讀取最前或最尾的字元，最後連成一串字串
題目給了最後的字串，求原本的字串。
我們可以知道題目要求的就是逆向操作，那我們要思考的即為如何實現逆向操作。
首先我們必須先作出第二步驟的反向操作。
我們可以逆著遍歷當前的 01 字串，可以知道 1 是將字元從後面取出，0 則是從前面取出，則反向操作即為放在目前字串後面或前面 !
我們在這邊建立一個雙向佇列 (deque)，可以在 $O(1)$ 的時間內在前端或後端放置我們要還原的字串。
接著，我們要逆向執行第一步驟。我們利用迴圈紀錄完 1 在字串的數量後，
可知 交換再交換 會回到原本的字串，那我們也就知道第一步驟的正向和逆向操作是相同的，直接執行第一步驟即可。
重複上述步驟 $N$ 次即可。
複雜度 $O(N \times M)$
註：由於本題 $N, M \leq 100$，不熟悉 deque 的人有幾個替代：
1. 利用 Linked list，複雜度同樣為 $O(N \times M)$
2. 可以直接暴力移動整個陣列，複雜度會多一個層級，為 $O(N \times M^2)$
### 解法
```cpp=
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<string> v(n);
string str;
for(int i = 0; i < n; i++) cin >> v[i];
cin >> str;
for(int i = n - 1; i >= 0; i--) {
deque<char> dq;
string t1, t2;
for(int j = m - 1; j >= 0; j--) {
if(v[i][j] == '1') dq.pb(str[j]);
else dq.push_front(str[j]);
}
int c = 0;
for(int j = 0; j < m; j++) {
if(v[i][j] == '1') c++;
}
if(c & 1) {
if(m & 1) {
for(int j = 0; j < m / 2; j++) t2 += dq[j];
for(int j = m / 2 + 1; j < m; j++) t1 += dq[j];
t1 += dq[m / 2];
}
else {
for(int j = 0; j < m / 2; j++) t2 += dq[j];
for(int j = m / 2; j < m; j++) t1 += dq[j];
}
str = t1 + t2;
}
else {
for(int j = 0; j < m; j++) str[j] = dq[j];
}
}
cout << str << endl;
}
```
## [第三題 雷射測試](https://zerojudge.tw/ShowProblem?problemid=i401)
這題在實作上會較第二題複雜，也算是最近 APCS 的一個趨勢 (?
由於座標範圍到 $3 \times 10^4$，且我們知道走過的路長最長為 $N \times 3 \times 10^4$，直接將鏡子存儲在二維陣列中一步一步走是不行的，會產生 MLE 及 TLE 的情形。
我們可以嘗試對每個鏡子的 $x, y$ 座標點都建立一個陣列，也就是若一個點在 $(3, 5)$，我們可以在以 $x$ 為索引的陣列 ( 這邊稱作 $vx$[ ] )放進 $y$ 座標點及他的 $c$ ( 鏡子方向 )，同理可以放在 $vy$[ ] 裡面，也就是我們可以得到每個 $x, y$ 座標上面有哪些鏡子，位置跟形狀又是如何，最後我們可以將每個 $vx$[ ]、$vy$[ ] 排序。
如 zerojudge 上面的圖片 https://zerojudge.tw/ShowImage?id=2189
:::spoiler **vx、vy 長這樣：**
$vx[1] = \{\{-1, 1\}, \{2, 0\}\}$
$vx[2] = \{\{-1, 1\}, \{0, 1\}\}$
.
.
$vy[1] = \{\{3, 1\}, \{4, 0\}\}$
$vy[2] = \{\{1, 0\}, \{3, 0\}, \{4, 0\}, \{7, 1\}\}$
.
.
( 未完全列出 )
:::
接著，我們每當從一個座標點開始，我們要知道他是往哪個方向走，可以建立一個變數紀錄。我們要知道從這個座標點開始走的下一個點在何處。
由於我們已經將其排序過，如我們要從 $(2, 4)$ 開始向右，我們就可以在 $vx$[2] 利用二分搜找到下一個座標點在哪裡。
接著更改我們的 $vx / vy$ 後，我們就只要利用對應的方向和鏡子形狀就可以調整方向了。
複雜度 $O(N \times logN)$
### 解法
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
const int maxn = 3e4 + 5;
const int ts = 3e4;
vector<pii> vx[2 * maxn], vy[maxn];
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++) {
int x, y, c;
cin >> x >> y >> c;
vx[y + ts].pb({x, c});
vy[x].pb({y, c});
}
for(int i = -3e4; i <= 3e4; i++) sort(all(vx[i + ts]));
for(int i = 0; i <= 3e4; i++) sort(all(vy[i]));
int sx = 0, sy = 0, drt = 1, cnt = 0;
while(true) {
if(drt == 1) {
pii p;
p.f = sx;
p.s = 2;
auto it = upper_bound(all(vx[sy + ts]), p);
if(it == vx[sy + ts].end()) break;
else {
auto [tx, c] = *it;
if(c == 0) {
drt = 2;
sx = tx;
}
else {
drt = 4;
sx = tx;
}
}
}
else if(drt == 3) {
pii p;
p.f = sx;
p.s = 0;
auto it = lower_bound(all(vx[sy + ts]), p);
if(it == vx[sy + ts].begin()) break;
else {
it--;
auto [tx, c] = *it;
if(c == 0) {
drt = 4;
sx = tx;
}
else {
drt = 2;
sx = tx;
}
}
}
else if(drt == 2) {
pii p;
p.f = sy;
p.s = 2;
auto it = upper_bound(all(vy[sx]), p);
if(it == vy[sx].end()) break;
else {
auto [ty, c] = *it;
if(c == 0) {
drt = 1;
sy = ty;
}
else {
drt = 3;
sy = ty;
}
}
}
else{
pii p;
p.f = sy;
p.s = 0;
auto it = lower_bound(all(vy[sx]), p);
if(it == vy[sx].begin()) break;
else {
it--;
auto [ty, c] = *it;
if(c == 0) {
drt = 3;
sy = ty;
}
else {
drt = 1;
sy = ty;
}
}
}
cnt++;
}
cout << cnt << endl;
}
```
## [第四題 內積](https://zerojudge.tw/ShowProblem?problemid=i402)
這題明顯地可以知道直接枚舉兩個陣列的子陣列是不行的，複雜度為 $O(N^3)$，那可以知道我們必須更有效的找到子陣列 !
我們可以想像答案的區間其實就是可以由兩個陣列之間的相對位置組合的一個子陣列，這是什麼意思呢 ?
若測資如下：
```
3 2
-1 2 -5
-2 -3
```
則他的配對方法有以下幾種：
```
-1 2 -5
-2 -3
形成
{3}
-1 2 -5
-2 -3
形成
{2, -6}
-1 2 -5
-2 -3
形成
{-4, 15}
-1 2 -5
-2 -3
形成
{10}
```
可以知道，答案會是 $\{-5\}$ 跟 $\{-3\}$ 的組合，其實可以發現答案都會在 **不同的對應方法** 產生的陣列的 **最大子陣列和**，那我們到這裡就解決這個問題啦 ~
我們只要枚舉對應的方法數，重疊的部分的相乘，產生一新陣列後，那我們在執行最大子陣列和算法，就完成拉 ~
而題目要求可能為逆序的數列，只需反轉 x 陣列 或 y 陣列即可
複雜度為 $O((N + M)^2)$ (? 我不太會算，但大概這樣
### 解法
```cpp=
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n, m, ret = -1e9;
void solve(vector<int>& x, vector<int>& y) {
for(int i = -m + 1; i <= n - 1; i++) {
vector<int> arr;
int ans = -1e9;
for(int j = 0; j < m; j++) {
if(i + j < 0 or i + j >= n) continue;
arr.pb(x[i + j] * y[j]);
}
int pfx = 0;
for(int j = 0; j < arr.size(); j++) {
if(pfx < 0) pfx = 0;
pfx += arr[j];
ans = max(ans, pfx);
}
ret = max(ret, ans);
}
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
vector<int> x(n), y(m);
for(int i = 0; i < n; i++) cin >> x[i];
for(int i = 0; i < m; i++) cin >> y[i];
solve(x, y);
reverse(y.begin(), y.end());
solve(x, y);
cout << ret << endl;
}
```
Sign in with Wallet
Connect another wallet