ap352第三章

ap352第三章

二月 07, 2025

3-1樹的高度與根慢速解:

複雜度O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define N 100010
typedef long long LL;
using namespace std;

int main()
{
    int parent[N]={0};
    int h[N]={0};
    int deg[N];
    int n,ch;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>deg[i];
        for(int j=0;j<deg[i];j++){
            cin>>ch;
            parent[ch]=i;
        }
    }
    int root;
    for(int i=1;i<=n;i++){
        if(parent[i]==0){
            root=i;
            break;
        }
    }
    cout<<root<<'\n';

    for(int i=1;i<=n;i++){
        int cnt=0;
        for(int j=i;j!=0;j=parent[j]){
            h[j]=max(h[j],cnt);
            cnt++;
        }
    }
    int total=0;
    for(int i=1;i<=n;i++){
        total+=h[i];
    }
    cout<<total;
    return 0;
}

時間複雜度過高
以下優化使用:bottom-up sequence、queue
複雜度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#define N 100010
typedef long long LL;
using namespace std;

int main()
{
    int parent[N]={0};
    int h[N]={0};
    int deg[N];
    queue<int> Q;
    int n,ch;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>deg[i];
        if(deg[i]==0) Q.push(i); //把葉節點加入queue處理
        for(int j=0;j<deg[i];j++){
            cin>>ch;
            parent[ch]=i;
        }
    }
    int root,total=0;
    while(1){
        int v=Q.front();
        Q.pop();
        total+=h[v];
        int p=parent[v];
        if(p==0){
            root=v;
            break;
        }
        h[p]=max(h[p],h[v]+1);
        if(--deg[p]==0){ //當一個節點的所有子節點皆以處理完，就可以加入queue處理
            Q.push(p); 
        }
    }
    cout<<root<<'\n';
    cout<<total;
    return 0;
}

3-2括弧配對

https://judge.tcirc.tw/problem/d026
這是自製stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

int main()
{
    char in[210],ch[7]="({[)}]";
    int S[210],top;
    while(cin>>in){
        if(cin.eof()){
            break;
        }
        top=-1;
        int len=strlen(in); //計算長度
        bool error=false;
        for(int i=0;i<len;i++){
            int k=strchr(ch,in[i])-ch;//strchr 函數會返回一個指向目標字符在字符串中第一次出現位置的指標。如果找到了，strchr 返回的指標會指向該字符在 ch 陣列中的地址，並且可以通過減去 ch 的基址來計算出字符在陣列中的索引。(在ch中找in[i])
             //or using: for (k=0; k<6 && ch[k]!=in[i]; k++);
             if(k<3){
                S[++top]=k;
             }else{
                 if(top<0||k!=S[top]+3){
                    error=true;
                    break;
                 }
             top--;
             }
        }
        if(top>=0){
            error=true;

        }
        cout<<(error? "no":"yes"); //要括弧是因為cout要先執行後才能到?執行，不括弧輸出會錯
        cout<<'\n';

    }
    return 0;
}

以下為使用stl:
(自己寫版本)
重點為使用副程式，讓stack不需要自己清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;
void stac(char in[]){
    stack<int> S;
    char ch[]="([{)]}";
    int len=strlen(in);
    bool error=false;
    for(int i=0;i<len;i++){
        if((strchr(ch,in[i])-ch)<3){
            S.push(strchr(ch,in[i])-ch);
        }else{
            if((strchr(ch,in[i])-ch-S.top())==3){
                S.pop();
            }else{
                error=true;
                break;
            }
        }
    }
    if(!S.empty()){
        error=true;
    }
    cout<<(error?"no\n":"yes\n");

}
int main()
{
    char in[210];
    while(cin>>in){
        if(cin.eof()){
            break;
        }
        stac(in);
    }
    return 0;
}

在面對eof輸入時，以上也是一個很好的範例。(也可以使用streamstring)

stack缺點:無法用auto遍歷

3-3加減乘除

https://judge.tcirc.tw/problem/d027
乘除先處理
O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>

using namespace std;

