# APCS 2021.09.05
###### tags: `APCS`
> [name=peienwu]
> [name=thanksone]
> [time=Wed, Sep 8, 2021 3:40 PM]

---

## 原文網址：https://peienwu.com/apcs2109/

---

## P1 七言對聯
[題目連結](https://zerojudge.tw/ShowProblem?problemid=g275)

總共有ABC三種規則，就每一種都比對一次就可以了！

**時間複雜度：** 共有 $n$ 組對聯，每一組都 $O(1)$ 檢查，時間 $O(n)$ 。（不過n最大也才50，不論什麼複雜度都可以吧）

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define int long long
#define N 50
#define Orz ios::sync_with_stdio(0),cin.tie(0)
#define INF 2e18
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n;
bool a[N],b[N],f = 1;

signed main(){
    Orz;
    cin>>n;
    while(n--){
        rep(i,1,7)cin>>a[i];
        rep(i,1,7)cin>>b[i];
        f = 1;
        if(a[2]==a[4]||a[2]!=a[6]){
                cout<<"A";f = 0;
        }
        else if(b[2]==b[4]||b[2]!=b[6]){
                cout<<"A";f = 0;
        }

        if(a[7]!=1 || b[7]!=0){
                cout<<"B";f = 0;
        }

        if(a[2]==b[2]||a[4]==b[4]||a[6]==b[6]){
                cout<<"C";f = 0;
        }
        if(f)cout<<"None"<<endl;
        else cout<<endl;
    }

}

## P2 魔王迷宮
[題目連結](https://zerojudge.tw/ShowProblem?problemid=g276)

這一題是去模擬每一個魔王移動的狀況，要特別注意每一輪的國王是同時移動的，沒有先後順序，也就是說一顆炸彈可以炸掉不只一位魔王，如果有多個魔王移動到同一個格子，則他們會一起被炸掉。

**時間複雜度：** 有點難估計，因為很難確定每一個魔王的移動狀況次數，不過由於數字範圍不大，且 $k$ 只有到500，因此直接做複雜度是可行的。

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define int long long
#define N 100
#define Orz ios::sync_with_stdio(0),cin.tie(0)
#define INF 2e18
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n,m,k;
bool maze[N][N],bomb[N][N];

struct node{
    int x,y,s,t;
    bool alive;
}mp[505];

signed main(){
    Orz;
    memset(maze,0,sizeof(maze));
    cin>>n>>m>>k;
    rep(i,0,k-1){
        cin>>mp[i].x>>mp[i].y;
        cin>>mp[i].s>>mp[i].t;
        mp[i].alive = 1;
    }
    
    int now_alive = k;
    while(now_alive){
        memset(bomb,0,sizeof(bomb));
        for(int p=0;p<k;p++){
            if(mp[p].alive == 0)continue;
            int i = mp[p].x,j = mp[p].y;
            maze[i][j] = 1;
        }
        for(int p=0;p<k;p++){
            if(mp[p].alive == 0)continue;
            int i = mp[p].x,j = mp[p].y;
            int nx = i + mp[p].s;
            int ny = j + mp[p].t;
            if(nx >= n || nx < 0 || ny >= m ||ny < 0){
                now_alive--;
                mp[p].alive = 0;
            }
            else if(maze[nx][ny]){
                now_alive--;
                mp[p].alive = 0;
                bomb[nx][ny] = 1;
            }
            else{
                mp[p].x = nx;
                mp[p].y = ny;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(bomb[i][j] == 1)
                    maze[i][j] = 0;
            }
        }
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(maze[i][j])ans++;
        }
    }
    cout<<ans<<endl;
}

## P3 幸運數字
[題目連結](https://zerojudge.tw/ShowProblem?problemid=g277)

以區間最小值作為區分點將數列分成兩半，可以利用線段樹找區間最小值，利用迴圈模擬每一次範圍縮小的情況。

不過這一題比較特別，他的區間範圍一定會越來越小，且區間外的數字也就不需要使用到，因此可以將數列做一次排序，從頭開始找如果遇上區間外的數字則不理他，否則使用它當作區間的分隔點（這一定會是最小值，因為由小到大排序），將區間範圍縮小。

至於挑選左右區間的區間和，則可以透過前綴和 $O(1)$ 算出答案。

**時間複雜度：** 如果是一個遞增或遞減的序列，則每一次區間大小只會縮減1，此時複雜度為 $O(n)$，加上最一開始的排序是 $O(n\log n)$，總共為 $O(n\log n)$。

### 排序作法

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define int long long
#define N 300005
#define Orz ios::sync_with_stdio(0),cin.tie(0)
#define INF 2e18
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n,arr[N],pref[N];
pii sorted[N];

signed main(){
    Orz;
    cin>>n;
    rep(i,1,n){
        cin>>sorted[i-1].x;
        arr[i] = sorted[i-1].x;
        sorted[i-1].y = i;
        pref[i] = pref[i-1]+arr[i];
    }
    sort(sorted,sorted+n);

    int ind = 0,l = 1,r = n;

    while(r>l){
        while(sorted[ind].y > r || sorted[ind].y < l)ind++;
        int left = pref[sorted[ind].y-1]-pref[l-1];
        int right = pref[r]-pref[sorted[ind].y];
        if(left > right){
            r = sorted[ind].y-1;
        }
        else{
            l = sorted[ind].y+1;
        }
    }
    cout<<arr[l]<<endl;
}

### 線段樹作法
如果用線段樹實作，尋找區間最小值，可以在 $O(\log n)$ 的時間內詢問。在最差的情況下，一共會詢問 $n$ 次，因此總時間複雜度一樣是 $O(n\log n)$。實作上也不複雜，建立線段樹以及區間詢問，區間修改和懶標之類的東西。可以比較一下時間：


線段樹的表現稍微好一點，不過其實是相當接近的！

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define int long long
#define N 300005
#define Orz ios::sync_with_stdio(0),cin.tie(0)
#define INF 2e18
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n,arr[N],pref[N];
pii seg[4*N];

//建立線段樹[l,r)
void build(int cur,int l,int r){
    if(r <= l)return;
    if(r - l <= 1){
        seg[cur] = {arr[l],l};
        return;
    }
    int mid = (l+r)/2;
    build(2*cur,l,mid);
    build(2*cur+1,mid,r);
    if(seg[2*cur].x < seg[2*cur+1].x)
        seg[cur] = seg[2*cur];
    else
        seg[cur] = seg[2*cur+1];
}

//詢問區間最小值，回傳pair
pii query(int cur,int l,int r,int ql,int qr){
    if(r <= l || ql >= r || qr <= l)return {INT_MAX,INT_MAX};
    if(ql <= l && qr >= r)return seg[cur];
    int mid = (l+r)/2;
    pii lft = query(2*cur,l,mid,ql,qr);
    pii rgt = query(2*cur+1,mid,r,ql,qr);
    if(lft.x < rgt.x)return lft;
    return rgt;
}

signed main(){
    Orz;
    cin>>n;
    rep(i,1,n){
        cin>>arr[i];
        pref[i] = pref[i-1]+arr[i];
    }
    build(1,1,n+1);
    int l = 1,r = n+1;
    
    while(r - l > 1){
        int ind = query(1,1,n+1,l,r).y;
        int left = pref[ind-1] - pref[l-1];
        int right = pref[r-1] - pref[ind];
        if(left > right)r = ind;
        else l = ind + 1;
    }
    cout<<arr[l]<<"\n";
}

### 歐恩作法
有一種二元樹，我也不知道叫啥，根為全序列最小值，左節點為左邊序列最小值，右節點為右邊序列最小值。
> [name=thanksone]
#### 建法
紀錄每個位置左、右邊離自己最近、比自己小的，爸爸就是兩個之中比較大的那一個。
> [name=thanksone]

**時間複雜度：** 種樹加跑答案總共 $O(n)$

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
array<int, 300004> A, S, L, R;
array<pii, 300004> tree;
void plant(int n){
    for(int i = 1; i <= n; i++){
        if(A[L[i]] > A[R[i]]) tree[L[i]].ss = i;
        else tree[R[i]].ff = i;
    }
}
int solve(int l, int r, int m){
    if(l == r) return A[l];
    if(S[m - 1] - S[l - 1] > S[r] - S[m]) return solve(l, m - 1, tree[m].ff);
    else return solve(m + 1, r, tree[m].ss);
}
signed main(){
    int n;
    cin >> n;
    stack<pii> s;
    pii m = {1e9, 0};
    s.push({0, 0});
    for(int i = 1; i <= n; i++){
        cin >> A[i];
        if(A[i] < m.ff) m = {A[i], i};
        S[i] = A[i] + S[i - 1];
        while(A[i] < s.top().ff){
            R[s.top().ss] = i;
            s.pop();
        }
        L[i] = s.top().ss;
        s.push({A[i], i});
    }
    plant(n);
    cout << solve(1, n, m.ss);
    return 0;
}

> [name=thanksone]

如果把範測的笛卡爾樹具象化，大概長這樣：
> 8
> 3 9 4 5 1 6 2 8


大致步驟就是：
1. 用**單調隊列**建立函數 $L$ 以及 $R$，表示往左往右看第一個小於自己的數
2. 建立笛卡爾樹（$L[i],R[i]$ 挑大的作為父節點）
3. 從根節點開始走訪，左右節點就會分別是左右區間的最小值
4. 利用前綴和計算區間大小，決定要走左還是右子樹
5. 走訪到區間長度為 $1$ 時即答案！

:::info
總共有三個不同的作法，使用到排序、線段樹、笛卡兒樹的作法。其中，他們的間複雜度分別是 $O(n\log n)$、$O(n\log n)$、$O(n)$。

1. 排序作法：AC (0.1s, 9.5MB)
2. 線段樹作法：AC (84ms, 20.9MB)
3. 歐恩作法：AC (82ms, 15.6MB)

在笛卡兒樹的作法中，對每一個數字尋找兩側第一個小於它的數字（這可以用單調隊列完成），之後把每一個數字的父親節點設為找到的兩端數字中較大的那一個。

此作法的概念是，假設序列中第 $i$ 個數字找到兩側數字分別是 $l_i$ 以及 $r_i$，當他如果是區間最小時，區間必須在 $[l_i+1:r_i-1]$ 之中，否則它就不會是最小值了。

至於為何是選擇 $max(A[l_i],A[r_i])$ 當做父節點？則是因為如果選擇較小的那一個，在縮小區間範圍後，無法確定另外一個是否在區間外，如果包含區間內，則 $A[i]$ 便不會是最小值，違反了定義。換言之，選擇了較大的那一個當作父節點，按照定義當走到這個父節點時，它是區間的最小值，將它排除之後，$A[i]$ 就會是下一個區間的最小值！
:::

## P4 美食博覽會
[題目連結](https://zerojudge.tw/ShowProblem?problemid=g278)

### NORMAL 版本

對於序列中k個連續的區間，每一個區間滿足區間內的元素皆不重複，區間範圍可以重疊（不過重疊部分只會算一次），找出這k個連續區間所能覆蓋到的最大長度。

感覺跟背包問題的概念有點像，n個物品可以對應到k個區間，重量則對應到這裡的序列中的數字。這題用DP解。

#### 定義
定義 $dp[i][j]$ 為 $i$ 個試吃員，看了前 $j$ 個攤位，最多可以吃到幾個攤位。

#### 轉移式
維護一個函數 $f[i]$ 表示如果試吃員吃了第 $i$ 個攤位的美食，他所能吃到**最左端的攤位的索引值**。也就是說，試吃員可以吃 $f[i]$ 到 $i$ 攤位的美食。

$$dp[i][j] = max(dp[i][j-1],dp[i-1][f[j]-1]+j-f[j]+1)$$

轉移式代表了要使用第 $i$ 的攤位作為右端點，或是不要使用（直接用前一個），取兩者的最大值。後面一串加減是計算區間大小

#### 邊界

$$dp[i][j] = 0,\text{for all 0≤i≤k,0≤j≤n}$$

從轉移式可以看到他空間可以用滾動DP優化！

:::info
**GREEDY的作法？**
如果每一次都選擇最大的區間，並將這個區間的值都改成0，做7次，得到答案，是正確的做法嗎？

:::spoiler 反例
最大的區間不一定會被完全選到。以下測資：

> 12 2
> 5 4 3 2 1 3 4 5 6 4 3 2

如果是Greedy會選擇 $2 \,1\, 3\, 4\, 5\, 6$ ，然後從兩邊挑一邊。答案是 $9$。
但是用DP做會是 $5\, 4\, 3\, 2\, 1$ 加上 $5\, 6\, 4\, 3\, 2$，答案是 $10$。
> [name=thanksone]

:::

**時間複雜度：** 兩層迴圈總共是 $O(kn)$

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define int long long
#define N 1000005
#define Orz ios::sync_with_stdio(0),cin.tie(0)
#define INF 2e18
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n,k,dp[2][N],lft[N],arr[N];
int mp[N];

signed main(){
    Orz;
    cin>>n>>k;
    memset(dp,0,sizeof(dp));
    memset(lft,0,sizeof(lft));
    memset(mp,0,sizeof(mp));
    rep(i,1,n)cin>>arr[i];
    int maxn = 0;
    for(int i=1;i<=n;i++){
        if(mp[arr[i]]!=0){
            lft[i] = mp[arr[i]]+1;
            mp[arr[i]] = i;
        }
        else{
            lft[i] = 1;
            mp[arr[i]] = i;
        }
        lft[i] = max(maxn,lft[i]);
        maxn = max(maxn,lft[i]);
    }

    
    for(int i=0;i<k;i++){
        for(int j=1;j<=n;j++){
            dp[1][j] = max(dp[1][j-1],dp[0][lft[j]-1]+j-lft[j]+1);
        }
        for(int j=1;j<=n;j++){
            dp[0][j] = dp[1][j];
        }
    }
    cout<<dp[1][n]<<endl;
}

// 1 1 2 1 4 1 7 1 3 8
// 1 1 2 2 4 4 7 7 7 8

### EXTRA 版本


熟悉的題目，大的感人的k。如果依照上面$O(nk)$的做法肯定TLE。
俗話說得好 : "好的DP定義是AC的一半"
因此經過一系列通靈，我們得到了一個非常漂亮的定義
> [name=thanksone]

#### 定義
$dp[i] =$ 必須選第 $i$ 家，$($能吃最多的攤販數量，需要的人數$) (dp[i]$是一個$pair)$
> [name=thanksone]
#### 轉移式
維護一個函數 $L[i]$ ，其實就是樓上的 $f[i]$，但是我比較想要叫他 $L$

$$dp[i] = max_{j<L[i]}(dp[j]) + i - L[i] + 1$$

$max(a, b) = a, if(a.first > b.first\ or\ (a.first == b.first\ and\ a.second > b.second))$
> [name=thanksone]

#### 優化
Aliens優化 : 利用penalty限制人數
每當有一個人加入，便扣除 $p$ 個攤販的業績
當總人數超過 $k$，表示 $p$ 不夠大，仍然有太多人利大於弊
反之，當總人數小於 $k$，表示 $p$ 太大，有太多人弊大於利
看出來了嗎? $p$ 可以二分搜喔!
> [name=thanksone]

**時間複雜度：** 二分搜加每次DP $O(nlogn)$

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
int n, k;
array<int, 100004> A/*num of stands*/, L/*leftest stand can eat to*/, cnt/*count of each num*/;
array<pii, 100004> dp;
pii add(pii p, int v){
    p.ff += v;
    p.ss++;
    return p;
}
pii max(pii a, pii b){
    if(a.ff == b.ff) return a.ss > b.ss? a : b;
    return a.ff > b.ff ? a : b;
}
pii DP(int p){
    //ff = stands visited, ss = people needed
    pii ans = {0, 0};
    int l = 0;
    for(int i = 0; i < n; i++){
        while(l < L[i]) ans = max(ans, dp[l++]);
        dp[i] = add(ans, i - L[i] + 1 + p);
    }
    while(l < n) ans = max(ans, dp[l++]);
    return ans;
}
int BIS(){
    int l = -n, r = n, mid, ans = 0;
    pii tmp;
    while(l != r){
        //binary search penalty
        mid = (l + r) >> 1;
        tmp = DP(mid);
        if(tmp.ss < k){
            l = mid + 1;
            ans = max(ans, tmp.ff - mid * tmp.ss);
        }else r = mid;
    }
    return max(ans, DP(l).ff - l * k);
}
signed main(){
    cin >> n >> k;
    int l = 0;
    for(int i = 0; i < n; i++){
        cin >> A[i];
        cnt[A[i]]++;
        while(cnt[A[i]] > 1) cnt[A[l++]]--;
        L[i] = l;
    }
    cout << BIS();
    return 0;
}

感謝 `東霖` 幫忙抓bug
> [name=thanksone]