# 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)
題目簡述：
輸入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的所有解
下圖是會互相攻擊的狀況
```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
解釋：
上圖是一種可能的走法。(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]才停止。
```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
如上圖（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
解釋：
第一位客人和第二位客人不重疊，答案是2。
作法
先創造一個陣列，當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
黃色有點問題
其他都是對的
以此類推
```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
Sign in with Wallet
Connect another wallet