int main()
{
    stack<int> s1;
    stack<char> s2;
    string s;
    cin>>s;
    int temp;
    for(char t:s){

        if(t>='0'&&t<='9'){

            if(!s2.empty()&&s2.top()=='*'){
                temp=s1.top()*(t-'0');
                s1.pop();
                s1.push(temp);
                s2.pop();
            }else if(!s2.empty()&&s2.top()=='/'){
                temp=s1.top()/(t-'0');
                s1.pop();
                s1.push(temp);
                s2.pop();
            }else{

                s1.push(t-'0');
            }
        }else{
            s2.push(t);
        }
    }
    int temp2;
    stack<int> s11;
    stack<int> s22;
    while(!s2.empty()){
        s22.push(s2.top());
        s2.pop();
    }
    while(!s1.empty()){
        s11.push(s1.top());
        s1.pop();
    }
    while(!s22.empty()){
        temp=s11.top();
        s11.pop();
        temp2=s11.top();
        s11.pop();
        if(s22.top()=='+'){
            s11.push(temp+temp2);
        }else if(s22.top()=='-'){
            s11.push(temp-temp2);
        }
        s22.pop();
    }
    cout<<s11.top();
    return 0;
}

3-4最接近高人

https://judge.tcirc.tw/problem/d028
因為每個傢伙只會進入堆疊一次，進去一次不可能出來兩次，所以整體的複雜度是
O(n)。這種算總帳的方式來計算複雜度稱為均攤分析(amortized analysis)，這
個題目是均攤分析的經典教學題目。
(此為單調序列題目)
O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
#define N 300010
#define oo 10000001
typedef long long LL;
int a[N];
stack<int>S;
int main() {
    int n;
    LL total=0;
    cin>>n;
    S.push(0);
    a[0]=oo;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        while(a[S.top()]<=a[i]){ //重點是維護一個遞減序列
            S.pop();
        }
        total+=i-S.top();
        S.push(i);
    }
    cout<<total;
    return 0;
}
單調序列重點:
  • 棧裡存的是位置而不是值

3-5 帶著板凳排雞排的高人

https://judge.tcirc.tw/problem/d029
因為「看起來像可以用單調棧處理」的題目，其實藏了不少陷阱。結論在前：本題並沒有一個「單純單調棧」就能一次從左掃到右、同時得到正確答案的做法。原因在於「能否擋住第 i 個人」所使用的高度門檻是 
ℎ(𝑖)+𝑝(𝑖)，這個門檻會因人而異，而且還有「未來的人」可能比現在這個人更矮，導致原本對「現在這個人」沒用的矮個子，卻可能變成「未來那個人」的障礙。
這跟一般常見的「最近大於／小於元素」單調棧題型有本質差異，導致如果你把「擋不住第 i 個人」的人直接從棧裡彈掉，就可能錯失「他去擋住更矮的未來人」的機會，最後就會算錯。

那「單調序列」(Monotonic Stack/Queue) 就真的沒救了嗎？

就「單棧、單趟」的標準用法而言，確實無法同時兼顧「先算擋住 i 的人」又「保留可能擋住未來更矮的人」。 你若在「計算 i」時，直接把「擋不住 i」的前人彈掉，將來就再也拿不到他了。

而「遮蔽」(overshadow) 在經典單調棧題目裡的判斷條件通常是：

「如果我（位置 i）比棧頂那位更高，且我在他後面，那麼棧頂對未來沒用，可以彈掉。」

但本題擋人的「高度標準」是動態的：每個人都用「h(i)+p(i)」在做比較，不是固定用「h(i)」。因此不能把「擋不住當前 i」就當作「擋不住任何未來人」。

有沒有更進階的「分段」或「離線」技巧？

有些競賽題可以藉由「先把人依某種順序排好，再配合兩段式單調結構」來做，但那往往需要更複雜的「offline 排序 + 資料結構」；本題在 APCS 考試中，官方通常給的做法就是像你看到的那段 map 或平衡樹版本，時間 O(nlogn) 就夠了，也能通過。
若你硬要做出 O(n) 的解法，也勢必得設計出「同時能查找『第一個大於 (h(i)+p(i))』，又能在每次 i 計算完後再做『刪除所有比 h(i) 矮者』」的結構，而且要能在不丟失「對未來可能有用的人」的前提下，仍維持單趟或雙趟即可。
但實務上，這樣的資料結構通常不會是「單純的單調棧」：
你需要能「在棧裡中間」搜尋到「第一個大於 (h(i)+p(i))」(這就不是單純 LIFO 的棧)；
還要能在「計算完 i」之後，再把所有「比 h(i) 矮」的人去除。
這其實就已經接近「平衡二元搜尋樹」或「跳表(skip list)」之類的結構了。
以下是解法，我不會這題QQ
題目的參考解法是用 C++ 的平衡樹（std::map）或類似結構，做兩件事：

先找出「第一個身高 > (h(i) + p(i))」的前人」
這可用 upper_bound(h(i)+p(i)) 找到「比 h(i)+p(i) 大的最小身高」對應的人，進而算出 S(i)。

