---
# System prepended metadata

title: apcs模擬考題解

---

apcs模擬考題解
by Cecill
# 1. 程式交易
### 考點: 基本語法
### 難度: ⭐
## 參考程式碼
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,d,x,earn,sellp,pr=-1;
int main()
{
    cin>>n>>d;
    for(int i=1; i<=n; i++)
    {
        cin>>x;
        if(i==1) pr=x;
        else if(pr!=-1 && x>=pr+d) earn+=x-pr,sellp=x,pr=-1;
        else if(pr==-1 && x<=sellp-d) pr=x;
    }
    cout<<earn<<endl;
    return 0;
}
```
<br>

# 2. 購物車
### 考點: 基本語法
### 難度: ⭐
## 參考程式碼
```cpp
#include<bits/stdc++.h>
using namespace std;
int a,b,n,c,res,x,y;
int main()
{
    cin>>a>>b>>n;
    for(int i=1; i<=n; i++)
    {
        x=0,y=0;
        while(cin>>c,c)
        {
            x+=(abs(c)==a)?(c/abs(c)):0;
            y+=(abs(c)==b)?(c/abs(c)):0;
        }
        if(x && y) res++;
    }
    cout<<res<<endl;
    return 0;
}
```
<br>

# 3. 巴士站牌
### 考點: 基本語法
### 難度: ⭐
## 參考程式碼
```cpp
#include<bits/stdc++.h>
using namespace std;
int px,py,x,y,n,res,res2=INT_MAX;
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>x>>y;
        if(i!=1)
        {
            res=max(res,abs(px-x)+abs(py-y));
            res2=min(res2,abs(px-x)+abs(py-y));
        }
        px=x,py=y;
    }
    cout<<res<<" "<<res2<<endl;
    return 0;
}
```
<br>

# 4. 生產線
### 考點: 差分
### 難度: ⭐⭐
## 思路
1. 根據題目敘述，最終的時間花費會是 w[1]*t1 + w[2]*t2 + w[3]*t3 + .... w[n]*t4
所以我們要讓他最小，只需將最大的w[i] * 最小的 t[i] 即可 ， 第二大的 * 第二小的 .... 依此類推，所以排個序即可。
2. 然後一開始要多次讓某段區間+w[i]，可以想到用差分來快速處理這種操作。

複雜度O(nlogn) n為機器數量
## 參考程式碼
```cpp
#include<bits/stdc++.h> 
using namespace std;
const int N=2e5+10;
long long n,m,t[N],s[N];
int main()
{
    cin.tie(0),cin.sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int l,r,w;
        cin>>l>>r>>w;
        s[l]+=w,s[r+1]-=w; 
    }
    for(int i=1; i<=n; i++) s[i]+=s[i-1];
    for(int i=1; i<=n; i++) cin>>t[i];
    sort(s+1,s+1+n,greater<int>()); 
    sort(t+1,t+1+n);
    long long res=0;
    for(int i=1; i<=n; i++) res+=s[i]*t[i];
    cout<<res<<endl;
    return 0;
}
```
<br>

# 5. 贏家預測
### 考點: 基本語法
### 難度: ⭐⭐
## 思路
vwin 表示那些贏的人、vlose 表示那些輸的人、v 代表當前剩餘的人
然後依照題目敘述模擬即可
## 參考程式碼
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1010;
int n,m,x;
LL att[N],exatt[N],lose[N];
vector<int> v;
vector<int> vwin,vlose;
void wcmp(int x,int y)
{
    LL a=att[x],b=exatt[x],c=att[y],d=exatt[y];
    if(a*b>=c*d)
    {
        att[x]=a+(c*d)/(2ll*b),exatt[x]=b+(c*d)/(2ll*a);
        att[y]=c+c/2ll,exatt[y]=d+d/2ll;
        vwin.push_back(x);
        if(++lose[y]<m) vlose.push_back(y);
    }
    else
    {
        att[y]=c+(a*b)/(2*d),exatt[y]=d+(a*b)/(2*c);
        att[x]=a+a/2,exatt[x]=b+b/2;
        vwin.push_back(y);
        if(++lose[x]<m) vlose.push_back(x);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>att[i];
    for(int i=1; i<=n; i++) cin>>exatt[i];
    for(int i=1; i<=n; i++)
    {
        cin>>x;
        v.push_back(x);
    }
    while(v.size()>1)
    {
        vwin.clear();
        vlose.clear();
        for(int i=0; i<v.size(); i+=2)
        {
            if(v.size()%2 && i==v.size()-1) vwin.push_back(v[i]);
            else
            {
                int a=v[i],b=v[i+1];
                wcmp(a,b);
            }
        }
        v.clear();
        for(int i=0; i<vwin.size(); i++) v.push_back(vwin[i]);
        for(int i=0; i<vlose.size(); i++) v.push_back(vlose[i]);
    }
    cout<<v[0]<<endl;
    return 0;
}
```
# 6. 動線安排
### 考點: 基本語法
### 難度: ⭐⭐⭐
## 思路
我們定義 題目中的線跟木樁以及空格為以下
直的線=1、橫的線=2、直跟橫都有=3、木樁為-1、空格為-2

