# APCS 2017/10 題解
## ==邏輯運算子==
### [題目](https://zerojudge.tw/ShowProblem?problemid=c461)
### 核心
條件判斷
### 思路

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    bool can=false;
    scanf("%d%d%d",&a,&b,&c);
    a=(a!=0?1:0),b=(b!=0?1:0);
    if((a&&b)==c) can=true,printf("AND\n");
    if((a||b)==c) can=true,printf("OR\n");
    if((a^b)==c) can=true,printf("XOR\n");
    if(!can) printf("IMPOSSIBLE\n");
}

## ==交錯字串==
### [題目](https://zerojudge.tw/ShowProblem?problemid=c462)
### 核心
vector
### 思路
將連續大(小)寫子串列長度存入segment，接著遍歷segment，初始設num=0，當子串列長度>=k時num=1，再找連續的長度k子串列，若找到長度> k的子串列，則更新答案並重計num，若找到長度< k的子串列，則更新答案並設num=0。

#include<bits/stdc++.h>
using namespace std;
int k,ans=0;
string str;
vector<int> segment;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>k>>str;
    int tmp=1;
    for(int i=1;i<str.size();i++)
    {
        if(isupper(str[i])==isupper(str[i-1])) tmp++;
        else
        {
            segment.push_back(tmp);
            tmp=1;
        }
    }segment.push_back(tmp);
    int num=0;
    for(int i=0;i<segment.size();i++)
    {
        if(num>0)
        {
            if(segment[i]==k) num++;
            else if(segment[i]>k)
            {
                ans=max(ans,(num+1)*k);
                num=1;
            }
            else ans=max(ans,num*k),num=0;
        }
        else
        {
            if(segment[i]>=k) num=1;
        }
    }
    ans=max(ans,num*k);
    cout<<ans<<endl;
}

## ==樹狀圖分析==
### [題目](https://zerojudge.tw/ShowProblem?problemid=c463)
### 核心
dfs、tree
### 思路1(bottom-up)
最差複雜度接近O(n^2^)，思路簡單但不建議這樣寫。
從子節點開始向上dfs，每次更新父節點的高度。
最後再取總和。

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n,k;
int parent[N],h[N]={0};
vector<int> child[N];
long long ans=0;
void dfs(int u)
{
    if(parent[u]==-1) return;
    h[parent[u]]=max(h[parent[u]],h[u]+1);
    dfs(parent[u]);
}
int main()
{
    memset(parent,-1,sizeof(parent));
    scanf("%d",&n);
    for(int v=1;v<=n;v++)
    {
        int u;
        scanf("%d",&k);
        while(k--)
        {
            scanf("%d",&u);
            child[v].push_back(u);
            parent[u]=v;
        }
    }
    int root;
    for(int i=1;i<=n;i++)
    {
        if(child[i].size()==0) dfs(i);
        if(parent[i]==-1) root=i;
    }
    for(int i=1;i<=n;i++) ans+=h[i];
    printf("%d\n%lld",root,ans);
}

### 思路2(top-down)
複雜度O(n)。
每個節點存子節點的最深深度far[id]，dep為當前深度，far[id]-dep就是最大高度。

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n,k,u,far[N];
vector<int> child[N];
unordered_set<int> S;
long long ans=0;
void dfs(int id,int dep)
{
    if(child[id].size()==0)
    {
        far[id]=dep;
        return;
    }
    for(int u:child[id])
    {
        dfs(u,dep+1);
        far[id]=max(far[id],far[u]);
    }
    ans+=far[id]-dep;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) S.insert(i);
    for(int v=1;v<=n;v++)
    {
        scanf("%d",&k);
        while(k--)
        {
            scanf("%d",&u);
            child[v].push_back(u);
            S.erase(u);
        }
    }
    dfs(*S.begin(),0);
    printf("%d\n%lld",*S.begin(),ans);
}

## ==物品堆疊==
### [題目](https://zerojudge.tw/ShowProblem?problemid=c471)
### 核心
貪心、加權排序
### 思路
若有A、B兩物品，A在下時取A要消耗 w(B) * f(A) 能量，B在下時取B要消耗 w(A) * f(B) 能量，小的應該在上面，排序的規則出來了。

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n;
struct good
{
    int w,f;
}goods[N];
bool cmp(good &a,good &b)
{
    return a.w*b.f<a.f*b.w;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&goods[i].w);
    for(int i=0;i<n;i++) scanf("%d",&goods[i].f);
    sort(goods,goods+n,cmp);
    long long cnt=goods[0].w,ans=0;
    for(int i=1;i<n;i++)
    {
        ans+=cnt*goods[i].f;
        cnt+=goods[i].w;
    }
    printf("%lld\n",ans);

}