# APCS 2021/09 題解
## ==七言對聯==
### <font color="0E81A6">題目</font>
[七言對聯](https://zerojudge.tw/ShowProblem?problemid=g275)
### <font color="0E81A6">核心</font>
條件判斷
### <font color="0E81A6">思路</font>

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    int first[7],second[7];
    while(n--)
    {
        bool mistake=false;
        for(int i=0;i<7;i++) scanf("%d",first+i);
        for(int i=0;i<7;i++) scanf("%d",second+i);
        if(first[1]==first[3]||first[1]!=first[5]||second[1]==second[3]||second[1]!=second[5])
        {
            printf("A"),mistake=true;
        }
        if(first[6]==0||second[6]==1) printf("B"),mistake=true;
        if(first[1]==second[1]||first[3]==second[3]||first[5]==second[5]) printf("C"),mistake=true;
        if(!mistake) printf("None");
        printf("\n");
    }
}

## ==魔王迷宮==
### <font color="0E81A6">題目</font>
[魔王迷宮](https://zerojudge.tw/ShowProblem?problemid=g276)
### <font color="0E81A6">核心</font>
模擬
### <font color="0E81A6">思路</font>
注意是同時移動、同時放炸彈。

#include<bits/stdc++.h>
using namespace std;
int place[105][105]={0};
struct boss
{
    int r,c,s,t;
};
int main()
{
    int n,m,k;
    vector<boss> kings;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<k;i++)
    {
        int r,c,s,t;
        scanf("%d%d%d%d",&r,&c,&s,&t);
        kings.push_back({r,c,s,t});
    }
    int ans=0;
    set<pair<int,int>> S;
    while(!kings.empty())
    {
        int x,y;
        vector<int> to_remove;
        for(int i=0;i<kings.size();i++)
        {
            x=kings[i].r,y=kings[i].c;
            if(place[x][y]==0) ans++;
            place[x][y]+=1;
        }
        for(int i=0;i<kings.size();i++)
        {
            x=kings[i].r+kings[i].s,y=kings[i].c+kings[i].t;
            if(x<0||y<0||x>=n||y>=m||place[x][y]>=1) to_remove.push_back(i);
            else kings[i].r=x,kings[i].c=y;
            if(x>=0&&y>=0&&x<n&&y<m&&place[x][y]>=1) S.insert({x,y});
        }
        for (int i=to_remove.size()-1;i>=0;i--) kings.erase(kings.begin()+to_remove[i]);
        while(!S.empty())
        {
            pair<int,int> p=*S.begin();
            S.erase(p);
            place[p.first][p.second]=0;
            ans--;
        }
    }
    printf("%d\n",ans);
}

## ==幸運數字==
### <font color="0E81A6">題目</font>
[幸運數字](https://zerojudge.tw/ShowProblem?problemid=g277)
### <font color="0E81A6">核心</font>
分治、線段樹
### <font color="0E81A6">90%解法(killed)思路</font>
只用分治的話會超時，但很簡單。

#include<bits/stdc++.h>
using namespace std;
#define N 300005
#define pii pair<int,int> //ans sum
#define int long long
int n;
int number[N];
pii findn(int l,int r)
{
    if(l+1==r) return {number[l],number[l]};
    int lsum=0,rsum=0,ans;
    int index=min_element(number+l,number+r)-number;
    pii left,right;
    if (index>l)
    {
        left=findn(l,index);
        lsum=left.second;
    }
    if (index<r-1)
    {
        right=findn(index+1,r);
        rsum=right.second;
    }
    if(lsum>rsum) ans=left.first;
    else ans=right.first;
    return {ans,lsum+rsum+number[index]};
}
signed main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",number+i);
    pii ans=findn(0,n);
    printf("%d\n",ans.first);

}

### <font color="0E81A6">AC解法思路</font>
需要使用線段樹來快速查詢區間最小值。
min_element函數複雜度是O(n)。
線段樹構樹複雜度也是O(n)，但查詢和修改是O(logn)，因此多次查詢的話，用線段樹會好很多。

#include<bits/stdc++.h>
using namespace std;
#define N 300005
#define pii pair<int,int>
#define int long long
int n,number[N],psum[N]={0};
pii tree[4*N];
void build(int s,int t,int pos)
{
    if(s==t)
    {
        tree[pos]={number[s],s};
        return;
    }
    int m=(s+t)>>1;
    build(s,m,2*pos+1),build(m+1,t,2*pos+2);
    if(tree[2*pos+1].first<tree[2*pos+2].first) tree[pos]=tree[2*pos+1];
    else tree[pos]=tree[2*pos+2];
    return;
}
pii query(int l,int r,int s,int t,int pos)
{
    if (r<s||t<l) return {LLONG_MAX, -1};
    if(l<=s&&t<=r) return tree[pos];
    int m=(s+t)>>1;
    auto left=query(l,r,s,m,2*pos+1),right=query(l,r,m+1,t,2*pos+2);
    if(left.first<right.first) return left;
    else return right;

}
signed main()
{
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld",number+i);
        psum[i]=number[i];
        if(i!=0) psum[i]+=psum[i-1];
    }
    build(0,n-1,0);
    int l=0,r=n-1;
    while(l<r)
    {
        int m=query(l,r,0,n-1,0).second;
        if(m==l) l=m+1;
        else if(m==r) r=m-1;
        else
        {
            if(psum[m-1]-psum[l]+number[l]>psum[r]-psum[m+1]+number[m+1]) r=m-1;
            else l=m+1;
        }
    }
    printf("%lld\n",number[l]);

}

## ==美食博覽會==
### <font color="0E81A6">題目</font>
[美食博覽會](https://zerojudge.tw/ShowProblem?problemid=g278)
### <font color="0E81A6">核心</font>
dp
### <font color="0E81A6">思路</font>
dp[i][j]表i個人從攤位0~j能吃多少個。
len[i]表第i個攤位開始最大不重複子序列。

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int n,k,dp[22][N]={0};
int stall[N],visit[N]={false},len[N];
int ans=0;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",stall+i);
    queue<int> Q;
    for(int i=n-1;i>=0;i--)
    {
        while(!Q.empty()&&visit[stall[i]])
        {
            visit[Q.front()]=false;
            Q.pop();
        }
        Q.push(stall[i]);
        visit[stall[i]]=true;
        len[i]=Q.size();
        dp[1][i+len[i]-1]=max(dp[1][i+len[i]-1], len[i]);
    }
    for(int i=1;i<=k;i++)
    {
        dp[i][i-1]=i;
        for(int j=i;j<n;j++)
        {
            dp[i][j]=max(dp[i][j], dp[i][j-1]);
            dp[i+1][j+len[j]-1] = max(dp[i+1][j+len[j]-1], dp[i][j-1]+len[j]);
        }
    }
    printf("%d\n",dp[k][n-1]);

}