所以往右或往左移除某個線 則
2 -> -2
3 -> 1
往上或往下移除某個線 則
1 -> -2
3 -> 2

所以往右或往左添加某個線 則
-2 -> 2
1 -> 3
往上或往下添加某個線 則
-2 -> 1
2 -> 3
## 參考程式碼
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,t,res;
int g[N][N]; //1=| 2=- 3=+  '@'=-1 '.'=-2;
void rmvx(int x,int y)
{
    g[x][y]=-2;
    for(int j=y+1; j<=m; j++) //right
    {
        if(g[x][j]==3) g[x][j]=1;
        else if(g[x][j]==2) g[x][j]=-2;
        else break;
    }
    
    for(int j=y-1; j>=1; j--) //left
    {
        if(g[x][j]==3) g[x][j]=1;
        else if(g[x][j]==2) g[x][j]=-2;
        else break;
    }
    
    for(int i=x+1; i<=n; i++) //down
    {
        if(g[i][y]==3) g[i][y]=2;
        else if(g[i][y]==1) g[i][y]=-2;
        else break;
    }
    
    for(int i=x-1; i>=1; i--) //up
    {
        if(g[i][y]==3) g[i][y]=2;
        else if(g[i][y]==1) g[i][y]=-2;
        else break;
    }
}
void addx(int x,int y)
{
    if(g[x][y]>=1) rmvx(x,y);
    g[x][y]=-1;
    for(int j=y+1; j<=m; j++) //right
    {
        if(g[x][j]==-1)
        {
            for(int k=y+1; k<j; k++)
            {
                if(g[x][k]==-2) g[x][k]=2;
                else if(g[x][k]==1) g[x][k]=3;
            }
            break;
        }
    }
    
    for(int j=y-1; j>=1; j--) //left
    {
        if(g[x][j]==-1)
        {
            for(int k=y-1; k>j; k--) 
            {
                if(g[x][k]==-2) g[x][k]=2;
                else if(g[x][k]==1) g[x][k]=3;
            }
            break;
        }
    }
    
    for(int i=x+1; i<=n; i++) //down
    {
        if(g[i][y]==-1)
        {
            for(int k=x+1; k<i; k++)
            {
                if(g[k][y]==-2) g[k][y]=1;
                else if(g[k][y]==2) g[k][y]=3;
            }
            break;
        }
    }
    
    for(int i=x-1; i>=1; i--) //up
    {
        if(g[i][y]==-1)
        {
            for(int k=x-1; k>i; k--)
            {
                if(g[k][y]==-2) g[k][y]=1;
                else if(g[k][y]==2) g[k][y]=3;
            }
            break;
        }
    }
}
int calc()
{
    int sum=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(g[i][j]==-1 || g[i][j]>=1)
                sum++;
    return sum;
}
int main()
{
    cin>>n>>m>>t;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            g[i][j]=-2;
    
    for(int i=1; i<=t; i++)
    {
        int x,y,type;
        cin>>x>>y>>type;
        if(type==0) addx(x+1,y+1);
        else if(type==1) rmvx(x+1,y+1);
        res=max(res,calc());
    }
    cout<<res<<"\n"<<calc();
    return 0;
}
```
<br>

# 7. 基地台
### 考點: 二分搜
### 難度: ⭐⭐⭐
## 思路
1. 如果某個直徑x滿足能使每個服務點都可以得到服務則>x的直徑一定也滿足
2. 如果某個直徑x不滿足能使每個服務點都可以得到服務則<x的直徑一定也不滿足，
基於這兩點，所以可以二分

二分的check(mid)函式:

基於以下兩點，所以如果第i個服務點的座標>當前服務到的範圍,則可以貪心的在架設一個基地台到p[i]這個座標
1. 假如放在<p[i]的位置,則一定不會比放在p[i]更好
2. 放在>p[i]的位置,則第i個服務點不會被服務到

時間複雜度: O(nlogk) n為服務點數量、k為座標
## 參考程式碼
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int p[N];
int n,k;
bool check(int r)
{
    int cur=0,cnt=0; 
    for(int i=1; i<=n; i++)
        if(p[i]>cur) cnt++,cur=p[i]+r;
    return cnt<=k;
}
int main()
{
    cin.tie(0),cin.sync_with_stdio(0);
    cin>>n>>k;
    for(int i=1; i<=n; i++) cin>>p[i];
    sort(p+1,p+1+n);
    int l=0,r=p[n];
    while(l<r) 
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid; 
        else l=mid+1; 
    }
    cout<<l<<endl;
    return 0;
}
```
<br>