再做「遮蔽/覆蓋」(overshadow) 的刪除：
用 upper_bound(h(i)) 找到第一個「大於 h(i)」的身高，並刪掉所有「小於等於 h(i)」的紀錄。
也就是說，若「當前人的實際身高」比某些人都還高，就把那些更矮的人全部移除，因為「在隊伍順序上，你（i）在他們後面、而且你又更高」，對未來更後面的人而言，如果需要一個「比他高」的前人，你會比那些矮個子更好、更近，所以那些矮個子等於被你「遮住」了。

重點在於：它先用舊的資料結構查完 S(i)（也就是先確定「能不能擋住 i」），再進行遮蔽刪除。
這樣就不會「在計算第 i 人」前，就先把可能擋不住第 i 人、但能擋住未來更矮之人的元素丟掉」。

而用 map 或平衡樹去做時，每次找「第一個大於某值」是 O(logn)，刪除區間也是 O(logn)（實務上有一些常數因子），整體 O(nlogn) 就能跑完。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <map>
using namespace std;
map<int, int> mp; //key表示身高,value表示索引值(位置)
map<int, int>::iterator it;
int h[200005], p[200005];
int main(){
    int n;
    long long sum;
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> h[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> p[i];
        }
        mp[h[0]] = 0; //加入第一個人
        sum = 0; //加入第一個人的總挑戰人數
        for (int i = 1; i < n; i++) {
            it = mp.upper_bound(h[i] + p[i]); //找出大於h[i] + p[i]第一個人
            if (it == mp.end()) sum += i;  //所有人都可以挑戰
            else {
                sum += i - it->second - 1; //it->second為大於h[i] + p[i]第一個人的位置
            }
            it = mp.upper_bound(h[i]); //找出大於h[i]第一個人
            mp.erase(mp.begin(), it);  //刪除所有小於等於h[i]的元素，刪除包含mp.begin()不包含it
            mp[h[i]] = i; //將h[i]加入
        }
        cout << sum << endl;
    }
}

3-6砍樹

https://judge.tcirc.tw/problem/d030
用直覺寫的
複雜度O(n)
雖然看起來for裡面有while，不過每個元素只會進入vector一次，根據之前學的均攤分析(amortized analysis)複雜度並不會增加。O(2n)<=>O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

int main()
{
    vector<LL> v;
    LL n,l;
    cin>>n>>l;
    LL s1[n+2];
    LL s2[n+1];
    s2[0]=10000000000;
    s1[0]=0;
    s1[n+1]=l;
    LL total=0;
    LL maxx=0;
    for(int i=1;i<=n;i++){
        cin>>s1[i];
    }
    v.push_back(0);
    for(int i=1;i<=n;i++){
        cin>>s2[i];
        while(!v.empty()&&(s1[v.back()]+s2[v.back()]<=s1[i])){
            maxx=max(maxx,s2[v.back()]);
            v.pop_back();
            total++;
        }
        if(!v.empty()&&s1[i]-s2[i]>=s1[v.back()]){
            maxx=max(maxx,s2[i]);
            total++;
        }else{
            v.push_back(i);
        }
    }
    cout<< total<<'\n';
    cout<<maxx;
    return 0;
}

用struct實作雙向linked-list解題:
O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
//  topological sort and linked list
#define N 100010
#define oo 1000000001
using namespace std;

struct {
    int c,h;// center and height
    int pre,next;// linked list
    int alive;
}tree[N];
queue<int> Q;
void removable(int i){
    if(!tree[i].alive){
        return;
    }
    int pree=tree[i].pre,nextt=tree[i].next;
    if(tree[i].c-tree[i].h>=tree[pree].c||tree[i].c+tree[i].h<=tree[nextt].c){
        Q.push(i);
        tree[i].alive=0;
        tree[pree].next=nextt;
        tree[nextt].pre=pree;
    }
    return;
}
int main()
{
    int n,l;
    int total=0,high=0;
    cin>>n>>l;
    for(int i=1;i<=n;i++){
        cin>>tree[i].c;
    }
    for(int i=1;i<=n;i++){
        cin>>tree[i].h;
    }
    for(int i=1;i<=n;i++){
        tree[i].pre=i-1;
        tree[i].next=i+1;
        tree[i].alive=1;
    }
    tree[0].c=0;
    tree[0].h=oo;
    tree[n+1].c=l;
    tree[n+1].h=oo;
    for(int i=1;i<=n;i++){
        removable(i);
    }
    while(!Q.empty()){
        int v=Q.front();
        Q.pop();
        total++;
        high=max(high,tree[v].h);
        removable(tree[v].pre);
        removable(tree[v].next);
    }
    cout<<total<<'\n'<<high;
    return 0;
}

3-7正整數序列之最接近的區間和

