---
# System prepended metadata

title: CSES題解

---

# CSES題解

## Introductory Problems
### Weird Algorithm（難度：☆）
[題目連結](https://cses.fi/problemset/task/1068)
題目簡述：
給定一個正整數n（1<=n<=10^6），若n是奇數，則n=3*n+1，否則n=n/2。輸出n從n到1的變化過程。
範例測資：
輸入：
3
輸出：
3 10 5 16 8 4 2 1
```c++=
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n;
    cin>>n;
    cout<<n;
    while(n!=1){
        cout<<' ';
        if(n%2==0){     //如果是偶數
            cout<<n/2;
            n/=2;
        }
        else{           //如果是奇數
            n*=3;
            n+=1;
            cout<<n;
        }
    }
    cout<<endl;
```
### Missing Number（難度：☆）
[題目連結](https://cses.fi/problemset/task/1083)
題目簡述：
第一行給定一個n（2<=n<=2*10^5），第二行給1~n之間的n-1個數（少一個），求出少了哪個數字。
範例測資：
輸入：
5
2 3 1 5
輸出：
4
```c++=
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    set<int> num;
    for(int i=1; i<=n; i++){
        num.insert(i);         //1~n的所有數字
    }
    int a;
    for(int i=0; i<n-1; i++){
        cin>>a;
        num.erase(a);          //把出現過的刪掉
    }
    for (const auto &s : num) {
        cout << s << endl;     //輸出剩下的那個
    }
}
```
### Repetitions（難度：★）
[題目連結](https://cses.fi/problemset/task/1069)
題目簡述：
給定一行字串，會出現的字元包含A T C G，問你連續最長的相同字元是多長。
範例測資：
輸入：
ATTCGGGA
輸出：
3

解題邏輯：
如果第i個字元和第i-1個字元一樣，則n[i]=n[i-1]+1，否則n[i]=1
ATTCGGGA
１１２１１２３１



| Ａ | Ｔ | Ｔ | Ｃ | Ｇ | Ｇ | Ｇ | Ａ　|
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| １     | １     | ２     |１     |１     |２     |３     |１     |

然後排序，即可求出最大值

```c++=
#include<bits/stdc++.h>
using namespace std;
int main(){
    string x;
    cin>>x;
    int m=x.size();
    int n[m];
    for(int i=0; i<m; i++)n[i]=1;
    for(int i=1; i<m; i++){
        if(x[i-1]==x[i])n[i]+=n[i-1];
    }
    sort(n, n+x.size());
    cout<<n[m-1]<<endl;
}
```
### Increasing Array（難度：★）
[題目連結](https://cses.fi/problemset/task/1094)
題目簡述：
給定n和一個長度為n的陣列，你可以對陣列的每一個數+1，請問總共要做幾次+1此陣列才會變成非嚴格遞增陣列。
例：
3 2 5 1 7（原本陣列）
3 3 5 1 7（1）
3 3 5 2 7（2）
3 3 5 3 7（3）
3 3 5 4 7（4）
3 3 5 5 7（5 非嚴格遞增陣列）
總共五次
範例測資：
輸入：
5
3 2 5 1 7
輸出：
5
```c++=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n;
    cin>>n;
    int num[n];
    for(int i=0; i<n; i++){
        cin>>num[i];
    }
    int ans=0;
    for(int i=1; i<n; i++){
        while(num[i-1]>num[i]){
            num[i]++;
            ans++;
        }
    }
    cout<<ans<<endl;
}
```
### Permutations（難度：★★）
[題目連結](https://cses.fi/problemset/task/1070)
題目簡述：
給定n，讓你對1~n排序，排序後任兩個數字的差不為1。輸出排序後的數列。因為此數列不唯一，所以輸出任意一組都算對。
範例測資：
輸入：
5
輸出：
4 2 5 3 1
輸入：
3
輸出：
NO SOLUTION

解題邏輯：
先輸出1, 3, 5, 7, 9，再輸出2, 4, 6, 8, 10。
```c++=
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n==1){
        cout<<'1'<<endl;
        return 0;
    }
    if(n<=3){
        cout<<"NO SOLUTION"<<endl;
        return 0;
    }
    vector<int> left, right;
    for(int i=1; i<=n; i++){
        if(i%2==1)left.push_back(i);
        else right.push_back(i);
    }
    for(int i=0; i<right.size(); i++){
        cout<<right[i]<<' ';
 
    }
    for(int i=0; i<left.size(); i++){
        cout<<left[i];
        if(i+1<left.size())cout<<' ';
    }
 
    cout<<endl;
}
```

### Number Spiral（難度：★★☆）
[題目連結](https://cses.fi/problemset/task/1070)
題目簡述：
![spira](https://hackmd.io/_uploads/SkNcmLGuJg.png)
輸入t，詢問t次。每次給定x, y，問在第x, y項的數字是多少？
範例測資：
輸入：
3
2 3
1 1
4 2
輸出：
8
1
15

```c++=
#include<iostream>
#define int long long
using namespace std;
signed main(){
  int t;
  cin>>t;
  while (t--){
    int x, y;
    cin >> y >> x;
    int maxi = max(x,y);
    int square = (maxi - 1) * (maxi - 1);
    if (maxi % 2 == 0){
      if (x > y){
        cout << square + y << endl;
      }
      else{
        cout << (maxi * maxi) - x + 1 << endl;
      }
    }
    else{
      if (x > y){
        cout << (maxi * maxi) - y + 1 << endl;
      }
      else{
        cout << square + x << endl;
      }
    }
  }
}
```

### Two Knights（難度：★☆）
[題目連結](https://cses.fi/problemset/task/1072)
題目簡述：
給定n，問從1*1到n*n的棋盤上，有幾種方法可以放置兩個騎士，而且兩個騎士不會互相攻擊。
範例測資：
輸入：
8
輸出：
0
6
28
96
252
550
1056
1848

下圖是2*2的所有解
![image](https://hackmd.io/_uploads/rkeoDIz_yl.png)
下圖是會互相攻擊的狀況
![image](https://hackmd.io/_uploads/Bkv3w8MO1l.png)

```c++=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n;
    cin>>n;
    int ans=0;
    for(int i=1; i<=n; i++){
        cout<<((i*i-1)*(i*i))/2-4*(i-1)*(i-2)<<endl;
    }
}
```
### Two Sets（難度：★★★）
[題目連結](https://cses.fi/problemset/task/1092)
題目簡述：
給定一個n，要把從1~n的所有數分成兩堆，兩堆的和要相同。輸出任一一組解皆算正確。

輸出格式：
YES
length of group A
elements in group A
length of group B
elements in group B
/
NO

範例測資：
輸入：
7
輸出：
YES
4
1 2 4 7
3
3 5 6
輸入：
6
輸出：
NO

```c++=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n;
    cin>>n;
    if((n+1)*n%4==0){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
        return 0;//不行就強制結束
    }
    int maxm=(n+1)*n/4;
    int sumleft=0, sumright=0;
    vector<int> left, right;
    for(int i=n; i>0; i--){//greedy行為，如果現在的sum小加上i不大於最大值就繼續加，不然就加到另外一邊
        if (sumleft+i<=maxm){
            left.push_back(i);
            sumleft+=i;
        }
        else{
            sumright+=i;
            right.push_back(i);
        }
    }
    cout<<left.size()<<endl;
    for(int i=0; i<left.size(); i++){
        cout<<left[i];
        if(i+1<left.size())cout<<' ';
    }
    cout<<endl;
    cout<<right.size()<<endl;
    for(int i=0; i<right.size(); i++){
        cout<<right[i];
        if(i+1<right.size())cout<<' ';
    }
    cout<<endl;
}
```
### Bit Strings（難度：★★）
[題目連結](https://cses.fi/problemset/task/1617)
題目簡述：
給定一個n，代表這個01陣列長度為n，輸出這個01陣列有幾中樣式。

範例測資：
輸入：
3
輸出：
8
解釋：
000、001、010、011、100、101、110、111共8種
```c++=
#include <bits/stdc++.h>
#define ll long long
 
using namespace std;
 
ll MOD = 1e9 + 7;
 
ll power(ll base, ll expo) {
    ll ans = 1;
    while(expo) {
        if(expo & 1LL) {
            ans = (ans * base) % MOD;
        }
        base = (base * base) % MOD;
        expo >>= 1LL;
    }
    return ans;
}
 
int main() {
    ll N;
    cin>>N;
    cout << power(2LL, N) << endl;
    return 0;
}
```
### Trailing Zeros（難度：★★★）
[題目連結](https://cses.fi/problemset/task/1618)
題目簡述：
給定一個n，問n!有幾個0。

範例測資：
輸入：
20
輸出：
4
解釋：
20!=2432902008176640000 有四個0

```c++=
#include <iostream>
using namespace std;
 
// Recursive function to calculate the multiples of 5 till N
int solve(int N)
{
    if (N == 0) {
        return 0;
    }
    return N / 5 + solve(N / 5);
}
 
int main()
{
    int N;
    cin>>N;
    cout << solve(N) << "\n";
    return 0;
```
### Coin Piles（難度：★★）
[題目連結](https://cses.fi/problemset/task/1754)
題目簡述：
給定t，然後重複t次給定一個a, b，每次操作可以將a-2 b-1或是a-1 b-2，問能不能a=b=0。

範例測資：
輸入：
3
2 1
2 2
3 3
輸出：
YES
NO
YES
```c++=
#include<bits/stdc++.h>
using namespace std;
void solve(){
    long long A, B;
    cin>>A>>B;
    if ((2 * A - B) % 3 || (2 * A - B) < 0
        || (2 * B - A) % 3 || (2 * B - A) < 0)
        cout<<"NO\n";
    else cout<<"YES\n";
    return;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}
```

### Coin Piles（難度：★★★）
[題目連結](https://cses.fi/problemset/task/1755)
題目簡述：
給定一個字串，將字串重新排序後輸出，結果要是一個回文字串。

範例測資：
輸入：
AAAACACBA
輸出：
AACABACAA
```c++=
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    string s;
    cin >> s;
 
    vector<int> a(26);
    for(char c : s) a[c - 'A']++;//將char轉換成int
 
    int check = 0;
    for(int i = 0; i < 26; i++) check += (a[i] % 2);
    if(check > 1){
        cout << "NO SOLUTION";
        return 0;
    }
    string result;
    for (int i = 0; i < 26; i++){
        if(!(a[i]%2)){
            for(int j = 0; j < a[i]/2; j++) result.push_back(i + 'A');
        }
    }
    for (int i = 0; i < 26; i++){
        if(a[i]%2){
            for(int j = 0; j < a[i]; j++) result.push_back(i + 'A');
        }
    }
    for (int i = 25; i >= 0; i--){
        if(!(a[i]%2)){
            for(int j = 0; j < a[i]/2; j++) result.push_back(i + 'A');
        }
    }
 
    cout << result << endl;
    return 0;
}
```
### Gray Code（難度：★★★☆）
[題目連結](https://cses.fi/problemset/task/2205)
題目簡述：
給定一個n，求出01陣列的2^n種排序方法，輸出時每個陣列和前一個陣列不同的位數只能有1個。

範例測資：
輸入：
3
輸出：
000
001
011
010
110
111
101
100
```c++=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n; cin>>n;
    int a[1<<n + 1] = {0};
    for (int i = 0; i < n; i++)
    	cout<<0;
    cout<<endl;
    a[0] = 1;
    int x = 0;
    for (int i = 1; i < 1<<n; i++) {
    	for (int j = 0; j < n; j++) {
    	    int y = x^(1<<j);
    	    if (!a[y]) {
    	        x = y;
    	        a[y] = 1;
	        string s;
		while (y) {
         	    if (y&1) s += '1';
		    else s += '0';
        		y >>= 1;
		}
		reverse(s.begin(), s.end());
		for (int i = 0; i < n - s.size(); i++)
		    cout<<0;
	        cout<<s<<endl;
		break;
            }
        }
    }
}
```
### Tower of Hanoi（難度：★★★☆）
[題目連結](https://cses.fi/problemset/task/2165)
題目簡述：
給定一個n，代表河內塔上有幾個圓盤。目標是將所有的盤子從1號移動到3號。輸出每個步驟是從幾號柱子上拿盤到放到幾號柱子。

範例測資：
輸入：
2
輸出：
3
1 2
1 3
2 3
```c++=
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(int a, int b, int c, int n) {
	if (n == 0)
		return;
	solve(a, c, b, n-1);
	cout<<a<<' '<<c<<endl;
	solve(b, a, c, n-1);
}
signed main(){
    int n; cin>>n;
    cout<< (1<<n) - 1<<endl;
 
    solve(1, 2, 3, n);
}
```
<<用法補充說明
```
n=1
n<<1
n=2

用二進制來想 就是右側多一個0
n=001->1
n<<1
n=0010->2
```

### Creating Strings（難度：★★★）
[題目連結](https://cses.fi/problemset/task/1622)
題目簡述：
給定一個字串，輸出字串內的字的所有排序方法。

範例測資：
輸入：
aabac
輸出：
20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaa
```c++=
#include<bits/stdc++.h>
#define lli long long int
#define li long int
#define ld long double
using namespace std;
const lli mod = 1e9 + 7;
 
set<string> perms;
 
void permutations(string prefix, string suffix)
{
    if (suffix.length() == 0)
    {
        perms.insert(prefix);
        return;
    }
    for (int i = 0; i < suffix.length(); i++)
    {
        permutations(prefix + suffix[i], suffix.substr(0, i) + suffix.substr(i + 1));
    }
}
 
int main()
{
    string s;
    cin >> s;
    permutations("", s);
    cout << perms.size() << endl;
    for (auto ele : perms)
    {
        cout << ele << endl;
    }
    return 0;
}
```
### Apple Division（難度：★★）
[題目連結](https://cses.fi/problemset/task/1623)
題目簡述：
給定n，並給定n個正整數。將這些正整數分成兩堆，求兩堆之差之最小值。
範例測資：
輸入：
5
3 2 7 4 1
輸出：
1
(7+2)-(3+4+1)=1
```c++=
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
const lli mod = 1e9 + 7;
 
int main()
{
	lli n, total=0, ans=INT_MAX;
	cin >> n;
	lli arr[n];
	for(lli i = 0; i < n; i++) {
		cin >> arr[i];
		total += arr[i];
	}
	for(lli i = 0; i < 1<<n; i++) {
		lli s = 0;
		for(lli j = 0; j < n; j++) {
			if(i & 1<<j) s += arr[j];
		}
		lli curr = abs((total-s)-s);
		ans = min(ans, curr);
	}
	cout << ans;
	return 0;
}
```
### Chessboard and Queens（難度：★★★☆）
[題目連結](https://cses.fi/problemset/task/1624)
題目簡述：
在8*8的棋盤裡放下8隻皇后，不過棋盤上有些格子被保留了，不能放置皇后，求有幾種放法能使皇后間不互相攻擊。
範例測資：
輸入：
```
........
........
..*.....
........
........
.....**.
...*....
........
```
輸出：
65
```c++=
#include<bits/stdc++.h>
using namespace std;
int ground[10][10], ans=0;
bool check(int a, int b){//(a, b)會不會和原有的衝突
    for(int i=0; i<8; i++){
        for(int j=0; j<8; j++){
            if(a==i or b==j or abs(a-i)-abs(b-j)==0){
                if(ground[i][j]==1){
                    return false;
                }
            }
        }
    }
    return true;
}
void dfs(int c){//第幾排
    if(c>=8){
        ans++;
        return;
    }
    for(int i=0; i<8; i++){
        if(ground[c][i]==0){
 
            if(check(c, i)){
                ground[c][i]=1;//dfs技巧先設成1再設成0，實用
                dfs(c+1);
                ground[c][i]=0;//dfs技巧
            }
 
        }
    }
}
int main(){
    char x;
    for(int i=0; i<8; i++){
        for(int j=0; j<8; j++){
            cin>>x;
            if(x=='.'){
                ground[i][j]=0;
            }
            else{
                ground[i][j]=-1;
            }
        }
    }
    dfs(0);
    cout<<ans<<endl;
}
```
### Digit Queries（難度：★★★★）
[題目連結](https://cses.fi/problemset/task/1624)
題目簡述：
給定t，詢問t次，每個給一個n，問12345678910111213141516171819202122232425.......中第n位數字是多少?
範例測資：
3
7
19
12
輸入：
7
4
1
```c++=
#include<bits/stdc++.h>
using namespace std;
#define int long long
int findKthDigit(long long k) {
    long long digitLength = 1;
    long long count = 9;
    long long start = 1;
    while (k > digitLength * count) {
        k -= digitLength * count;
        digitLength++;
        count *= 10;
        start *= 10;
    }
    long long number = start + (k - 1) / digitLength;
    int digitIndex = (k - 1) % digitLength;
    string numberStr = to_string(number);
    return numberStr[digitIndex] - '0';
}
signed main(){
    int n, x;
    cin>>n;
    while(n--){
        cin>>x;
        cout<<findKthDigit(x)<<endl;;
    }
 
}
```
### Grid Paths（難度：★★★★☆）
[題目連結](https://cses.fi/problemset/task/1625)
題目簡述：
在8*8的棋盤裡從左上走到右下，已知其中幾部的走法，求出所有可能數。
範例測資：
??????R??????U??????????????????????????LD????D?
輸入：
201
解釋：
![image](https://hackmd.io/_uploads/Hk0QcsnOJe.png)
上圖是一種可能的走法。(DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD)
如果題目給出DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDD?
則所有可能的答案就只有一種，即上圖。
如果題目給定????????????????????????????????????????????????
則有91294種(但願我沒有算錯)
```c++=
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool vis[9][9];
int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};
int ans=0;
string str;
void solve(int x, int y, int s){
    if(x<1 or x>7 or y<1 or y>7 or vis[x][y]==1)return;
    if(x == 1 && y == 7 && s < 48)return;
    if(vis[x-1][y] && vis[x+1][y] && !vis[x][y+1] && !vis[x][y-1])return;
    if(!vis[x-1][y] && !vis[x+1][y] && vis[x][y+1] && vis[x][y-1])return;
    if(s==48){
        ans++;
        return;
    }
    vis[x][y]=1;
    if(str[s] == 'L')solve(x - 1, y, s + 1);
    if(str[s] == 'R')solve(x + 1, y, s + 1);
    if(str[s] == 'U')solve(x, y - 1, s + 1);
    if(str[s] == 'D')solve(x, y + 1, s + 1);
    if(str[s] == '?'){
        for(int i = 0;i < 4;i++){
            int nx = x + dx[i],ny = y + dy[i];
            solve(nx,ny,s+1);
        }
    }
    vis[x][y]=0;
}
signed main(){
    cin>>str;
    for(int i=1;i<=7;i++){
        vis[i][0] = 1;
        vis[8][i] = 1;
        vis[i][8] = 1;
        vis[0][i] = 1;
    }
    solve(1,1,0);
    cout<<ans<<endl;
}
```

## Sorting and Searching
### Permutations（難度：☆）
[題目連結](https://cses.fi/problemset/task/1621)
題目簡述：
給定n，並且輸入n個數。求共有幾個相異數。
範例測資：
輸入：
5
2 3 2 2 3
輸出：
2

最簡單的解法，用set解
```c++=
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n;
    cin>>n;
    int x;
    set<int> in;
    for(int i=0; i<n; i++){
        cin>>x;
        in.insert(x);
    }
    cout<<in.size();
}
```
### Permutations（難度：★★）
[題目連結](https://cses.fi/problemset/task/1084)
題目簡述：
給定n間房間，m個房客，n個房間都有一個大小值，m個房客的大小期望都不一樣。房客可以接受自己的期望±k大小的房間，且不接受和別人同居。輸出有幾個房客找到心儀的房間。
輸入格式
n, m, k
a1, a2, a3->n個房客的期望值
b1, b2, b3->m個房間的大小。
範例測資：
輸入：
4 3 5
60 45 80 60
30 60 75
輸出：
2

程式碼解說：先進行排序，如果house[i]>man[j]則代表man[j]太小，所以j++，讓更大的人來嘗試這間房子。反之亦然。
如例圖（此狀況k=0），在house[1]和man[1]時，man[1]相較house[1]更小，因此j往下數，直到j=4時house[1]=man[4]才停止。
![image](https://hackmd.io/_uploads/S15TxDfOke.png)

```c++=
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
#define int long long
int house[N], man[N];
signed main(){
    int n, m, k;
    cin>>n>>m>>k;
    for(int i=0; i<n; i++)cin>>house[i];
    for(int i=0; i<m; i++)cin>>man[i];
    sort(house, house+n);
    sort(man, man+m);
    int i=0, j=0;
    int ans=0;
    while(i<n and j<m){
        if(abs(house[i]-man[j])<=k){
            i++;
            j++;
            ans++;
        }
        else if(house[i]>man[j]){
            j++;
        }
        else{
            i++;
        }
    }
    cout<<ans<<endl;
}
```
### Ferris Wheel（難度：★★）
[題目連結](https://cses.fi/problemset/task/1090)
題目簡述：
給定n個小孩想搭纜車，一台纜車最多搭2個小孩，每個纜車可以乘載x重量。給你每個小孩的體重，求最少需要多少纜車。
輸入格式
n, x
w1, w2, w3...
範例測資：
輸入：
4 10
7 2 3 9
輸出：
3
![image](https://hackmd.io/_uploads/Sk4HVPfOJx.png)
如上圖（x=10）
當做完(1,9)之後R左移、L右移，發現(3, 8)無法收容，所以只裝8進去，然後R往左移，發現(3, 7)可以。
```c++=
#include<bits/stdc++.h>
using namespace std;
signed main(){
    int n, m, k;
    cin>>n>>m;
    vector<int> child;
    for(int i=0; i<n; i++){
        cin>>k;
        child.push_back(k);
    }
    sort(child.begin(), child.end());
    int idxl=0, idxr=n-1, ans=0;
    while(idxl<idxr){
        if(child[idxr]+child[idxl]<=m){
            idxr--;
            idxl++;
            ans++;
        }
        else{
            idxr--;
            ans++;
        }
    }
    if(idxr==idxl)ans++;//如果剩下最後一個沒有收進去纜車
    cout<<ans<<endl;
}
```
### Concert Tickets（難度：★★）
[題目連結](https://cses.fi/problemset/task/1091)
題目簡述：
給定n場演唱會，m個客人，分別給n場演唱會的門票價格以及m位客人的預算，每位客人會買在繼子預算內最貴的那一張門票。求每位客人分別買了多貴的票。若該客人沒票可買則輸出-1。
輸入格式
n, m,
a1, a2, a3->n張門票價格
b1, b2, b3->m位客人預算
範例測資：
輸入：
5 3
5 3 7 8 5
4 8 3
輸出：
3
8
-1

註：upper_bound是求小於等於、lower_bound是求小於
```c++=
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    multiset <int> s;
    for(int i = 0;i < n;i++){
        int x;
        cin >> x;
        s.insert(x);
    }
    for(int i = 0;i < m;i++){
        int x;
        cin >> x;
        auto it = s.upper_bound(x);
        if(it == s.begin()) {
            cout << "-1";
        }
        else {
            it--;
            cout << *it;
            s.erase(it);
        }
        cout << " \n"[i <= n-1];
    }
}
```
### Restaurant Customers（難度：★★☆）
[題目連結](https://cses.fi/problemset/task/1619)
題目簡述：
給定n位客人，第i位客人有來的時間ai和離開的時間bi。求餐廳裡最多同時出現幾位客人。

範例測資：
輸入：
3
5 8
2 4
3 9
輸出：
2
解釋：
![image](https://hackmd.io/_uploads/B1v3ia2OJl.png)
第一位客人和第二位客人不重疊，答案是2。

作法
![image](https://hackmd.io/_uploads/BybApp2uJg.png)
先創造一個陣列，當a, b被輸入的時候，陣列第a項+1，陣列第b項-1，等最後再O(n)掃過去就行了(上圖第五行)。當然也可以開個vector<pair<int, int>>然後作排序，會有一樣的效果。
```c++=
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> times;
	for (int i = 0; i < n; i++) {
		int start, endd;
		cin >> start >> endd;
		times.push_back({start, 1});
		times.push_back({endd, -1});
	}
 
	sort(times.begin(), times.end());
 
	int curr_ppl = 0;
	int max_ppl = 0;
	for (const pair<int, int> &t : times) {
		curr_ppl += t.second;
		max_ppl = max(max_ppl, curr_ppl);
	}
	cout << max_ppl << endl;
}
```
### Movie Festival（難度：★★☆）
[題目連結](https://cses.fi/problemset/task/1629)
題目簡述：
給定n個電影，第i部電影有開始的時間ai和結束的時間bi。求最多可以看幾部電影。

範例測資：
輸入：
3
3 5
4 9
5 8
輸出：
2
```c++=
#include <bits/stdc++.h>
using namespace std;
bool sortFnc(pair<int, int>& p1, pair<int, int>& p2)
{
    return p1.second < p2.second;
}
int solve(vector<pair<int, int> >& movies, int N)
{
    sort(movies.begin(), movies.end(), sortFnc);
    int timeElapsed = 0, moviesWatched = 0;
    for (int i = 0; i < N; i++) {
        if (movies[i].first >= timeElapsed) {
            moviesWatched++;
            timeElapsed = movies[i].second;
        }
    }
    return moviesWatched;
}
 
int main()
{
    int N;
    cin>>N;
    vector<pair<int, int> > movies;
    int a, b;
    for(int i=0; i<N; i++){
        cin>>a>>b;
        movies.push_back(make_pair(a, b));
    }
    cout << solve(movies, N) << "\n";
    return 0;
}
```
### Sum of Two Values（難度：★★☆）
[題目連結](https://cses.fi/problemset/task/1640)
題目簡述：
給定n、x以及n個正整數，在n個正整數裡是否有兩個數加起來是x，如果有則輸出兩個數的位置，否則輸出IMPOSSILBE

範例測資：
輸入：
4 8
2 7 5 1
輸出：
2 4
利用map能在log n時間完成插入含查詢的特性。對於每一個
```c++=
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, x;
	cin >> n >> x;
	vector<int> values(n);
	for (int i = 0; i < n; i++) { cin >> values[i]; }
	map<int, int> val_to_ind;
	for (int i = 0; i < n; i++) {
		if (val_to_ind.count(x - values[i])) {
			cout << i + 1 << " " << val_to_ind[x - values[i]] << endl;
			return 0;
		}
		val_to_ind[values[i]] = i + 1;
	}
	cout << "IMPOSSIBLE" << endl;
}
```

### Maximum Subarray Sum（難度：★★）
[題目連結](https://cses.fi/problemset/task/1643)
題目簡述：
給定n、和一個長度為n的array。求區間最大和

範例測資：
輸入：
8
-1 3 -2 5 3 -5 2 2
輸出：
9

思路：看到區間最大和就會想要做前綴和。做法是由左往右遍歷，遍歷的同時維護當前最小值相減。以範例來說
前綴和是-1 2 0 5 8 3 5 7
![image](https://hackmd.io/_uploads/HkrIYgmt1l.png)
黃色有點問題
其他都是對的
以此類推

```c++=
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int maxN = 2e5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
 
int N;
ll maxSum, curSum, x[maxN];
 
int main(){
    scanf("%d", &N);
    maxSum = -INF;
    for(int i = 0; i < N; i++){
        scanf("%lld", &x[i]);
        maxSum = max(maxSum, x[i]);
    }
 
    for(int i = 0; i < N; i++){
        curSum += x[i];
        maxSum = max(maxSum, curSum);
        if(curSum < 0)  curSum = 0;
    }
    printf("%lld\n", maxSum);
}
```
### Stick Lengths（難度：★★）
[題目連結](https://cses.fi/problemset/task/1074)
題目簡述：
給定n和一個長度是n的數列。把數列中的每個數+1或是-1都需要1點花費。求將數列全部操作成桐個數字最少需要多少花費。

範例測資：
輸入：
5
2 3 1 5 2
輸出：
5

思路：
既標準又簡單的二分搜題目。自己看code，這個技巧很常用，但比賽不太會用到，因為很簡單，但APCS會考[APCS類似題](https://zerojudge.tw/ShowProblem?problemid=o713)
範例扣是用另外一種方法，算出總和之後用n去減。
```c++=
#include <bits/stdc++.h>
#define lli long long int
#define li long int
#define ld long double
using namespace std;
const lli mod = 1e9 + 7;
 
lli compute_cost(vector<int> arr, int target)
{
	lli cost = 0;
	for (auto ele : arr)
	{
		cost += abs(target - ele);
	}
	return cost;
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	sort(arr.begin(), arr.end());
	int median = arr[n / 2];
	cout << compute_cost(arr, median);
	return 0;
}
```
### Missing Coin Sum（難度：★★★）
[題目連結](https://cses.fi/problemset/task/2183)
題目簡述：
給定一個n和n個數字，求最小的無法用給定的n個數字湊出的數為何?

範例測資：
輸入：
5
2 9 1 2 7
輸出：
6

思路：
先sort然後DP。
```c++=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
const int mxn = 2e5 + 5;
ll dp[mxn];
 
int main(){
    int n; cin >> n;
    vector<ll> x(n+1);
    x[n] = 0;
    for(int i=0;i<n;i++) cin >> x[i];
    sort(x.begin(), x.end());
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        if(dp[i-1] < x[i]) { cout<<dp[i-1]<<endl; return 0;}
        dp[i] = dp[i-1] + x[i];
    }
    cout<<dp[n];
}
```
### Collecting Numbers（難度：★★★）
[題目連結](https://cses.fi/problemset/task/2216)
題目簡述：
給定一個n和n個數字，你可以進行一個操作：由前往後遍歷。求需要遍歷幾次才能按照順序蒐集到所有的數字?

範例測資：
輸入：
5
4 2 1 5 3
輸出：
3
解說：
第一次遍歷：1
第二次遍歷：2 3
第三次遍歷：4 5
思路：
如果數字 X 出現在 X + 1 之前，那麼我們可以在同一輪內收集 X 和 X + 1。否則，如果 X 出現在 X + 1 之後，那麼我們無法將它們放在同一輪內，這時需要額外增加 1 到最終答案中。所以記錄所有數字在數組 arr[] 中的索引位置。接著，對於 1 到 N - 1 之間的每個數字 X，檢查 X + 1 在數組中的位置是位於 X 之前還是之後。如果 X + 1 出現在 X 之前，則將答案增加 1。
```c++=
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n; cin>>n;
    int l = 1;
    int ind[n+1] = {0};
    for (int i = 1; i <= n; i++) {
    	int x; cin>>x;
    	ind[x] = i;
    }
    int c = 1;
    for (int i = 1; i <= n; i++) {
    	if (l > ind[i])
    		c++;
    	l = ind[i];
    }
    cout<<c;
}
```
### Collecting NumbersII（難度：★★★☆）
[題目連結](https://cses.fi/problemset/task/2217)
題目簡述：
給定一個n、m和n個數字，你可以進行一個操作：由前往後遍歷。求需要遍歷幾次才能按照順序蒐集到所有的數字。然後題目會給你m筆操作，每次操作給定兩個位置，交換位置上的數字。輸出交換後的答案。

範例測資：
輸入：
5 3
4 2 1 5 3
2 3
1 5
2 3
輸出：
2
3
4
思路：延續上一題的邏輯。如果交換的兩個數字左邊那個比較大，那就是ans--，否則ans++。(我應該沒寫錯吧XD)
```c++=
#include<bits/stdc++.h>
using namespace std;
#define int long long
 
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    int l = 1;
    int ind[n+2] = {0}, a[n+1] = {0};
    ind[n+1] = n+1;
    for (int i = 1; i <= n; i++) {
		int x; cin>>x;
		ind[x] = i;
		a[i] = x;
    }
    int c = 1;
    for (int i = 1; i <= n; i++) {
		if (l > ind[i])
		c++;
		l = ind[i];
    }
    while(m--) {
		int x,y; cin>>x>>y;
		int r = a[x], s = a[y];
		swap(a[x], a[y]);
		if (ind[r-1] <= ind[r] && ind[r-1] > y) c++;
		if (ind[r-1] > ind[r] && ind[r-1] <= y) c--;
		if (ind[r] <= ind[r+1] && y > ind[r+1]) c++;
		if (ind[r] > ind[r+1] && y <= ind[r+1]) c--;
		ind[r] = y;
		if (ind[s-1] <= ind[s] && ind[s-1] > x) c++;
		if (ind[s-1] > ind[s] && ind[s-1] <= x) c--;
		if (ind[s] <= ind[s+1] && x > ind[s+1]) c++;
		if (ind[s] > ind[s+1] && x <= ind[s+1]) c--;
		ind[s] = x;
		cout<<c<<endl;
    }
}
```
### Collecting NumbersII（難度：★★☆）
[題目連結](https://cses.fi/problemset/task/1141)
題目簡述：
給定一個n和n個數字，問你最長相異子序列。

範例測資：
輸入：
8
1 2 1 3 2 7 4 2
輸出：
5
[類似題](https://zerojudge.tw/ShowProblem?problemid=e289)

解法：
我是用雙指標(這應該是雙指標吧XD)的做法，當multiset裡面沒有重複的數字就右指標++，否則就左指標++。
```c++=
#include<bits/stdc++.h>
using namespace std;
int num[200005];
int main(){
    int n;
    cin>>n;
    for(int i=0; i<n; i++)cin>>num[i];
    int maxm=0, l=0, r=0;
    int wrong=0;
    multiset<int> sgs;
    while(r<n){
        if(wrong==0){
            r++;
            sgs.insert(num[r-1]);
            if(sgs.count(num[r-1])>=2)wrong++;;
 
        }
        else {
            l++;
            sgs.erase(sgs.find(num[l-1]));
            if(sgs.count(num[r-1])<=1)wrong--;
        }
        if(wrong==0 and r<=n)maxm=max(maxm, r-l);
        //cout<<l<<' '<<r<<' '<<wrong<<endl;
    }
    cout<<maxm<<endl;
}
```
### Towers（難度：★★★）
[題目連結](https://cses.fi/problemset/task/1073)
題目簡述：
給定一個n。依序給你n個正方體方塊，需要把他堆成塔，塔底一定要最大。問你在按順序堆塔的前提下，最少可以堆幾個塔。

範例測資：
輸入：
5
3 8 2 1 5
輸出：
2
```c++=
#include<bits/stdc++.h>
using namespace std;
int num[200005];
int main(){
    int n, m;
    cin>>n;
    multiset<int>ts;
    for(int i=0; i<n; i++){
        cin>>m;
        if(ts.upper_bound(m)!=ts.end()){
            ts.erase(ts.upper_bound(m));
        }
        ts.insert(m);
    }
    cout<<ts.size()<<endl;
}
```

### ABC
123