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;
}
```
Sign in with Wallet
Connect another wallet