# APCS 2023/6 題解
## ==路徑偵測==
### <font color="0E81A6">敘述</font>
給一個二維平面，座標如同數學的二維座標(Ｙ正為北，Ｘ正為東)。
起始位置在 (0, 0)，接下來會有n個座標，你需要按照這些座標點的順序移動，保證僅會垂直或水平方向上移動，不會斜向移動，且第一個點保證一定是Ｘ軸正的位置(初始方向向右)。
請輸出這條路徑中，左轉、右轉、迴轉的個數分別為多少。
### <font color="0E81A6">輸入說明</font>
第一行輸入一個正整數n，接下來有n行，每一行都有兩個正整數x,y。
保證的是相鄰兩個點的座標差值不超過100。
### <font color="0E81A6">輸出說明</font>
輸出三個正整數，分別代表左轉、右轉、迴轉的次數。
### <font color="E3A506">核心</font>
陣列、外積、條件判斷
### <font color="E3A506">思路</font>
會外積這題就會輕鬆很多。
dir是z軸向量的方向。
```c++=
#include <bits/stdc++.h>
using namespace std;
struct point
{
int x=0,y=0;
}p[105];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
int dir,left=0,right=0,turn=0;
int x1,x2,y1,y2;
for(int i=2;i<=n;i++)
{
x1=p[i-1].x-p[i-2].x,y1=p[i-1].y-p[i-2].y;
x2=p[i].x-p[i-1].x,y2=p[i].y-p[i-1].y;
dir=x1*y2-x2*y1;
if(dir>0) left++;
else if(dir<0) right++;
else
{
if(x1*x2<0||y1*y2<0) turn++;
}
}
printf("%d %d %d\n",left,right,turn);
}
```
## ==特殊位置==
### <font color="0E81A6">敘述</font>
給定一個n x m的二維矩陣a，設 x = a[i][j]，離(i,j)曼哈頓距離為 x 內的點數值總和 % 10 恰為 x 的稱之為特殊位置。定義兩個點 (a, b) 和 (c, d) 的曼哈頓距離為 |a - c| + |b - d|。
請寫一個程式，輸出共有幾個特殊位置，並按照字典序由小到大輸出這些位置的座標。
### <font color="0E81A6">輸入說明</font>
第一行輸入兩個正整數 n , m (1<= n , m <= 50) ，接下來有 n 行，每行有 m 個數字，每一個數字介於 0 到 9 。
### <font color="0E81A6">輸出說明</font>
第一行輸出共有幾個特殊位置，接下來輸出 k 行，每一行輸出兩個正整數代表作標點位。特殊位置請按照字典順序由小到大輸出。
### <font color="E3A506">核心</font>
二維陣列、模擬
### <font color="E3A506">思路</font>
只需注意檢查邊界。
```c++=
#include<bits/stdc++.h>
using namespace std;
int M[55][55];
int X[55*55],Y[55*55];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&M[i][j]);
int num=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int sum=0;
for(int x=max(0,i-M[i][j]);x<min(n,i+M[i][j]+1);x++)
{
for(int y=max(0,j-M[i][j]);y<min(m,j+M[i][j]+1);y++)
{
if(abs(x-i)+abs(y-j)<=M[i][j]) sum+=M[x][y];
}
}
sum%=10;
if(sum==M[i][j]) X[num]=i,Y[num]=j,num++;
}
}
printf("%d\n",num);
for(int i=0;i<num;i++) printf("%d %d\n",X[i],Y[i]);
}
```
## ==磁軌移動序列==
### <font color="0E81A6">敘述</font>
你拿到一個磁帶和一串指令。磁帶上的指針初始位置為 10，我們將其表示為 T10。指令是一個由多個 T 和 loop 指令組成的字串，每個指令都會影響指針的移動。
T 指令的格式為 Txx，其中 xx 是兩位數的整數（10~99），代表指針從當前位置移動到 xx 所指示的位置。
除了 T 指令外，還有一個 loop 指令結構，其格式為 Lx...E，其中 x 是一位數的整數（1~9）。loop 指令允許重複執行一系列指令。loop 指令的開始標記為 Lx，結束標記為 E，指令序列位於這兩個標記之間。loop 指令可以嵌套，也就是說，一個 loop 指令的內部可以包含其他的 loop 指令。保證所有 loop 指令內一定會有至少一個 T 指令。
請寫一個程式，根據給定的指令串，計算指針總共移動的距離。
範例： 給定指令串：T10T15T23T23T22T22T44 指針總共移動的距離為：5 + 8 + 0 + 1 + 0 + 22 = 36
字串長度不超過10^5^，總距離不超過2^60^
### <font color="0E81A6">輸入說明</font>
輸入一個字串，為該磁帶指針的控制指令。
### <font color="0E81A6">輸出說明</font>
輸出一個正整數，代表指針執行完指令後所移動的總路徑長。
### <font color="E3A506">核心</font>
queue、遞迴
### <font color="E3A506">思路</font>
有點像有括號的四則運算，由最裡層的嵌套往外計算。
last記錄每層嵌套的最左端，注意檢查和更新!
before為now往後探勘後的當前位置，now檢查到個位數，表示遇到一層嵌套，進行遞歸，若不是則計算距離並右移before。
若此嵌套需執行times次，則嵌套內距離將乘上times，注意嵌套最左端位置和最右端位置的距離只需乘times - 1次。接著將此嵌套的總距離返回給外層嵌套，內層就無需再理會了，很好理解，若外層執行k次，則外層的總距離為 ( 內層總距離 + 外層進入內層)* k + 外層左右端位置距離* (k-1)，移此類推。
每層嵌套會返回它的最左端位置(給外層進入)、最右端位置以及總距離，分別是last、before、total_distance。
last要注意檢查!!!若<10則此嵌套開頭為內層嵌套，需更新為內層嵌套的最左端位置。
before的更新很好懂，不多做解釋。
```c++=
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define piii pair<pair<int,int>,int>
#define ff first.first
#define fs first.second
#define s second
queue<int> Q;
piii caculate()
{
int before = Q.front();
int last = Q.front();
int total_distance = 0;
while (Q.front()!=-1)
{
int now = Q.front();
Q.pop();
if (now >= 10)
{
total_distance += abs(now - before);
before = now;
}
else
{
piii in = caculate();
total_distance += (in.s) * now;
total_distance += abs(in.fs - in.ff) * (now - 1);
if(last<10) last=in.ff;
else total_distance+=abs(before-in.ff);
before=in.fs;
}
}Q.pop();
return {{last, before}, total_distance};
}
signed main()
{
char ch;
int num;
while (scanf("%c", &ch) != EOF)
{
if (ch == '\n') break;
else if (ch == 'T') scanf("%d", &num), Q.push(num); // num >= 10
else if (ch == 'L') scanf("%d", &num), Q.push(num); // num < 10
else if (ch == 'E') Q.push(-1);
}
Q.push(-1);
piii ans = caculate();
printf("%lld\n", ans.s+abs(10-ans.ff));
}
```
## ==開啟寶盒==
### <font color="0E81A6">敘述</font>
已知有 n 個寶盒編號 0~n-1 以及 m 種鑰匙編號 0~m-1。一開始你有 t
種鑰匙分別為x1,...,xt。
每一個寶盒要打開都需要同時擁有 k 種鑰匙，第 i 個寶盒分別需要 ri1,...,rik 種類的鑰匙。每個寶盒打開後都會得到 k 種鑰匙，第 i 個寶盒打開後分別會得到 si1,...,sik 種類的鑰匙，當拿到新的鑰匙之後可以繼續開啟新的寶盒。保證寶盒內的鑰匙不會重複，並且每種鑰匙可以開啟的寶盒數量不超過60。
請輸出最多可以開啟多少個寶盒。
### <font color="0E81A6">輸入說明</font>
第一行輸入三個正整數 n,m,k，代表有 n 個寶盒，m 種鑰匙以及每個寶盒需要的鑰匙數量 k。
接下來輸入一行，第一個數字 t 代表一開始有的鑰匙種類數量，後面有 t 個數字代表這些鑰匙分別的種類。
接下來有 n 行，每一行有 k 個數字，代表要開啟第 i 個寶盒的第 j 種鑰匙為 rij。
最後有 n 行，每一行有 k 個數字，代表開啟第 i 個寶盒後得到的第 j 種鑰匙為 sij 。
### <font color="E3A506">核心</font>
圖論、BFS
### <font color="E3A506">思路</font>
暴力解肯定超時，此題必須在O(n)內。
試想一下，已知每個寶盒需要的鑰匙，換句話說，已知哪種鑰匙能打開此寶盒。
我們記錄which鑰匙能打開which種寶盒為keysOpen陣列，which寶盒能給which種鑰匙為boxsGive陣列。
boxsCount記錄每個寶盒剩餘所需鑰匙數。
答案呼之欲出了!!
我們只需走訪所獲得的鑰匙就好了，看它能打開哪種寶盒並獲得哪種鑰匙。
以queue記錄手頭上的鑰匙，每拿一把，就開它能開的寶盒i，然後丟掉這把鑰匙，
boxsCount[i]- -，if boxsCount[i]==0，寶盒打開，欣賞它的鑰匙並搶走，推入queue。但很可惜的是，已經看過的鑰匙就不用拿了，別氣憤，因為時間不允許。
```c++=
#include<bits/stdc++.h>
using namespace std;
#define N 100005
vector<int> boxsGive[N];
vector<int> keysOpen[N];
int boxsCount[N];
queue<int> own;
bool keysHave[N]={false};
int main()
{
int n,m,k,t;
scanf("%d%d%d%d",&n,&m,&k,&t);
int key;
for(int i=0;i<t;i++) scanf("%d",&key),keysHave[key]=true,own.push(key);
for(int i=0;i<n;i++)
{
for(int j=0;j<k;j++) scanf("%d",&key),keysOpen[key].push_back(i);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<k;j++) scanf("%d",&key),boxsGive[i].push_back(key);
}
for(int i=0;i<n;i++) boxsCount[i]=k;
int ans=0;
while(!own.empty())
{
key=own.front();
own.pop();
for(int num:keysOpen[key])
{
boxsCount[num]--;
if(boxsCount[num]==0)
{
ans++;
for(int get:boxsGive[num])
{
if(keysHave[get]==false) keysHave[get]=true,own.push(get);
}
}
}
}
printf("%d\n",ans);
}
```
Sign in with Wallet
Connect another wallet