# APCS 2020/1 題解
## ==猜拳==
### 題目
[猜拳](https://zerojudge.tw/ShowProblem?problemid=h026)
### 核心
條件判斷、模擬
### 思路
我覺得是歷屆中較麻煩的第一題。

#include<bits/stdc++.h>
using namespace std;
int F,n;
bool determine(int bro,int sis,int i)
{
    if(bro==sis) return false;
    if((bro==0&&sis==2)||(bro==2&&sis==5)||(bro==5&&sis==0))
    {
        printf(": Won at round %d",i+1);
        return true;
    }
    else
    {
        printf(": Lost at round %d",i+1);
        return true;
    }
    return false;
}
int main()
{
    scanf("%d%d",&F,&n);
    int i,sister[n];
    bool finish=false;
    for(i=0;i<n;i++) scanf("%d",sister+i);
    for(i=0;i<n;i++)
    {
        printf("%d ",F);
        if(i<1)
        {
            finish=determine(F,sister[i],i);
            F=sister[i];
        }
        else
        {
            finish=determine(F,sister[i],i);
            if(sister[i]==sister[i-1])
            {
                if(sister[i]==0) F=5;
                else if(sister[i]==2) F=0;
                else F=2;
            }
            else F=sister[i];
        }
        if(finish) break;
    }
    if(i==n) printf(": Drew at round %d",n);
}

## ==矩陣總和==
### 題目
[矩陣總和](https://zerojudge.tw/ShowProblem?problemid=h027)
### 核心
二維陣列
### 思路
土法煉鋼。

#include<bits/stdc++.h>
using namespace std;
#define N1 15
#define N2 105
int main()
{
    int s,t,m,n,r,i,j,Asum=0;
    int A[N1][N2],B[N1][N2];
    scanf("%d%d%d%d%d",&s,&t,&n,&m,&r);
    for(i=0;i<s;i++) for(j=0;j<t;j++) scanf("%d",&A[i][j]),Asum+=A[i][j];
    for(i=0;i<n;i++) for(j=0;j<m;j++) scanf("%d",&B[i][j]);
    int ans=0,mind=INT_MAX;
    for(i=0;i<n-s+1;i++)
    {
        for(j=0;j<m-t+1;j++)
        {
            int num=0,sum=0;
            for(int k=0;k<s;k++)
            {
                for(int q=0;q<t;q++)
                {
                    if(B[k+i][q+j]!=A[k][q]) num++;
                    sum+=B[k+i][q+j];
                }
            }
            if(num<=r) ans++,mind=min(mind,abs(Asum-sum));
        }
    }
    if(ans==0) printf("0\n-1\n");
    else printf("%d\n%d",ans,mind);
}

## ==砍樹==
### 題目
[砍樹](https://zerojudge.tw/ShowProblem?problemid=h028)
### 核心
鏈結串列、堆疊
### 思路(鏈結串列)
用鏈結串列模擬，首先檢查一遍可砍除的樹，將它們放入queue，後一一從queue拿出時，再檢查相鄰的樹可不可砍除。
注意要更新鏈結的部分。

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define oo 1000000001
struct
{
    int c,h;
    int prev,next;
    int alive;
}tree[N];
void removable(int i)
{
    if (!tree[i].alive) return;
    int s=tree[i].prev, t=tree[i].next;
    if ((tree[i].c-tree[i].h)>=tree[s].c || (tree[i].c+tree[i].h)<=tree[t].c)
    {
        tree[i].alive=0;
        Q.push(i); // insert into queue
        tree[s].next=t; //remove from linked list
        tree[t].prev=s;
    }
    return;
}
queue<int> Q;
int main()
{
    int n,l,i;
    int total=0, high=0;
    scanf("%d %d",&n,&l);
    for (i=1; i<=n; i++) scanf("%d", &tree[i].c);
    for (i=1; i<=n; i++) scanf("%d", &tree[i].h);
    for (i=1; i<=n; i++)
    {
        tree[i].pre=i-1;
        tree[i].next=i+1;
        tree[i].alive=1;
    }
    // two boundaries
    tree[0].c=0, tree[0].h=oo, tree[0].alive=0;
    tree[n+1].c=l, tree[n+1].h=oo, tree[n+1].alive=0;
    //initial check
    for (i=1; i<=n; i++) removable(i);
    while (!Q.empty())
    {
        int v=Q.front();
        Q.pop();
        total++;
        high=max(high, tree[v].h);
        // check its previous and next
        removable(tree[v].prev);
        removable(tree[v].next);
    }
    printf("%d\n%d\n", total, high);
}

### 思路(stack)
堆疊寫起來就比較簡潔。
從頭掃到尾，每次砍除一棵樹只需檢查堆疊中前面未能砍除的樹是否可砍除。

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define oo INT_MAX
int n,L;
int high[N],trees[N];
stack<int> S;
int main()
{
    scanf("%d%d",&n,&L);
    trees[0]=0,trees[n+1]=L;
    for(int i=1;i<=n;i++) scanf("%d",trees+i);
    high[0]=oo,high[n+1]=oo;
    for(int i=1;i<=n;i++) scanf("%d",high+i);
    S.push(0);
    int total=0,maxHigh=0;
    for(int i=1;i<=n;i++)
    {
        if(trees[i]-high[i]>=trees[S.top()]||trees[i]+high[i]<=trees[i+1])
        {
            total++;
            maxHigh=max(maxHigh,high[i]);
            while(trees[S.top()]+high[S.top()]<=trees[i+1])
            {
                total++;
                maxHigh=max(maxHigh, high[S.top()]);
                S.pop();
            }
        }
        else S.push(i);
    }
    printf("%d\n%d\n",total,maxHigh);
}

## ==自動分裝==
### 題目
[貨物分配](https://zerojudge.tw/ShowProblem?problemid=h029)
### 核心
bfs、tree
### 思路
蠻簡單的。

#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define M 105
vector<int> child[N];
int number;
int box[N]={0};
void bfs(int v)
{
    for(int e:child[v])
    {
        box[v]+=bfs(e);
    }
    return;
}
void findb(int v,int w)
{
    if(child[v].size()==0) return;
    int num1=child[v][0],num2=child[v][1];
    if(box[num1]<=box[num2])
    {
        box[num1]+=w;
        number=num1;
        findb(num1,w);
    }
    else
    {
        box[num2]+=w;
        number=num2;
        findb(num2,w);
    }
    return;
}
int main()
{
    int n,m,p,s,t;
    int weight[M];
    scanf("%d%d",&n,&m);
    for(int i=n; i<2*n; i++) scanf("%d",box+i);
    for(int i=0; i<m; i++) scanf("%d",weight+i);
    for(int i=0; i<n-1; i++)
    {
        scanf("%d%d%d",&p,&s,&t);
        child[p].push_back(s),child[p].push_back(t);
    }
    bfs(1);
    for(int i=0; i<m; i++)
    {
        findb(1,weight[i]);
        printf("%d ",number);
    }
}