# APCS 2021/11題解
## ==修補圍籬==
### <font color="0E81A6">題目</font>
[修補圍籬](https://zerojudge.tw/ShowProblem?problemid=g595)
### <font color="0E81A6">核心</font>
陣列、條件判斷
### <font color="0E81A6">思路</font>
陣列頭尾建一個超高圍籬。

#include<bits/stdc++.h>
using namespace std;
#define oo 1000
int main()
{
    int n,fence[102];
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",fence+i);
    fence[0]=oo,fence[n+1]=oo;
    int cost=0;
    for(int i=1;i<=n;i++)
    {
        if(fence[i]==0) cost+=min(fence[i-1],fence[i+1]);
    }
    printf("%d\n",cost);
}

## ==動線安排==
### <font color="0E81A6">題目</font>
[動線安排](https://zerojudge.tw/ShowProblem?problemid=g596)
### <font color="0E81A6">核心</font>
搞人、模擬
### <font color="0E81A6">思路</font>
純屬搞人心態。

#include<bits/stdc++.h>
using namespace std;
int m,n,h,r,c,t,arr[100][100]={},mx=0;
bool findNeighbor(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)
{
    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 cutWire(int x,int y,int d)
{
    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()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>m>>n>>h;
    while(h--)
    {
        cin>>r>>c>>t;
        if(t==0)
        {
            if(arr[r][c]!=0)
            {
                for(int i=0;i<4;i++) if(findNeighbor(r,c,i)) cutWire(r,c,i);
            }
            arr[r][c]=-1;
            for(int i=0;i<4;i++) if(findNeighbor(r,c,i)) add(r,c,i);
        }
        else
        {
            arr[r][c]=0;
            for(int i=0;i<4;i++) if(findNeighbor(r,c,i)) rmv(r,c,i);
        }
        mx=max(mx,cnt());
    }
    cout<<mx<<"\n"<<cnt();
}

## ==生產線==
### <font color="0E81A6">題目</font>
[生產線](https://zerojudge.tw/ShowProblem?problemid=g597)
### <font color="0E81A6">核心</font>
BIT、前綴和
### <font color="0E81A6">思路</font>
[BIT教學](https://oi-wiki.org/ds/fenwick/)
學會之後這題就迎刃而解了。

#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n,m,machine[N];
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()
{
    scanf("%d%d",&n,&m);
    bit.init(n);
    int a,b,w;
    while(m--)
    {
        scanf("%d%d%d",&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++) scanf("%d",machine+i);
    sort(machine,machine+n);
    for(int i=0;i<n;i++) ans+=machine[i]*v[i];
    printf("%lld\n",ans);
}

## ==真假子圖==
### <font color="0E81A6">題目</font>
[真假子圖](https://zerojudge.tw/ShowProblem?problemid=g598)
### <font color="0E81A6">核心</font>
並查集、二分圖
### <font color="0E81A6">思路</font>
這題運用到填色和並查集的觀念，屬實漂亮。

#include<bits/stdc++.h>
using namespace std;
#define N 20005
#define int long long
int parent[N],color[N]={0},rk[N];
vector<int> edge[N];
int other(int s){return (s%2)?s+1:s-1;}
void init(int col)
{
    for(int i=1;i<=col;i++) parent[i]=i,rk[i]=0;
}
void dfs(int id,int col)
{
    color[id]=col;
    for(auto i:edge[id])
    {
        if(!color[i]) dfs(i,other(col));
    }
}
int findp(int u)
{
    if(parent[u]==u) return u;
    return parent[u]=findp(parent[u]);
}
void join(int u,int v)
{
    int r1=findp(u),r2=findp(v);
    if(r1==r2) return;
    if(rk[r1]<rk[r2]) swap(r1,r2);
    parent[r2]=r1;
    if(rk[r1]==rk[r2]) rk[r1]++;
    return;
}
signed main()
{
    int n,m,p,k,u,v;
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%lld%lld",&u,&v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    int now=1;
    for(int i=0;i<n;i++)
    {
        if(!color[i]) dfs(i,now),now+=2;
    }
    vector<int> ans;
    scanf("%lld%lld",&p,&k);
    for(int i=1;i<=p;i++)
    {
        bool mistake=false;
        init(now);
        for(int j=0;j<k;j++)
        {
            scanf("%lld%lld",&u,&v);
            if(mistake) continue;
            if(findp(color[u])==findp(color[v])) mistake=true,ans.push_back(i);
            else
            {
                join(color[u],other(color[v]));
                join(color[v],other(color[u]));
            }
        }
    }
    for(int i:ans) printf("%lld\n",i);
}