# APCS 2021年11月題解
## 第一題 修補圍籬
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=g595
### 解套
給一大小為n的陣列$h[0],h[1],...h[n-1]$，求$\sum_{i=0}^{n-1} if(h[i]=0)min(h[i-1],h[i+1])$
### 題目分析
直接遍歷，遇到數值為0的就更新答案
另外因為0有可能位在邊界，所以這部分要特判(若在第0個直接加第1個，若在第n-1個直接加第n-2個)
如此時間複雜度$O(n)$
### 解題流程
讀入測資$→$遍歷$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int arr[100],n;
```
arr即題目說的h
```cpp=7
int ans=0;
```
儲存答案
#### 輸入
```cpp=5
cin>>n;
for(int i=0;i<n;i++)cin>>arr[i];
```
#### 遍歷、處理
```cpp=8
for(int i=0;i<n;i++){
if(arr[i]==0){
if(i==0)ans+=arr[1];
else if(i==n-1)ans+=arr[n-2];
else ans+=min(arr[i-1],arr[i+1]);
}
}
```
因為題目保證不會有相鄰的0，所以不用擔心取min時取到0而影響答案
#### 輸出
```cpp=17
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int arr[100],n;
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>arr[i];
int ans=0;
for(int i=0;i<n;i++){
if(arr[i]==0){
if(i==0)ans+=arr[1];
else if(i==n-1)ans+=arr[n-2];
else ans+=min(arr[i-1],arr[i+1]);
}
}
cout<<ans;
}
```
## 第二題 動線安排
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=g596
### 解套
N/A
題目說的挺清楚的
### 題目分析
~~又是實作量爆炸的一題呢～~~
---
大概看過題目後會發現我們基本上需要四種不同的功能：
加木樁、拆木樁、拆線(放木樁前)、數線與木樁面積
其中「加木樁」時還需要找某個方向有沒有木樁，也是一個重要功能
我的作法是把每個功能寫成一個函數
然後也需要紀錄當前狀況的陣列，我開的陣列叫arr，意義如下：
$$arr數值對應
\begin{cases}
-1& \text{木樁}\\
0& \text{沒有東西}\\
other& \text{線段數量}\\
\end{cases}
$$
各函數說明如下
(喔對在座標方面我是假設$arr[x][y]$，所以x是上下、y是左右，可能會跟有些人的習慣不太一樣)
(看不習慣可以改成$arr[r][c]$之類的)
---
**1.找某方向有沒有木樁$(finddirec)$**
==(方向定義：上0下1左2右3)==
參數：x,y,d(方向)
功能：由給定座標往d方向一直走，若遇到木樁就回傳true，不然最後回傳false
**2.加木樁$(add)$**
把陣列的值設為-1寫在main函式裡，此函數目的在處理新增的線
參數：x,y,d
功能：根據方向不斷往某方向加線直到遇到木樁為止
**3.拆木樁$(rmv)$**
把陣列的值設為寫在main函式裡，此函數目的在處理刪除的線
參數：x,y,d
功能：根據方向不斷往某方向拆線直到遇到木樁為止
**4.拆線$(rmv2)$**
參數：x,y,d
功能：根據方向不斷往某方向拆線直到遇到木樁或空地為止
**5.算面積$(cnt)$**
參數：無
功能：算總共有多少個是線/木樁
---
函數都寫好後，接下來就是如何使用～
大致上有三種情況：
**1.要加木樁，而且該位置沒有線**
把陣列值設為-1，並向四個方向加線(add)
**2.要加木樁，而且該位置有線**
向四個方向拆線(rmv2)，把陣列值設為-1，並向四個方向加線(add)
**3.要拆木樁**
把陣列值設為0，並向四個方向拆(rmv)
然後在每次操作後用cnt更新最大值
最後輸出最大值與當時的cnt
如此時間複雜度$O(hmn)$
### 解題流程
輸入$→$~~非常複雜地~~處理$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int m,n,h,r,c,t,arr[100][100]={},mx=0;
```
arr存當前狀態，mx存最大面積，其他與題述同
#### 函式宣告
**1.finddirec**
```cpp=4
bool finddirec(int x,int y,int d){//up 0 down 1 left 2 right 3
if(d==0){
for(int i=x-1;i>=0;i--)if(arr[i][y]==-1)return 1;
return 0;
}
else if(d==1){
for(int i=x+1;i<m;i++)if(arr[i][y]==-1)return 1;
return 0;
}
else if(d==2){
for(int i=y-1;i>=0;i--)if(arr[x][i]==-1)return 1;
return 0;
}
else{
for(int i=y+1;i<n;i++)if(arr[x][i]==-1)return 1;
return 0;
}
}
```
往特定方向前進直到遇到木樁/邊界為止
**2.rmv**
```cpp=22
void rmv(int x,int y,int d){//up 0 down 1 left 2 right 3
if(d==0){
for(int i=x-1;i>=0;i--){
if(arr[i][y]==-1)return;
else if(arr[i][y]>0)arr[i][y]--;
}
}
else if(d==1){
for(int i=x+1;i<m;i++){
if(arr[i][y]==-1)return;
else if(arr[i][y]>0)arr[i][y]--;
}
}
else if(d==2){
for(int i=y-1;i>=0;i--){
if(arr[x][i]==-1)return;
else if(arr[x][i]>0)arr[x][i]--;
}
}
else{
for(int i=y+1;i<n;i++){
if(arr[x][i]==-1)return;
else if(arr[x][i]>0)arr[x][i]--;
}
}
}
```
往特定方向前進，在遇到木樁前不斷拆繩子
**3.rmv2**
```cpp=48
void rmv2(int x,int y,int d){//up 0 down 1 left 2 right 3
if(d==0){
for(int i=x-1;i>=0;i--){
if(arr[i][y]==0||arr[i][y]==-1)return;
else if(arr[i][y]>0)arr[i][y]--;
}
}
else if(d==1){
for(int i=x+1;i<m;i++){
if(arr[i][y]==-1||arr[i][y]==0)return;
else if(arr[i][y]>0)arr[i][y]--;
}
}
else if(d==2){
for(int i=y-1;i>=0;i--){
if(arr[x][i]==-1||arr[x][i]==0)return;
else if(arr[x][i]>0)arr[x][i]--;
}
}
else{
for(int i=y+1;i<n;i++){
if(arr[x][i]==-1||arr[x][i]==0)return;
else if(arr[x][i]>0)arr[x][i]--;
}
}
}
```
往特定方向前進，在遇到木樁或空格前不斷拆繩子
**4.add**
```cpp=74
void add(int x,int y,int d){//up 0 down 1 left 2 right 3
if(d==0){
for(int i=x-1;i>=0;i--){
if(arr[i][y]==-1)return;
else arr[i][y]++;
}
}
else if(d==1){
for(int i=x+1;i<m;i++){
if(arr[i][y]==-1)return;
else arr[i][y]++;
}
}
else if(d==2){
for(int i=y-1;i>=0;i--){
if(arr[x][i]==-1)return;
else arr[x][i]++;
}
}
else{
for(int i=y+1;i<n;i++){
if(arr[x][i]==-1)return;
else arr[x][i]++;
}
}
}
```
往特定方向前進，在遇到木樁前不斷加繩子
**5.cnt**
```cpp=100
int cnt(){
int ans=0;
for(int i=0;i<m;i++)for(int j=0;j<n;j++){
if(arr[i][j]!=0)ans++;
}
return ans;
}
```
遍歷整個陣列，看有幾個木樁/繩子
#### 輸入
```cpp=108
cin>>m>>n>>h;
```
#### 循環處理
**1.輸入**
```cpp=110
cin>>r>>c>>t;
```
**2.處理**
```cpp=111
if(t==0){
if(arr[r][c]!=0){
if(finddirec(r,c,0))rmv2(r,c,0);
if(finddirec(r,c,1))rmv2(r,c,1);
if(finddirec(r,c,2))rmv2(r,c,2);
if(finddirec(r,c,3))rmv2(r,c,3);
}
arr[r][c]=-1;
if(finddirec(r,c,0))add(r,c,0);
if(finddirec(r,c,1))add(r,c,1);
if(finddirec(r,c,2))add(r,c,2);
if(finddirec(r,c,3))add(r,c,3);
}
else{
arr[r][c]=0;
if(finddirec(r,c,0))rmv(r,c,0);
if(finddirec(r,c,1))rmv(r,c,1);
if(finddirec(r,c,2))rmv(r,c,2);
if(finddirec(r,c,3))rmv(r,c,3);
}
mx=max(mx,cnt());
```
前面是加木樁，後面是拆木樁
因為加木樁的兩種只差在要不要先拆繩子，所以只有這部分特別處理，其他部分一起處理
最後更新最大值
#### 輸出
```cpp=133
cout<<mx<<"\n"<<cnt();
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int m,n,h,r,c,t,arr[100][100]={},mx=0;
bool finddirec(int x,int y,int d){//up 0 down 1 left 2 right 3
if(d==0){
for(int i=x-1;i>=0;i--)if(arr[i][y]==-1)return 1;
return 0;
}
else if(d==1){
for(int i=x+1;i<m;i++)if(arr[i][y]==-1)return 1;
return 0;
}
else if(d==2){
for(int i=y-1;i>=0;i--)if(arr[x][i]==-1)return 1;
return 0;
}
else{
for(int i=y+1;i<n;i++)if(arr[x][i]==-1)return 1;
return 0;
}
}
void rmv(int x,int y,int d){//up 0 down 1 left 2 right 3
if(d==0){
for(int i=x-1;i>=0;i--){
if(arr[i][y]==-1)return;
else if(arr[i][y]>0)arr[i][y]--;
}
}
else if(d==1){
for(int i=x+1;i<m;i++){
if(arr[i][y]==-1)return;
else if(arr[i][y]>0)arr[i][y]--;
}
}
else if(d==2){
for(int i=y-1;i>=0;i--){
if(arr[x][i]==-1)return;
else if(arr[x][i]>0)arr[x][i]--;
}
}
else{
for(int i=y+1;i<n;i++){
if(arr[x][i]==-1)return;
else if(arr[x][i]>0)arr[x][i]--;
}
}
}
void rmv2(int x,int y,int d){//up 0 down 1 left 2 right 3
if(d==0){
for(int i=x-1;i>=0;i--){
if(arr[i][y]==0||arr[i][y]==-1)return;
else if(arr[i][y]>0)arr[i][y]--;
}
}
else if(d==1){
for(int i=x+1;i<m;i++){
if(arr[i][y]==-1||arr[i][y]==0)return;
else if(arr[i][y]>0)arr[i][y]--;
}
}
else if(d==2){
for(int i=y-1;i>=0;i--){
if(arr[x][i]==-1||arr[x][i]==0)return;
else if(arr[x][i]>0)arr[x][i]--;
}
}
else{
for(int i=y+1;i<n;i++){
if(arr[x][i]==-1||arr[x][i]==0)return;
else if(arr[x][i]>0)arr[x][i]--;
}
}
}
void add(int x,int y,int d){//up 0 down 1 left 2 right 3
if(d==0){
for(int i=x-1;i>=0;i--){
if(arr[i][y]==-1)return;
else arr[i][y]++;
}
}
else if(d==1){
for(int i=x+1;i<m;i++){
if(arr[i][y]==-1)return;
else arr[i][y]++;
}
}
else if(d==2){
for(int i=y-1;i>=0;i--){
if(arr[x][i]==-1)return;
else arr[x][i]++;
}
}
else{
for(int i=y+1;i<n;i++){
if(arr[x][i]==-1)return;
else arr[x][i]++;
}
}
}
int cnt(){
int ans=0;
for(int i=0;i<m;i++)for(int j=0;j<n;j++){
if(arr[i][j]!=0)ans++;
}
return ans;
}
int main(){
cin>>m>>n>>h;
while(h--){
cin>>r>>c>>t;
if(t==0){
if(arr[r][c]!=0){
if(finddirec(r,c,0))rmv2(r,c,0);
if(finddirec(r,c,1))rmv2(r,c,1);
if(finddirec(r,c,2))rmv2(r,c,2);
if(finddirec(r,c,3))rmv2(r,c,3);
}
arr[r][c]=-1;
if(finddirec(r,c,0))add(r,c,0);
if(finddirec(r,c,1))add(r,c,1);
if(finddirec(r,c,2))add(r,c,2);
if(finddirec(r,c,3))add(r,c,3);
}
else{
arr[r][c]=0;
if(finddirec(r,c,0))rmv(r,c,0);
if(finddirec(r,c,1))rmv(r,c,1);
if(finddirec(r,c,2))rmv(r,c,2);
if(finddirec(r,c,3))rmv(r,c,3);
}
mx=max(mx,cnt());
}
cout<<mx<<"\n"<<cnt();
}
```
~~真的好長~~
## 第三題 生產線
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=g597
### 解套
有n個機器的單位資料產出時間$t[0],t[1],...,t[n-1]$以及m項工作，每項工作要求一區間的機器各產出$w[i]$單位資料，求妥善安排機器後總共花費的最少時間
(好像有寫跟沒寫一樣)
### 題目分析
很直觀地(大概)，處理速度越快的機器應該要負責越多的工作
而每台機器的處理速度(單位資料處理時間)題目已經給了（$t[i]$）
所以接下來就剩下找出每個位置需要處理多少資料，就能把單位處理時間由小到大排，每位置處理量由大到小排，進而得到答案
於是目標就變成找方法找出每個位置需要處理多少資料
如果直接開一個陣列並每次一個一個加的話總複雜度會是$O(mn)$
代出來會是$4×10^{10}$，明顯會TLE
那要怎麼增進效率呢？
這時就要用到 **BIT(樹狀數組，學名Fenwick Tree)** 這種資料結構
詳細介紹在[這裡](https://oi-wiki.org/ds/fenwick/)
簡單來說他會有三個函式，init負責初始化， upd可以在$O(logn)$時間單點加值，sum可以在$O(logn)$時間求前綴和
不過在本題中要透過以下方式把它變成區間加值，求單點值：
存數值改成存差分，在區間$[a,b]$加上c時用upd(a,c),upd(b+1,-c)來實現，這樣sum(a)就會是a的值
然後總時間最大可以到$100×100×200000×200000=4×10^{14}$，所以最後答案要開long long
這樣實現總複雜度就會降到$O(mlogn+mlogm+nlogn)$
(當然也能用線段樹，不過實作複雜度較高)
### 解題流程
輸入、用BIT存各位置處理量$→$排序$→$貪心地算答案$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,m,a,b,w,t[200000];
long long ans=0;
```
#### 排序函式
```cpp=5
bool cmp(int a,int b){
return a>b;
}
```
讓數字從大到小排
#### BIT
```cpp=8
struct BIT{
int sz;
vector<int>dat;
void init(int n){
sz=n;
dat.assign(sz+2,0);
return;
}
void upd(int id,int x){
for(int i=id;i<=sz;i+=i&-i)dat[i]+=x;
return;
}
int sum(int id){
int ans=0;
for(int i=id;i>0;i-=i&-i)ans+=dat[i];
return ans;
}
}bit;
```
BIT的實作 ~~(無法理解就背起來反正只有18行)~~
如果是一般的BIT初始化只要sz+1就好，但因為變體版需要所以設sz+2
#### 輸入、放進BIT
```cpp=27
cin>>n>>m;
bit.init(n);
while(m--){
cin>>a>>b>>w;
bit.upd(a,w);
bit.upd(b+1,-w);
}
```
要記得初始化BIT(第28行)
因為是變體的BIT所以在a的地方加w，在b+1的地方-w
#### 獲取工作量、排序
```cpp=34
vector<int>v;
for(int i=1;i<=n;i++)v.push_back(bit.sum(i));
sort(v.begin(),v.end(),cmp);
```
把BIT的資料放到vector裡，並由大到小排序
#### 輸入、排序
```cpp=37
for(int i=0;i<n;i++)cin>>t[i];
sort(t,t+n);
```
輸入t後由小到大排
#### 計算、輸出
```cpp=39
for(int i=0;i<n;i++)ans+=t[i]*v[i];
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,w,t[200000];
long long ans=0;
bool cmp(int a,int b){
return a>b;
}
struct BIT{
int sz;
vector<int>dat;
void init(int n){
sz=n;
dat.assign(sz+2,0);
return;
}
void upd(int id,int x){
for(int i=id;i<=sz;i+=i&-i)dat[i]+=x;
return;
}
int sum(int id){
int ans=0;
for(int i=id;i>0;i-=i&-i)ans+=dat[i];
return ans;
}
}bit;
int main(){
cin>>n>>m;
bit.init(n);
while(m--){
cin>>a>>b>>w;
bit.upd(a,w);
bit.upd(b+1,-w);
}
vector<int>v;
for(int i=1;i<=n;i++)v.push_back(bit.sum(i));
sort(v.begin(),v.end(),cmp);
for(int i=0;i<n;i++)cin>>t[i];
sort(t,t+n);
for(int i=0;i<n;i++)ans+=t[i]*v[i];
cout<<ans;
}
```
## 第四題 真假子圖
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=g598
### 解套
給定二分圖的一部分，與一些可能連結集合，求那些連結集合讓二分圖變成不是二分圖
### 題目分析
這題如果要用APCS範圍內的技巧解需要通靈出二分搜解法，可以參考[這裡](https://hackmd.io/@peienwu/APCS1107#P4-%E7%9C%9F%E5%81%87%E5%AD%90%E5%9C%96)(我是看了這個題解才會寫的，歡迎大家改去那邊看，可能會比較清楚)
這題的重點是要怎麼找出哪些調查員的資料與組長的資料有矛盾
因為用組長現有資料建構出的圖必定是二分圖，因此我們要做的就是看哪些調查員把應位在二分圖中不同群組的人連起來，他們就是答案
至於要怎麼知道哪些人位在哪個群組呢？這時就要用到一個叫做**並查集**的資料結構
(詳細說明可以看[這裡](https://oi-wiki.org/ds/dsu/))
一開始先按照組長手中的資料建立二分圖並將點著色(用奇數與偶數代表兩個群組)
接著處理每個調查員的資料，若其欲連結的兩個點的顏色屬於同個群組代表他矛盾，否則代表他目前是對的，於是把他提供的資訊納入考量，即加入並查集，每個調查員都處理完後就能得到答案
這樣最後複雜度是$O(n+pk)$(如果把並查集視為$O(1)$的話)
### 解題流程
輸入$→$dfs遍歷$→$並查集處理$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,m,a,b,p,k,color[20000+10]={};
vector<int>v[20000+10];
```
v存圖，color存顏色，a、b只是輸入用，其他跟題述相同
#### dfs函式
```cpp=5
void dfs(int id,int c1,int c2,bool c){
if(c)color[id]=c1;
else color[id]=c2;
for(int i:v[id])if(color[i]==0)dfs(i,c1,c2,!c);
return;
}
```
把相連的著不同顏色以滿足二分圖條件(配合後面)
#### 並查集
```cpp=11
struct DSU{
int p[20000+10],rk[20000+10];
void init(int n){
for(int i=1;i<=n;i++){
p[i]=i;
rk[i]=0;
}
return;
}
int boss(int x){
return x==p[x]?x:p[x]=boss(p[x]);
}
void join(int x,int y){
x=boss(x);
y=boss(y);
if(x==y)return;
if(rk[x]<rk[y])swap(x,y);
p[y]=x;
if(rk[x]==rk[y])rk[x]++;
return;
}
}djs;
```
其中boss函式負責找對應集合的代表節點，即常見的find，join函式則負責合併，對應常見的find
#### other函式
```cpp=33
int other(int x){
return x%2==0?x-1:x+1;
}
```
方便找到對應的顏色(後面會用到)
#### 輸入、存圖
```cpp=37
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
```
```cpp=48
cin>>p>>k;
```
#### 遍歷、著色
```cpp=43
int c=1;
for(int i=0;i<n;i++){
if(color[i]==0)dfs(i,c,c+1,1);
c+=2;
}
```
#### 依序處理
```cpp=49
vector<int>ans;
for(int i=1;i<=p;i++){
djs.init(c);
bool cmp=0;
for(int j=0;j<k;j++){
cin>>a>>b;
if(cmp)continue;
if(djs.boss(color[a])==djs.boss(color[b])){
cmp=1;
ans.push_back(i);
}
else{
djs.join(color[a],other(color[b]));
djs.join(color[b],other(color[a]));
}
}
}
```
依序處理所有調查員，並開變數cmp紀錄是否矛盾，若已矛盾輸入後就不用做後續處理(第55行)
判斷是否矛盾的方式是看兩個人的顏色是不是同一個集合(第56-59行)
如果不是分別跟對方的相反顏色連接(第60-63行)
#### 輸出
```cpp=66
for(int i:ans)cout<<i<<"\n";
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,p,k,color[20000+10]={};
vector<int>v[20000+10];
void dfs(int id,int c1,int c2,bool c){
if(c)color[id]=c1;
else color[id]=c2;
for(int i:v[id])if(color[i]==0)dfs(i,c1,c2,!c);
return;
}
struct DSU{
int p[20000+10],rk[20000+10];
void init(int n){
for(int i=1;i<=n;i++){
p[i]=i;
rk[i]=0;
}
return;
}
int boss(int x){
return x==p[x]?x:p[x]=boss(p[x]);
}
void join(int x,int y){
x=boss(x);
y=boss(y);
if(x==y)return;
if(rk[x]<rk[y])swap(x,y);
p[y]=x;
if(rk[x]==rk[y])rk[x]++;
return;
}
}djs;
int other(int x){
return x%2==0?x-1:x+1;
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
int c=1;
for(int i=0;i<n;i++){
if(color[i]==0)dfs(i,c,c+1,1);
c+=2;
}
cin>>p>>k;
vector<int>ans;
for(int i=1;i<=p;i++){
djs.init(c);
bool cmp=0;
for(int j=0;j<k;j++){
cin>>a>>b;
if(cmp)continue;
if(djs.boss(color[a])==djs.boss(color[b])){
cmp=1;
ans.push_back(i);
}
else{
djs.join(color[a],other(color[b]));
djs.join(color[b],other(color[a]));
}
}
}
for(int i:ans)cout<<i<<"\n";
}
```
Sign in with Wallet
Connect another wallet