# 2023 南 11 校聯合寒訓 - STL容器題解
:::warning
**Slide 講義**
link : https://slides.com/jasonliu424/cpp-stl/
:::
:::info
**有地方沒講清楚歡迎來問我 > <**
Github ⚙️ https://github.com/jason810496
FB 🧬 https://www.facebook.com/JasonBigCow
IG 🐮 https://www.instagram.com/jason2004424/
:::
:::success
**延伸閱讀**
非常建議把 **CSES** 的 **Searching & Sorting** 都寫一遍
link : https://cses.fi/problemset/list/
裡面有很多**資料結構**( `STL` `pbds` `BIT` )與**排序、搜尋**搭配的經典技巧！
近幾次的 **APCS 第四題**都跟延伸閱讀的題單蠻相似的！
:::
## vector
### Zerojuege : f819 圖書館
link : https://zerojudge.tw/ShowProblem?problemid=f819
:::spoiler solution
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
OAO
int n;
cin>>n;
int ans=0;
vector<int> over;
int id,d;
while(n--){
cin>>id>>d;
if( d>100 ){
over.push_back(id);
ans+=5*(d-100);
}
}
sort(all(over));
for(const auto & i : over ){
cout<<i<<' ';
}
cout<<(over.empty() ? "":"\n")<<ans<<"\n";
return 0;
}
```
:::
### TOJ : 575
link : https://toj.tfcis.org/oj/pro/575/
:::info
**要注意輸出格式：** 行尾不要有空白
:::
:::spoiler solution
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
vector<int> vec[1000005];
signed main(){
OAO
int n,k;
cin>>n>>k;
while(k--){
int a,b;
cin>>a>>b;
vec[a].push_back(b);
vec[b].push_back(a);
}
for(int i = 1; i <= n; i++){
sort(vec[i].begin(),vec[i].end());
if( vec[i].size() )cout << vec[i][0];
for(int j = 1; j < vec[i].size(); j++){
cout << ' ' << vec[i][j];
}
cout << '\n';
}
return 0;
}
```
:::
## pair
### Zerojuege : a915 二維點排序
link : https://zerojudge.tw/ShowProblem?problemid=a915
:::spoiler solution
用 `pair` 的話：連 `struct` , `compare function` 都不用寫！
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef pair<int,int> pii;
signed main(){
OAO
int n;
cin>>n;
vector<pii> vec(n);
for(auto & i :vec ){
cin>>i.F>>i.S;
}
sort(all(vec));
for(const auto & i : vec ){
cout<<i.F<<' '<<i.S<<'\n';
}
return 0;
}
```
:::
## stack
### Zerojuege : b304 Parentheses Balance
link : https://zerojudge.tw/ShowProblem?problemid=b304
:::info
**輸入格式：** 要用 `getline` 讀
**其他：** 空字串也算正確
:::
:::spoiler solution
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<stack>
#include<string>
#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
OAO
int n;
cin>>n;
string str;
getline(cin,str);
while(n--){
getline(cin,str);
if(str.empty()){
cout<<"Yes\n";
continue;
}
else if( str.size()%2 ){
cout<<"No\n";
continue;
}
stack<char> stk;
bool flag = true;
for(int i=0;i<str.size() && flag ;i++){
if( str[i] == '(' || str[i] == '[' ){
stk.push(str[i]);
}
else if( str[i] == ')' ){
if( stk.empty() || stk.size() && stk.top() != '(' ){
flag = false;
break;
}
else stk.pop();
}
else if( str[i] == ']' ){
if( stk.empty() || stk.size() && stk.top() != '[' ){
flag = false;
break;
}
else stk.pop();
}
}
cout<<(flag&&stk.empty() ? "Yes\n": "No\n" );
}
return 0;
}
```
:::
## deque
### Zerojuege : i400 字串解碼
link : https://zerojudge.tw/ShowProblem?problemid=i400
:::info
題目頗長，要仔細看，解碼要記得反著做
:::
:::spoiler solution
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<deque>
#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
OAO
int m , n;
cin>>m>>n;
vector<deque<int>> decode(m);
deque<char> orig;
string str;
for(auto & i : decode ){
cin>>str;
for(char c : str){
i.push_back( c-'0' );
}
}
cin>>str;
for(char c : str){
orig.push_back( c );
}
int mid=n/2;
for(int k=m-1;k>=0;k--){
// decode part
deque<char> after;
for(int i=n-1;i>=0;i--){
if(decode[k][i]){
after.push_back( orig.back() );
orig.pop_back();
}
else{
after.push_front( orig.back() );
orig.pop_back();
}
}
orig = after;
// swap front & back
int cnt=0;
for(int i=0;i<n;i++){
cnt+=decode[k][i];
}
if( cnt%2 ){
for(int i=0;i<mid;i++){
swap(orig[i],orig[i+mid+(n%2)]);
}
}
}
for(const char & i : orig ){
cout<<i;
}
cout<<'\n';
return 0;
}
```
:::
## set
### CSES : Distinct Numbers
link : https://cses.fi/problemset/task/1621
:::spoiler solution
```cpp=
#include<iostream>
#include<utility>
#include<vector>
#include<set>
using namespace std;
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second
#define PB push_back
#define all(x) x.begin(),x.end()
signed main(){
OAO
int n,x;
set<int> Uset;
cin>>n;
while( n-- ){
cin>>x;
Uset.insert(x);
}
cout<<Uset.size()<<"\n";
return 0;
}
```
:::
### Zerojuege : f607 切割費用
link : https://zerojudge.tw/ShowProblem?problemid=f607
:::info
:::spoiler 一些提示
1. 考慮邊界條件
2. 會用到 `二分搜` 跟 `iterator`
:::
:::spoiler solution
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
OAO
ll sum=0;
int n,len,tmp,idx;
cin>>n>>len;
set<int> S{0,len};
vector<int> vec(n);
for(int i=0;i<n;i++){
cin>>tmp>>idx;
vec[idx-1]=tmp;
}
set<int>::iterator L,R;
for(int i=0;i<n;i++){
S.insert(vec[i]);
L=S.lower_bound(vec[i]);
L--;
R=S.upper_bound(vec[i]);
sum+=(*R-*L);
}
cout<<sum;
return 0;
}
```
:::
## map
### CSES : Sum of Two Values
link : https://cses.fi/problemset/task/1640
:::spoiler solution
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<map>
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
OAO
int n , k;
cin>>n>>k;
vi arr(n);
map<int,int> MP;
for(int &i: arr) cin>>i;
bool flag = false;
for(int i=0;i<n;i++ ){
int target = k-arr[i];
if( MP.find(target)!=MP.end() ){
cout<<MP[ target ]+1<<" "<<i+1<<"\n";
flag = true;
break;
}
MP[ arr[i] ]=i;
}
if( !flag ) cout<<"IMPOSSIBLE\n";
return 0;
}
```
:::
## priority_queue
### Leetcode : kth largest element in an array
link : https://leetcode.com/problems/kth-largest-element-in-an-array/
:::info
嘗試用 $O( n \log k )$ 的時間複雜度來解
:::
:::spoiler solution
```cpp=
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int,vector<int>,greater<int>> pq;
for(const int & i : nums ){
pq.push(i);
if(pq.size()>k) pq.pop();
}
return pq.top();
}
};
```
:::
### CSES : Sliding Median
link : https://cses.fi/problemset/task/1076
:::info
這題預設用 `priority_queue` 解，不過也可以用 `multiset` ( 其實後者應該比較好想怎麼解XD )
還有 `pbds` 跟 `binary index tree` 也可以解
:::spoiler 一些提示（ 用 PQ 的話 ）
1. 中位數可以看成： 前半序列的最大值 or 後半序列的最小值
2. 所以可以開 maxHeap 跟 minHeap 來維護
3. PQ 只能刪除最大或最小值，但是有可能現在在 PQ 中的元素已經不在 window 當中了
4. 承 `3.` 所以需要另一個資料結構來紀錄「哪些元素已經不在 window 中 」這個狀態
5. 需要維護兩個 PQ 的平衡性
:::
:::spoiler solution
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<map>
#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef pair<int,int> pii;
const int MAX_N = 2e5+5;
int arr[MAX_N];
signed main(){
OAO
int n,k;
cin>>n>>k;
map<int,int> Delete;
priority_queue<int> Left;
priority_queue<int,vector<int>,greater<int>> Right;
for(int i=0;i<n;i++){
cin>>arr[i];
}
int mid=(k+1)/2;
int x;
for(int i=0;i<k;i++){
Right.push(arr[i]);
}
for(int i=0;i<mid;i++){
Left.push(Right.top());
Right.pop();
}
cout<<Left.top()<<" ";
for(int i=k;i<n;i++){
int balance = 0;
int old = arr[i-k];
// delete old element from window
if( old<=Left.top() ){
balance--;
if( old==Left.top() ) Left.pop();
else Delete[ old ]++;
}
else{
balance++;
if( old==Right.top() ) Right.pop();
else Delete[ old ]++;
}
// insert cur into pq
if( arr[i] <= Left.top() ){
balance++;
Left.push(arr[i]);
}
else{
balance--;
Right.push(arr[i]);
}
// balance two pq
if(balance<0) {
Left.push(Right.top());
Right.pop();
}
if(balance>0) {
Right.push(Left.top());
Left.pop();
}
while( Right.size() && Delete[Right.top()]) {
Delete[Right.top()]--;
Right.pop();
}
while( Left.size() && Delete[Left.top()]) {
Delete[Left.top()]--;
Left.pop();
}
cout<<Left.top()<<' ';
}
return 0;
}
```
:::
:::success
如果想知道題怎麼用其他資料結構來解的話：
可以看 [這邊](https://usaco.guide/problems/cses-1076-sliding-median/solution)
:::
###### tags: `題解` `資料結構` `競程`
Sign in with Wallet
Connect another wallet