---
title: STL練習賽題解 # 簡報的名稱
tags: 7th 題解 # 簡報的標籤
---

# STL練習賽題解

## A. Bit++
> 來源: [CF 282A](https://codeforces.com/contest/282/problem/A)

### 想法：
直接判斷第二個字元是什麼就好。

:::spoiler 為什麼?
你會發現指令只有四種：

1. X++
2. ++X
3. X--
4. --X

其中，前兩種要做`X+=1`，後兩種要做`X-=1`，你發現這剛好可以用指令的第二個字元區分開來。
:::

:::spoiler <font size=4>Sample Code :</font>

#include<iostream>

using namespace std;

int main(){

    int n,now=0;
    cin>>n;
    
    while(n--){ // 共做 n 次
        string s; 
        cin>>s;
        if(s[1]=='+') now++; // 判斷第二個字元是什麼
        else now--;
    }
    
    cout<<now<<endl;
}

:::

## B. Minimal string
> 來源: [CF 797C](https://codeforces.com/contest/797/problem/C)

### 想法：
#### 小知識：
字典序最小就是
1. 從第一個字母開始比大小，有不一樣的就小的排前面
2. 長度不一樣時，長度小的排前面（空白最小）

#### 進入正題：
可以發現 $t$ 是一個 **stack**，且我們希望小的字母排前面，因此我們可以從 $s$ 的第一個字元開始往後遍歷，如果目前這個字元滿足：
* 在這個字元的後面沒有比他大的
* **stack** 的頂端沒有比他大

那麼就就應該把這個字元丟到 $u$ (答案) 的最後

相對的，如果 **stack** 頂端的字元滿足：
* 目前遍歷到的字元的後面（含那個字元）沒有比他大的

那麼也同樣應該把它丟到答案的最後

:::spoiler <font size=4>Sample Code :</font>

#include<iostream>
#include<stack>

using namespace std;

string s,u;
stack<char> t;

int last[30]; // 記錄每個字元最後出現在哪裡

int main(){

    cin>>s;
    
    for(int i=0;i<s.size();i++){
        last[s[i]-'a']=i;
    }
    
    char c='a'; // 目前的目標字元，從最小的 a 開始
    
    for(int i=0;i<s.size();i++){
    
        while(c<='z'&&i>=last[c-'a']){
            c++; // 進到這裡的 c 在後面都不會再出現了
        }
        
        while(t.size()&&t.top()<=s[i]&&t.top()<=c){
            u+=char(t.top()); // 將 stack 中可以丟的先丟
            t.pop();
        }
            
        if(s[i]<=c){ // 判斷當前字元可不可以丟
            u+=s[i]; 
        }
        else{ // 如果不行就先放到 stack 裡面
            t.push(s[i]);
        }
    }
    
    while(t.size()){ // 清空 stack
        u+=char(t.top());
        t.pop();
    }
    
    cout<<u<<endl;
}

:::

## C. Plug-in
> 來源: [CF 81A](https://codeforces.com/contest/81/problem/A)

### 想法：
從前面開始檢查每一個字，同時記錄目前留下來的字。嘗試加入一個字的時候，有兩種可能的情況：

1. 新字元與留下來的最後一個字相同：
若留下新字元會產生兩個連續的相同字元，因此移除新字元與留下的最後一個字元。例如，`abcbca + a`會產生`abcbc`
2. 新字元與留下來的最後一個字不同：
新字元不會產生連續相同字元，因此留下這個新字元。例如，`abcbca + d`會產生`abcbcad`

容易知道這樣一番操作，不會留下來任何連續的重複字元。因此我們需要一個能在尾部新增、刪除的資料結構，也就是**stack**。實作上`std::vector`在任何方面(功能、速度)都勝過`std::stack`，因此推薦直接用`std::vector`實現stack的功能。

:::spoiler <font size=4>Sample Code :</font>

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    // std::stack can be fully replaced with std::vector
    vector<char> st;
    
    for(char ch:s){ // next character to be added
        if(st.size()!=0 && st.back()==ch){
            st.pop_back(); // removed
        }else{
            st.emplace_back(ch); // left (for now)
        }
    }

    for(char ch:st){
        cout<<ch;
    }
    cout<<"\n";
    return 0;
}

:::

## D. Number of Pairs
> 來源: [CF 1538C](https://codeforces.com/contest/1538/problem/C)

### 想法：
把整個序列排序後，對於每個數，可以跟他配對的會是一段連續的區間
如果暴力的去找，複雜度會是 $O(N^2)$，但 $N<=2*10^5$，所以不行
對於具有單調性的序列我們可以用[二分搜](https://hackmd.io/@nehs-iced-7th/S1bNH5YB_#/)來解決，詳細內容之後會教
在 STL 中，有內建的二分搜：lower_bound 跟 upper_bound，用法如下

lower_bound(某STL.begin(),某STL.end(),要二分搜的東西 (看這個STL是包什麼資料型態))
-> 回傳這個東西"第一個"可以放的位置的迭代器

lower_bound(...) - vector.begin() 可以得到那個位置的 index 
就是可以丟在 某陣列[這裡] 的東西，比如說 a[5] 的 5 的那個位置

upper_bound(某STL.begin(),某STL.end(),要二分搜的東西 (看這個STL是包什麼資料型態))
-> 回傳這個東西"最後一個"可以放的位置的迭代器

剩下跟 lower_bound() 一樣

於是我們就可以二分搜出，每個人可以配對的第一個人跟最後一個人，要注意重複的問題

:::spoiler <font size=4>Sample Code :</font>

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void solve(){

    int n,l,r;
    long long ans=0;
    vector<int> v;
    
    cin>>n>>l>>r;
    
    for(int i=0;i<n;i++){
        int x; 
        cin>>x;
        v.push_back(x);
    }
    
    sort(v.begin(),v.end()); // 排序原序列
    
    for(int i=0;i<n;i++){
    
        int tr=upper_bound(v.begin(),v.end(),r-v[i])-v.begin(); // 第一個不能配對的位置
        int tl=lower_bound(v.begin(),v.end(),l-v[i])-v.begin(); // 第一個可以配對的位置
        
        tl=max(tl,i+1); // 避免選到比自己小的，才不會重複選到
        tr=max(tr,i+1);
        
        ans+=tr-tl;     
    }
    
    cout<<ans<<endl;
}

int main(){
    int t; 
    cin>>t;
    
    while(t--){
        solve();
    }
}

複雜度：$O(NlogN)$
:::

## E. Berpizza
> 來源: [CF 1468C](https://codeforces.com/contest/1468/problem/C)

### 想法
~~砸資結~~
同時維護兩個不同排序方法(先來在前和比較有錢的在前)的priority_queue(或者你是大毒梟 喜歡用set)
在要替客人上菜的時候看過去的紀錄裏面這個編號的客人有沒有被上菜過
有的話就pop掉 直到你找到一個沒有被上菜過的 你就幫他上菜(輸出他的編號) 並記得把這個客人標記為以上菜過的
複雜度 $O(NlogN)$

:::spoiler <font size=4>Sample Code with priority_queue :</font>

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=500005;
int counter;
bool vis[N];
struct ff
{
     int a,b;//a代表有多少錢 b代表他的編號(第幾個來)
     bool operator>(const ff&x)const
     {
          return b>x.b;
     }//排序編號
     bool operator<(const ff&x)const
     {
          if(a==x.a)return b>x.b;
          return a<x.a;
     }//排序錢的多寡
};
priority_queue<ff,vector<ff>,greater<ff>>M;//先來先上的排序法
priority_queue<ff,vector<ff>,less<ff>>P;//有錢先上的排序法
void solve()
{
     int n;cin>>n;
     while(n--)
     {
          int now;cin>>now;
          if(now==1)
          {
               ff the;cin>>the.a;
               the.b=++counter;
               M.push(the);
               P.push(the);
          }
          else if(now==2)
          {
               while(vis[M.top().b])M.pop();//持續查看最前端的客人 上過就踢掉看下一個
               cout<<M.top().b<<" ";//迴圈結束表示目前最前面的那個就是最小還沒上過的
               vis[M.top().b]=1;//把他標記為上過後 再把他踢掉
               M.pop();
          }
          else
          {
               while(vis[P.top().b])P.pop();
               cout<<P.top().b<<" ";
               vis[P.top().b]=1;
               P.pop();
          }
     }
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    solve();
}

:::

:::spoiler <font size=4>Sample Code with std::set :</font>

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=500005;
int counter;
struct ff
{
     int a,b;
     bool operator<(const ff&x)const
     {
          return b<x.b;
     }
     bool operator>(const ff&x)const
     {
          if(a==x.a)return b<x.b;
          return a>x.a;
     }
};
set<ff,less<ff>>M;
set<ff,greater<ff>>P;
void solve()
{
     int n;cin>>n;
     while(n--)
     {
          int now;cin>>now;
          if(now==1)
          {
               ff the;cin>>the.a;
               the.b=++counter;
               M.insert(the);
               P.insert(the);
          }
          else if(now==2)
          {
               ff the=*M.begin();
               cout<<the.b<<" ";
               M.erase(M.begin());//set因為結構的關係 可以O(logN)刪除
               P.erase(the);//所以就可以快速地同時刪除兩個set裡的東西
          }
          else
          {
               ff the=*P.begin();
               cout<<the.b<<" ";
               P.erase(P.begin());
               M.erase(the);
          }
     }
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    solve();
}

:::
:::spoiler #### set跟priority_queue的快慢差距
:::