# 8. 邏輯電路
### 考點: 拓撲排序 or DFS
### 難度: ⭐⭐⭐⭐
## 思路
根據題目敘述，為一個有向無環圖，所以對於某個點x的輸出值以及最大延遲，可以先把所有他的前驅處理完，變可求出該點，因此可以想到用拓撲排序。

1. 我們定義f[i]表示已i為終點的輸出值，delay[i]為已i為終點的最大延遲
2. 拓排過程:
2-1 
首先起點為所有一開始已知的f[i]，也就是那些輸入端口
2-2 
當枚舉到某個邏輯閘，代表他的某個前驅點已得到，可以先用另一個陣列存起來，當所有前驅都得到(也就是入度為零時)，即可得知該點的最大延遲以及輸出，此時這個點就可以用於計算更後面的點了，因次加入對列

時間複雜度: O(n+m) n為點數、m為邊數
## 參考程式碼
```cpp 
#include<bits/stdc++.h>
using namespace std;
const int N=(2e3+5e4+10),M=N*2;
int p,q,r,m,f[N],delay[N],type[N],ind[N],res;
int h[N],ne[M],e[M],idx;
vector<int> v[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool calc(int type,bool a,bool b)
{
    if(type==1) return a&b;
    else if(type==2) return a|b;
    else return a^b;
}
void topsort()
{
    queue<int> qu;
    for(int i=1; i<=p; i++) qu.push(i);

    while(qu.size())
    {
        auto t=qu.front();
        qu.pop();
        for(int i=h[t]; ~i; i=ne[i])
        {
            int j=e[i];
            if(j>=p+1 && j<=p+q)
            {
                v[j].push_back(f[t]);
                delay[j]=max(delay[j],delay[t]+1);
                if(--ind[j]==0)
                {
                    if(type[j]==4) f[j]=!v[j][0];
                    else f[j]=calc(type[j],v[j][0],v[j][1]);
                    qu.push(j);
                }
            }
            else
            {
                f[j]=f[t];
                delay[j]=max(delay[j],delay[t]);
            }
            res=max(res,delay[j]);
        }
    }
}
int main()
{
    cin.tie(0),cin.sync_with_stdio(0);
    memset(h,-1,sizeof h);
    cin>>p>>q>>r>>m;
    for(int i=1; i<=p; i++) cin>>f[i];
    for(int i=p+1; i<=p+q; i++) cin>>type[i];
    for(int i=0; i<m; i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        ind[b]++;
    }
    topsort();
    cout<<res<<endl;
    for(int i=p+q+1; i<=p+q+r; i++) cout<<f[i]<<" ";
    return 0;
}
```
<br>

