# APCS 2021.11.07
---
## 1. [修補圍籬](https://zerojudge.tw/ShowProblem?problemid=g595)
----
### 想法：
直接遍歷一次陣列，當遇到 $0$ 時就對左右兩個位置取 $min$
可以把 $h[0]$ 跟 $h[n+1]$ 設成一個很大的數，實做起來比較方便
::: spoiler code :
```cpp=
#include<iostream>
using namespace std;
int h[105],n,ans;
int main(){
cin>>n;
h[0]=h[n+1]=100000; // 將 h[0] 跟 h[n+1] 設為一個很大的數
for(int i=1;i<=n;i++)
cin>>h[i];
for(int i=1;i<=n;i++)
if(h[i]==0)
ans+=min(h[i-1],h[i+1]); // 如果 h[i] 是 0 就對左右取 min(最小值)
cout<<ans<<endl;
return 0;
}
```
:::
---
## 2. [動線安排](https://zerojudge.tw/ShowProblem?problemid=g596)
這題大概是這次 APCS 第二難（或是第一）的題目惹
### 想法：
我們存每根木樁往上、下、左、右是否有連出線，每次操作完就從每根木樁往外走，
同時在圖上標記，最後再看有幾個格子有標記就好，詳情請見 code
:::spoiler code :
```cpp=
#include<iostream>
using namespace std;
bool is[105][105]; // 每個位置是否有木樁
bool ex[105][105][4]; // 每個位置的木樁往上、左、右、下是否有連線
/* 0 -> 上
* 1 -> 左
* 2 -> 右
* 3 -> 下
* 為什麼要醬設呢，之後就知道惹~
* */
int m,n,h;
int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0}; // 4個方向每次移動的座標改變量
bool mk[105][105]; // 有沒有被標記
bool op(int x,int y,int d,int t){
// 從 (x,y) 這個格子往d方向，做各種操作
// 並且這次的操作是 t
// t=0 連上，並回傳是否有遇到木樁
// t=1 拔掉
// t=2 標記
while(x>=0&&x<m&&y>=0&&y<n){
if(is[x][y]){
if(t==1||t==0){
ex[x][y][3-d]=(t^1);
// 我們發現相反方向的代號加起來剛好是3耶！！！
// 於是乎就可以順便修改這個木樁的狀態啦！！！
}
return 1;
}
if(t==2) mk[x][y]=1;
x+=dx[d];
y+=dy[d];
}
return 0;
}
int cnt(){ // 計算當前圖上的答案
for(int i=0;i<m;i++)for(int j=0;j<n;j++) mk[i][j]=0; // 把標記清空
for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(is[i][j]){ // 找出有木樁的格子
for(int d=0;d<4;d++)if(ex[i][j][d]){
is[i][j]=0; // 避免直接回傳
op(i,j,d,2);
is[i][j]=1; // 回復原狀
}
}
int ans=0;
for(int i=0;i<m;i++)for(int j=0;j<n;j++){
if(is[i][j]||mk[i][j]) ans++; // 有木樁或有標記都會算進答案
}
return ans;
}
int main(){
int maxn=0;
cin>>m>>n>>h;
while(h--){
int r,c,t;
cin>>r>>c>>t;
if(t==0){ // 加入木樁
for(int d=0;d<4;d++)// 4個方向
if(op(r,c,d,t)){
ex[r][c][d]=1;
}
is[r][c]=1;
}
else{ // 拔掉木樁
is[r][c]=0;
for(int d=0;d<4;d++)// 4個方向
if(ex[r][c][d]){ // 如果原本有連出線，就要修改他連到的那根木樁的狀態
ex[r][c][d]=0;
op(r,c,d,t);
}
}
maxn=max(maxn,cnt());
}
cout<<maxn<<endl<<cnt()<<endl;
return 0;
}
```
:::
::: spoiler 乾淨的 code :
```cpp=
#include<iostream>
using namespace std;
bool is[105][105];
bool ex[105][105][4];
int m,n,h;
int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
bool mk[105][105];
bool op(int x,int y,int d,int t){
while(x>=0&&x<m&&y>=0&&y<n){
if(is[x][y]){
if(t==1||t==0) ex[x][y][3-d]=(t^1);
return 1;
}
if(t==2) mk[x][y]=1;
x+=dx[d];
y+=dy[d];
}
return 0;
}
int cnt(){
for(int i=0;i<m;i++)for(int j=0;j<n;j++) mk[i][j]=0;
for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(is[i][j]){
for(int d=0;d<4;d++)if(ex[i][j][d]){
is[i][j]=0;
op(i,j,d,2);
is[i][j]=1;
}
}
int ans=0;
for(int i=0;i<m;i++)for(int j=0;j<n;j++){
if(is[i][j]||mk[i][j]) ans++;
}
return ans;
}
int main(){
int maxn=0;
cin>>m>>n>>h;
while(h--){
int r,c,t;
cin>>r>>c>>t;
if(t==0){
for(int d=0;d<4;d++)if(op(r,c,d,t))
ex[r][c][d]=1;
is[r][c]=1;
}
else{
is[r][c]=0;
for(int d=0;d<4;d++)if(ex[r][c][d]){
ex[r][c][d]=0;
op(r,c,d,t);
}
}
maxn=max(maxn,cnt());
}
cout<<maxn<<endl<<cnt()<<endl;
return 0;
}
```
:::
---
## 3. [生產線](https://zerojudge.tw/ShowProblem?problemid=g597)
這題會用到一個小技巧，叫做差分
----
### 什麼是差分？
對於一個正整數序列 $A$ ，我們用另一個陣列 $B$ 來記錄 $A$ 中每一項的差
具體來說 $B[i]=A[i]-A[i-1]$
因此當我們想要在 $A$ 中的 $l$ ~ $r$ 加上某個數 $x$ 時
我們可以直接在 $B[l]$ 加上 $x$ , 並在 $B[r+1]$ 扣除 $x$
這麼一來，我們只要從頭跑一次差分陣列 $B$ 就可以知道每一項是多少了
----
### 想法：
先利用差分處理完每台機器需要處理多少資料後
再將 "要處理比較多資料的機器" 跟 "產出速率較快的位置配對"
就可以得出答案惹 ~
要小心 overflow
::: spoiler code
```cpp=
#include<iostream>
#include<algorithm> // sort
#include<vector> // vector
#define ll long long
using namespace std;
int n,m;
ll dif[200005]; // 差分陣列
int main(){
vector<ll> pos,mac;
// pos 是存每個位置的產出速率
// mac 是存每台機器要處理的資料量
cin>>n>>m;
while(m--){
int l,r,w;
cin>>l>>r>>w;
dif[l]+=w;
dif[r+1]-=w;
}
for(int i=1;i<=n;i++){
int t; cin>>t;
pos.push_back(t);
}
ll now=0; // 用來得出差分陣列所派表的每一項是多少
for(int i=1;i<=n;i++){
now+=dif[i]; // 加上差分陣列（變化量）就可以得到這項的值
mac.push_back(now);
}
// 排序 pos 跟 mac
sort(pos.begin(),pos.end());
sort(mac.begin(),mac.end());
ll ans=0;
for(int i=0;i<n;i++){
ans+=pos[i]*mac[n-i-1]; // 大配小
}
cout<<ans<<endl;
return 0;
}
```
:::
---
## 4. [真假子圖](https://zerojudge.tw/ShowProblem?problemid=g598)
這題好像有蠻多解法的，但我只會 dsu...
### 什麼是 dsu ?
中文是併查集，顧名思義，就是一種支援合併與查詢的資料結構
詳情請自行 google
### 想法：
因為題目保證只有三個人會與組長的資料矛盾，且剩下的人彼此都是不矛盾的
因此我們可以在發現矛盾時，將資料恢復成只有組長的資料的狀態
#### 要怎麼知道有沒有矛盾呢？
我們可以幫每個人建立一個假想敵，
編號為 $i$ 的人的假想敵編號為 $i+n$
當我們要建立一個 ${x,y}$ 之間的合作關係時
如果 $x$ 跟 $y$ 是同組的，或者 $x+n$ 跟 $y+n$ 是同組的
那就產生矛盾了，因為合作關係的雙方必須是不同組的
同樣的，對於這組合作關係
我們把 $x$ 和 $y+n$ 合併成同一組
同樣的 $y$ 和 $x+n$ 合併為同一組
這樣就可以快樂 AC 了～
::: spoiler code :
```cpp=
#include<iostream>
#include<vector>
using namespace std;
const int N=4e4+5; // 因為還有假想敵所以陣列要開兩倍
vector<int> ini; // 組長手中的資料
int n,m;
// dsu 的部分
int boss[N],siz[N];
int find(int x){
if(boss[x]==x) return x;
return boss[x]=find(boss[x]);
}
void merge(int a,int b){
if(siz[a]<siz[b]) swap(a,b);
siz[a]+=siz[b];
boss[b]=a;
}
// 回復成組長的資料的部分
void repair(){
for(int i=0;i<2*n;i++){
siz[i]=1; boss[i]=i;
}
for(int i=0;i<m;i++){
int a=ini[i*2],b=ini[i*2+1];
int fa=find(a),fb=find(b);
int FA=find(a+n),FB=find(b+n);
merge(fa,FB); merge(FA,fb);
}
}
signed main(){
cin>>n>>m;
for(int i=0;i<2*n;i++){ // 初始化
siz[i]=1;
boss[i]=i;
}
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
ini.push_back(a);
ini.push_back(b);
int fa=find(a),fb=find(b);
int FA=find(a+n),FB=find(b+n); // 假想敵
merge(fa,FB); merge(FA,fb);
}
vector<int> ans;
int p,k;
cin>>p>>k;
for(int i=0;i<p;i++){
bool ok=1; // 是否矛盾
for(int j=0;j<k;j++){
int a,b;
cin>>a>>b;
if(!ok) continue; // 如果已經矛盾了就不用往下做了
int fa=find(a),fb=find(b);
int FA=find(a+n),FB=find(b+n); // 假想敵
if(fa==fb||FA==FB){ // 產生矛盾！
ok=0; continue;
}
merge(fa,FB); merge(FA,fb);
}
if(!ok){
ans.push_back(i+1);
repair();
}
}
for(int i:ans) cout<<i<<endl;
}
```
:::
Sign in with Wallet
Connect another wallet