# **APCS實作題解** powered by hamster
* 第1題
算是APCS中簡單的第一題
以變數l跟r分別記錄 左邊食物數量 和 右邊食物數量
for迴圈跑一次e陣列 if(e[i]<x)成立就是左邊l++ 反之在右邊r++
l跟r比較
對大的進行輸出
而最後的位置一定是最右 或 最左
我當初懶惰直接用sort (也可找最大值 和 最小值?
一般sort後 e[0]是最左 e[n-1]是最右
O(nlogn)
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int x,n;
cin>>x>>n;
vector<int> e(n,0);
for(int i=0;i<n;i++)
cin>>e[i];
sort(e.begin(),e.end());
int r=0,l=0;
for(int i=0;i<n;i++){
if(e[i]<x)
l++;
else
r++;
}
if(r>l)
cout<<r<<" "<<e[n-1]<<endl;
else
cout<<l<<" "<<e[0]<<endl;
return 0;
}
```
---
* 第2題
嗯這題有點難解釋
但直接暴力做是沒問題的
最重要的是 甚麼時候停止?
題目有說 其中數字只有0~1000 且每個數字獨特
如果有最差的情況就是每跑一次只解開一個配對
最多就要跑1000多次
所以跑1000多次後就是一定結束了 保險跑1005次owob
(應該可開bool 紀錄每回合有沒有數字被解開
但不能觀查ans值有沒有變化因為會忽略 數字0 被解開的狀況
O(nm*10^3)
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>> v(n,vector<int>(m,0));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
cin>>v[i][j];
}
int ans=0;
for(int l=0;l<1005;l++){
for(int i=0;i<n;i++){
int left=-2,leftj=-2;//紀錄左邊元素
for(int j=0;j<m;j++){
if(left==v[i][j]){
ans+=left;
v[i][j]=-1;
v[i][leftj]=-1;
}
if(v[i][j]==-1)continue;
leftj=j;
left=v[i][j];
}
}
for(int j=0;j<m;j++){
int up=-2,upi=-2;//紀錄上面元素
for(int i=0;i<n;i++){
if(up==v[i][j]){
ans+=up;
v[i][j]=-1;
v[upi][j]=-1;
}
if(v[i][j]==-1)continue;
upi=i;
up=v[i][j];
}
}
}
cout<<ans<<endl;
return 0;
}
```
---
* 第3題
這題有點複雜
直接BFS 就行 DFS容易堆疊溢位
bfs加入點時要先確定兩個有連通
if條件寫好穩穩過
function 當函式看就好不要太糾結(X
O(nm)
```cpp
#include<bits/stdc++.h>
using namespace std;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
struct point{
int x,y;
point(int x,int y):x(x),y(y){
}
};
bool check_next(char c,int d){//確定該位置能接受哪些方向
if(c=='X')return 1;
if(c=='F'&&(d==0||d==1))return 1;
if(c=='H'&&(d==1||d==3))return 1;
if(c=='7'&&(d==0||d==3))return 1;
if(c=='I'&&(d==0||d==2))return 1;
if(c=='L'&&(d==1||d==2))return 1;
if(c=='J'&&(d==3||d==2))return 1;
return 0;
}
bool check_d(char c,int d){//確定所在方向能通往哪裡
if(c=='X')return 1;
if(c=='F'&&(d==3||d==2))return 1;
if(c=='H'&&(d==1||d==3))return 1;
if(c=='7'&&(d==1||d==2))return 1;
if(c=='I'&&(d==0||d==2))return 1;
if(c=='L'&&(d==0||d==3))return 1;
if(c=='J'&&(d==0||d==1))return 1;
return 0;
}
int main(){
int n,m;
cin>>n>>m;
vector<vector<char>> v(n+2,vector<char>(m+2,'0'));
vector<vector<int>> vis(n+2,vector<int>(m+2,0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>v[i][j];
}
}
function<int(int,int)> bfs=[&](int x,int y){
int sum=1;
point s(x,y);
queue<point> q;
q.push(s);
while(!q.empty()){
point p=q.front();
q.pop();
for(int i=0;i<4;i++){
if(!check_d(v[p.x][p.y],i))continue;
int nx=p.x+dx[i],ny=p.y+dy[i];
if(!check_next(v[nx][ny],i))continue;
if(vis[nx][ny])continue;
vis[nx][ny]=1;
sum++;
q.push(point(nx,ny));
}
}
return sum;
};
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!vis[i][j]&&v[i][j]!='0'){
vis[i][j]=1;
ans=max(ans,bfs(i,j));
}
}
}
cout<<ans<<endl;
return 0;
}
```
---
* 第4題
如果k=0 很簡單->dp最大子數列
轉移式是 dp[i]=max(dp[i-1],0)+e[i];
但如果k!=0那就不是了
我們需要幫dp增維進行考慮 -> dp[i][j] 增加j代表用了多少金幣
可得到新的轉移式
`dp[i][j]=max(dp[i][j-1],dp[i-1][j]+e[i],dp[i][j-1])`
dp[i][j-1]好像不用 我考APCS太擔心加的
O(nk)
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,k;
cin>>n>>k;
vector<int> e(n);
vector<vector<int>> dp(n,vector<int>(k+1,0));
for(int i=0;i<n;i++)
cin>>e[i];
int ans=0;
dp[0][0]=e[0];
ans=max(e[0],ans);
for(int i=1;i<n;i++){
dp[i][0]=max(0LL,dp[i-1][0])+e[i];
ans=max(dp[i][0],ans);
for(int j=1;j<=k;j++){
dp[i][j]=max({dp[i-1][j]+e[i],dp[i-1][j-1],dp[i][j-1]});
ans=max(ans,dp[i][j]);
}
}
cout<<ans<<endl;
}
```
**心得**
歷次
祈禱自己實作能有5
owob
Sign in with Wallet
Connect another wallet