https://judge.tcirc.tw/problem/d031
此題是滑動視窗(Sliding window)
O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

int main()
{
    LL n,k;
    cin>>n>>k;
    LL A[n];
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    LL total=0;
    LL ans=0;
    LL leftbound=0;
    LL maxx=0;
    for(int i=0;i<n;i++){
        total+=A[i];
        while(total>k&&leftbound<i){
            total-=A[leftbound];
            leftbound++;
        }
        if(total>maxx){
            maxx=total;
            ans=1;
        }else if(total==maxx){
            ans++;
        }
    }
    cout<<maxx<<'\n'<<ans;
    return 0;
}

3-8 固定長度區間的最大區段差

https://judge.tcirc.tw/problem/d032
嘗試用O(nlogn)實作，發現居然過了… logn是map插入與刪除
這裡用map模擬multiset是壞習慣，因為刪除時要自己維護數量，不過map好用，讚 :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

int main()
{
    map<LL,LL> m;
    LL n,l;
    cin>>n>>l;
    LL s[n];
    LL maxx=0;
    for(LL i=0;i<n;i++){
        cin>>s[i];
    }
    for(LL i=0;i<l;i++){
        m[s[i]]++;
    }
    auto it2=m.end();
    it2--;
    auto it1=m.begin();
    maxx=it2->first-it1->first;
    for(LL i=l;i<n;i++){
        m[s[i]]++;
        if(m[s[i-l]]==1){
            m.erase(s[i-l]);
        }else{
            m[s[i-l]]--;
        }
        it1=m.begin();
        it2=m.end();
        it2--;
        maxx=max(maxx,it2->first-it1->first);
    }
    cout<<maxx;
    return 0;
}

果然有更快的方法，以下是教科書中O(n)的解法:
使用deque同時運用跟3-4一樣的單調性建立max與min

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>

using namespace std;
int ans=0;
deque<int> max_q,min_q;
int main()
{
    int n,l;
    cin>>n>>l;
    int s[n+10];
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    for(int i=0;i<n;i++){
        while(!max_q.empty()&&s[max_q.back()]<=s[i]){
            max_q.pop_back();
        }
        max_q.push_back(i);
        while(!min_q.empty()&&s[min_q.back()]>=s[i]){
            min_q.pop_back();
        }
        min_q.push_back(i);
        while(max_q.back()-max_q.front()>=l){
            max_q.pop_front();
        }
        while(min_q.back()-min_q.front()>=l){
            min_q.pop_front();
        }
        ans=max(s[max_q.front()]-s[min_q.front()],ans);
    }
    cout<<ans;
    return 0;
}

3-9最多色彩帶

https://judge.tcirc.tw/problem/d033
deque 真的挺方便，可以用auto遍歷，偵錯容易
O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,l;
    cin>>n>>l;
    int s[n];
    int co[n+10]={};
    int ans=0;
    int maxx=0;
    deque<int> d;
    for(int i=0;i<n;i++){
        cin>>s[i];
        d.push_back(i);
        if(++co[s[i]]==1){
            ans++;
        }
        if((d.back()-d.front())>=l){
            if(--co[s[d.front()]]==0){
                ans--;
            }
            d.pop_front();
        }
        maxx=max(ans,maxx);
        /*for(auto t:d){
            cout<<t<<' ';
        }
        cout<<'\n';*/
    }
    cout<<maxx;


    return 0;
}

3-10全彩彩帶 (需離散化或字典) (@@)

https://judge.tcirc.tw/problem/d034
不知為何用codeblock陣列設成這麼大時會當機，但丟進judge跑得動，真神奇
最壞:O(nlogn) 一般:O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define N 1000010
using namespace std;

int main()
{
    int n;
    cin>>n;
    int temp;
    map<int,int> m,M;
    deque<int> d;
    int co;
    int ans=10000000;
    int s[N]={};
    for(int i=0;i<n;i++){
        cin>>temp;
        s[i]=temp;
        m[temp]++;
    }
    co=m.size();
    for(int i=0;i<n;i++){
        d.push_back(i);
        M[s[i]]++;
        while(M.size()==co){
            if(M.size()==co){
                ans=min(d.back()-d.front(),ans);
            }
            if(--M[s[d.front()]]==0){
                M.erase(s[d.front()]);
            }
            d.pop_front();
            if(M.size()==co){
                //cout<<d.back()<<' '<<d.front()<<'\n';
                ans=min(d.back()-d.front()+1,ans);
            }
        }
        /*for(auto t:d){
            cout<<t<<' ';
        }
        cout<<'\n';*/
    }
    cout<<ans+1;
    return 0;
}