# 9. 開啟寶盒
### 考點: 拓撲排序
### 難度: ⭐⭐⭐⭐
## 思路
根據題目敘述，每個寶盒都需要一些前驅點鑰匙來開啟他，且開啟寶盒後又可以獲得某些鑰匙，所以我們可以依照某種順序來模擬開啟的過程，把鑰匙跟寶盒視為圖上的點，且這樣的圖是個有向無環圖，因此可以想到拓撲排序。

1. 我們可把鑰匙跟寶盒視為圖上的點，我們假設0~n-1是寶盒 n~n+m-1是鑰匙
2. 對於某個寶盒，我們可以讓鑰匙指向他，每需要一種不同鑰匙就把他的入度+1
3. 拓排過程:
3-1 
首先起點會是一開始獲得的鑰匙，也就是入度為0的點，放入對列。
3-2 
對於某個鑰匙而言當枚舉到某個寶箱指向他時，即可加入隊列。
3-3 
對於某個寶箱而言當入度為零表示所有它的前驅(鑰匙)，都已被搜索到，即可加入隊列。

時間複雜度: O(n+m) n為點數、m為邊數
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2*(1e5+10),M=2*5e5+10;
int n,m,k,x,t,res;
int h[N],ne[M],e[M],idx,ind[N];
bool isit[N];
vector<int> key;
//0~n-1 is box n~n+m-1 is key
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void topsort()
{
    queue<int> q;
    for(auto i:key)
    {
        isit[i]=true;
        q.push(i);
    }

    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=h[t]; ~i; i=ne[i])
        {
            int j=e[i];
            if(j>=n && !isit[j])
            {
                isit[j]=true;
                q.push(j);
            }
            else if(j<n && --ind[j]==0)
            {
                res++;
                q.push(j);
            }
        }
    }
}
int main()
{
    cin.tie(0),cin.sync_with_stdio(0);
    memset(h,-1,sizeof h);
    cin>>n>>m>>k;
    cin>>t;
    for(int i=1; i<=t; i++)
    {
        cin>>x;
        key.push_back(x+n);
    }
    for(int i=0; i<n; i++)
    {
        for(int j=1; j<=k; j++)
        {
            cin>>x;
            add(x+n,i);
            ind[i]++;
        }
    }
    for(int i=0; i<n; i++)
    {
        for(int j=1; j<=k; j++)
        {
            cin>>x;
            add(i,x+n);
            ind[x+n]++;
        }
    }
    topsort();
    cout<<res<<endl;
    return 0;
}
```
<br>

# 10. 搬家
## 考點: BFS or DFS
## 難度: ⭐⭐⭐⭐⭐
## 思路
## 假如你這題是用DFS且拿到(95% RE)，那你是對的，會錯是因為zerojudge的棧空間不夠用，把他等價改為BFS後你就能AC。
這題其實思路很簡單，只是實作比較複雜
1. 首先各種水管我們開個pair陣列存放水管到達的下一個點所需添加的x、y偏移量。
2. 判斷某個水管是否能接在另一個水管，我們可以在另外寫一個function，傳入(當前x,當前y,上一個x,上一個y) 來判斷方向。
3. 使用BFS模擬，當遍歷到新的可行水管時cnt++，然後繼續搜索下去，當不能搜索就return並重新計算cnt，答案就會是所有cnt(連通塊)取max。

時間複雜度: O(n*m) nm為行數和列數
```cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair<int,int> PII;
const int N=510;
int n,m,cnt,res;
bool isit[N][N];
char g[N][N];
PII df[2]= {{0,1},{1,0}};
PII dh[2]= {{0,-1},{0,1}};
PII ds[2]= {{0,-1},{1,0}};
PII di[2]= {{-1,0},{1,0}};
PII dx[4]= {{-1,0},{1,0},{0,-1},{0,1}};
PII dl[2]= {{0,1},{-1,0}};
PII dj[2]= {{0,-1},{-1,0}};
struct point
{
    int x,y,prex,prey;
};
bool valid(int x,int y)
{
    if(g[x][y]=='0') return false;
    if(x<=0 || x>n || y<=0 || y>m) return false;
    return true;
}
int type(int x,int y,int prex,int prey)
{
    if(x==prex && y<prey) return 1;//rtol
    else if(x==prex && y>prey) return 2;//ltor
    else if(y==prey && x<prex) return 3;//dtou
    else if(y==prey && x>prex) return 4;//utod
    else if(prex==-1) return -1;
    return -1;
}
void bfs(int a,int b,int c,int d)
{
    queue<point> q;
    q.push({a,b,c,d});
    while(q.size())
    {
        auto u=q.front();
        q.pop();
        int x=u.x,y=u.y,prex=u.prex,prey=u.prey;

        if(isit[x][y]) continue;

        int t=type(x,y,prex,prey);
        bool canpass=false;

        if(g[x][y]=='F' && (t==-1 || t==1 || t==3)) canpass=true;
        else if(g[x][y]=='H' && (t==-1 || t==1 || t==2)) canpass=true;
        else if(g[x][y]=='7' && (t==-1 || t==2 || t==3)) canpass=true;
        else if(g[x][y]=='I' && (t==-1 || t==3 || t==4)) canpass=true;
        else if(g[x][y]=='X') canpass=true;
        else if(g[x][y]=='L' && (t==-1 || t==1 || t==4)) canpass=true;
        else if(g[x][y]=='J' && (t==-1 || t==2 || t==4)) canpass=true;

        if(!canpass) continue;
        cnt++;
        isit[x][y]=true;

        if(g[x][y]=='F')
        {
            for(int i=0; i<2; i++)
            {
                int nx=x+df[i].F,ny=y+df[i].S;
                if(!isit[nx][ny] && valid(nx,ny)) q.push({nx,ny,x,y});
            }
        }
        if(g[x][y]=='H')
        {
            for(int i=0; i<2; i++)
            {
                int nx=x+dh[i].F,ny=y+dh[i].S;
                if(!isit[nx][ny] && valid(nx,ny)) q.push({nx,ny,x,y});
            }
        }
        if(g[x][y]=='7')
        {
            for(int i=0; i<2; i++)
            {
                int nx=x+ds[i].F,ny=y+ds[i].S;
                if(!isit[nx][ny] && valid(nx,ny)) q.push({nx,ny,x,y});
            }
        }
        if(g[x][y]=='I')
        {
            for(int i=0; i<2; i++)
            {
                int nx=x+di[i].F,ny=y+di[i].S;
                if(!isit[nx][ny] && valid(nx,ny)) q.push({nx,ny,x,y});
            }
        }
        if(g[x][y]=='X')
        {
            for(int i=0; i<4; i++)
            {
                int nx=x+dx[i].F,ny=y+dx[i].S;
                if(!isit[nx][ny] && valid(nx,ny)) q.push({nx,ny,x,y});
            }
        }
        if(g[x][y]=='L')
        {
            for(int i=0; i<2; i++)
            {
                int nx=x+dl[i].F,ny=y+dl[i].S;
                if(!isit[nx][ny] && valid(nx,ny)) q.push({nx,ny,x,y});
            }
        }
        if(g[x][y]=='J')
        {
            for(int i=0; i<2; i++)
            {
                int nx=x+dj[i].F,ny=y+dj[i].S;
                if(!isit[nx][ny] && valid(nx,ny)) q.push({nx,ny,x,y});
            }
        }

    }
}
int main()
{
    cin.tie(0),cin.sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>g[i][j];
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(!isit[i][j] && g[i][j]!='0')
            {
                cnt=0;
                bfs(i,j,-1,-1);
                res=max(res,cnt);
            }
        }
    }
    cout<<res<<endl;
    return 0;
}
```
