# SCIST 演算法課程 第一次練習賽 題解
## p_A 千年魔法使 (Frieren)
> 命題者：百鬼真香
簽到題ouob
按照題意輸出即可
~~芙莉蓮真的超好看，比完賽請務必光顧~~
:::spoiler code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
cout << "autoputto " << n << " no mahoo" << endl;
return 0;
}
```
:::
## p_B 硬幣數量 (Coins)
> 命題者：陳秉宏
數學題
第 $x$ 天到第 $y$ 天得到的硬幣數量是 $\frac{(x+y) \times (y-x+1)}{2}$ 。
因為 $x, y\leq 10^9$ ，答案的極值會超過 int 的範圍，所以要記得開 long long。
~~如果很執著於迴圈的話，用一些神奇的優化技巧還是會AC的。~~
:::spoiler AC code
```cpp=
#include<iostream>
using namespace std;
int main()
{
long long x, y;
cin >> x >> y;
long long ans=(x+y)*(y-x+1)/2;
cout << ans << endl;
return 0;
}
```
:::
## p_C 環島之旅 (Island Tour)
> 命題者：temmie
可以發現**東西向與南北向的結果彼此獨立**，因此我們可以分開討論。
若只看東西向，往東走 $x$ 單位的距離，則需要往西走 $x$ 單位才能回到原點，而南北向同理。
最終得出結論，若 $E = W$ 且 $S = N$，則可以回到原點。
:::spoiler AC code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int e, s, w, n;
int main(){
// input
cin >> e >> s >> w >> n;
// output
if (e==w && s==n){
cout << "Yes\n";
}else{
cout << "No\n";
}
return 0;
}
```
:::
:::spoiler 補充
這種東西向與南北向互相獨立的概念其實在往後複雜的演算法題目中相當常見，通常是二維平面上的[曼哈頓距離](https://zh.wikipedia.org/zh-tw/%E6%9B%BC%E5%93%88%E9%A0%93%E8%B7%9D%E9%9B%A2)之類的問題，各位可以對這個概念先有個印象。
:::
:::spoiler bonus
1. 假如 temmie **要修改不大於兩個路程**使他的旅行是成功的，請問他「修改後與原本路程長度的差」的最小總和是多少。
2. 給 $q$ 個查詢，每次查詢會指定其中一個方位 $dir$ 以及距離 $dis$，判斷是否為成功的。
- $1 \le q \le 10^5$
- $dir \in \{E, S, W, N\}$
- $1 \le dis \le 10^9$
:::
## p_D 買超級多的衣服 (Crazy buyer)
> 命題者：小麥
題目的意思要連續的合剛好為 $m$，之後再看一下測資的範圍 $n \leq 10^4$，那在想一下如果要跑一次所有的區間要多少時間，剛好是 $10^8$，在 $10^9$ 時間之內。時間複雜度 $O(n^2)$。
那就可以**直接跑一次全部的區間**，並且只要符合 $m$ 就把答案 $+1$，並且一樣可以發現如只要**目前的總合 $>m$**，那麼就不用在繼續跑下去了。
以上就可以拿到滿分，程式可以參考++解答程式碼一++。
這題就算都不會也可以拿範測的 $20$ 分，但有很多人沒有拿QQ。
::: spoiler 補充
但是只要今天我的 $n$ 改為 $\leq 10^5$，就會發現這個時候不能去枚舉全部的區間。
對於上敘的問題我們可以使用前綴合的技巧，先把前綴合建起來，之後就可以從掃一次前綴合，每一次掃描的時候使用二分搜去查看有沒有減掉目前的前綴合會剛好 $=m$的，有的話就 $+1$，可以參考<u>解答程式碼二</u>。時間複雜度 $O(nlogn)$
如果 $n$ 在大一點到 $n \leq 1e9$，這個時候連上敘的解法也不行，因為上面的解法有使用到二分搜，那這個時候換一種想法，如果我使用一個變數從陣列的頭開始加總，會發現越來越大，而如果總合在從頭開始減會越來越小，這其實就是單調性，那就可以使用一個叫滑動窗口的技巧，可以參考<u>解答程式碼三</u>。時間複雜度 $O(n)$。
那如果題目再機車一點，價格有負的，那這樣上面的兩個解法就都不行了（假設 $n \leq 10^5$），這個時候就可以使用一個變數像前綴合那樣去紀錄目前的總合，並且把總合當作索引值記錄起來，而每一次都要使用目前的總合去減掉 $m$，並且在紀錄的資料結構裡面查詢先前是否有過一樣的總合，有的話答案就加一，可以參考<u>解答程式碼四</u>。時間複雜度因為有使用到使用 map 等的資料結構來裝，這樣要 $O(nlogn)$。
:::
:::spoiler 解答程式碼一
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n;
int m;
int arr[10000 + 5];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> arr[i];
int ans = 0;
for (int i = 0; i < n; i++)
{
long long sum = arr[i];
for (int j = i + 1; j < n; j++)
{
if (sum >= m) break;
sum += arr[j];
}
if (sum == m)
ans++;
}
cout << ans << '\n';
return 0;
}
```
:::
:::spoiler 解答程式碼二
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
vector<int> arr;
vector<int> prefix_sum;
void solve()
{
cin >> n >> m;
arr.resize(n);
prefix_sum.resize(n + 1);
for (int i = 0; i < n; i++) cin >> arr[i];
for (int i = 1; i <= n; i++) prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1];
int ans = 0;
for (int i = 0; i < n; i++)
{
int l = i + 1, r = n + 1;
while (l < r)
{
int mid = (l + r) >> 1;
if (prefix_sum[mid] - prefix_sum[i] < m) l = mid + 1;
else r = mid;
}
if (prefix_sum[l] - prefix_sum[i] == m) ans++;
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
```
:::
:::spoiler 解答程式碼三
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, m;
vector<int> arr;
void solve()
{
cin >> n >> m;
arr.resize(n);
for (int i = 0; i < n; i++) cin >> arr[i];
if (m == 0)
{
cout << '0' << '\n';
return;
}
int ans = 0;
int l = 0, r = 0;
int sum = arr[r];
while (r < n)
{
if (sum == m)
{
ans++;
r++;
sum += arr[r];
}
while (sum < m)
{
r++;
sum += arr[r];
}
while (sum > m)
{
sum -= arr[l];
l++;
}
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
```
:::
:::spoiler 解答程式碼四
```cpp=
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio; cin.tie(0); cout.tie(0)
#define debug(container) for (auto i : container) cerr << i << ' '; cerr << '\n';
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, m;
vector<int> arr;
map<int, int> ma;
void solve()
{
cin >> n >> m;
arr.resize(n);
for (int i = 0; i < n; i++) cin >> arr[i];
int current_sum = 0;
int ans = 0;
ma[0] = 1;
for (int i = 0; i < n; i++)
{
current_sum += arr[i];
ans += ma[current_sum - m];
ma[current_sum]++;
}
cout << ans << '\n';
}
int main()
{
fastio;
solve();
return 0;
}
```
:::
## p_E Eason 的計算機 (Magic Calculator)
> 命題者：Eason
~~首先要瞭解題目的意思，然後直接實作即可~~
這題分為三個子任務
- 子任務 1：$q \leq 10$ （10 分）
- 子任務 2：$op \in \{$"$RS$", "$Rp$"$\}$（10 分）
- 子任務 3：題目範圍（80 分）
然後觀察一下 $q$ 的範圍是 $1 \leq q \leq 100$
所以在最壞的情況下（$q=100$ 且所有操作都是乘以 $10$），$num$ 的數值會來到 $10^{100}$，顯然用 ```long long``` 也存不下，如果你是用 ```long long``` 直接實作的話就只能拿到前面的 20 分，滿分解需要用陣列去模擬 $num$
note: 用字串實作也可以
在陣列實作中，先令 $arr_0$ 為 $1$，利用變數（$ptr$）去紀錄當前的個位數字在陣列中的哪一個位置，接下來面對以下操作：
- $LS$：將 $ptr$ 加 $1$，並讓 $arr_{ptr}$ 為 $0$
- $RS$：將 $ptr$ 減 $1$
- $Rp x$：將 $arr_{ptr}$ 設為 $x$
同時實作上需要注意 $0 \times 10 = 0$，還有 $ptr=0$ 時的細節。最後印出 $arr_0$ ~ $arr_{ptr}$ 即為答案
:::spoiler AC code
```cpp=
#include<iostream>
using namespace std;
int arr[105];
int main(){
int q;
cin >> q;
arr[0] = 1;
int ptr = 0;
while (q--){
string op;
cin >> op;
if (op == "RS"){
if (ptr == 0) arr[ptr] = 0;
else ptr--;
}
else if (op == "LS"){
if (ptr != 0 || arr[ptr] != 0){
arr[++ptr] = 0;
}
}
else if (op == "Rp"){
int x;
cin >> x;
arr[ptr] = x;
}
}
for (int i = 0; i <= ptr; i++) cout << arr[i];
cout << '\n';
return 0;
}
```
:::
:::spoiler 補充
出這題的目的是想讓大家認識左移、右移的概念，即題目中的 LS (Left Shift)、RS (Right Shift)，兩者的概念通常出現在二進位。題目中的<mark>左移是將整個數字往左移 1 位，最右方的空位補 0</mark>。在十進位中左移就類似乘以 10 的概念，而在二進位中就是乘以 2 的概念。
- 十進位：
| 左移位數 | 實際數值 |
| :-----: | :----: |
| $0$ | $1$ |
| $1$ | $10$ |
| $2$ | $100$ |
| $3$ | $1000$ |
| $n$ | $10^n$ |
- 二進位
| 左移位數 | 二進位數值 | 二進位轉十進位數值 |
| :----: | :-------: | :------: |
| $0$ | $1_2$ | $1_{10}$ |
| $1$ | $10_2$ | $2_{10}$ |
| $2$ | $100_2$ | $4_{10}$ |
| $3$ | $1000_2$ | $8_{10}$ |
| $4$ | $10000_2$ | $16_{10}$ |
| $n$ | $(10^{n})_{2}$ | $(2^n)_{10}$ |
可以發現<mark>左移 $n$ 位對於二進位來說就是乘以 $2^n$ 的概念</mark>，相對來說，右移就是將最右邊那一位去掉，數學意義就是除以 $2$ 並取下高斯。而左移右移在 C++ 中也是能實現的（見下方的 code）。
<font color=red>注意：本題為了讓大家容易理解才利用十進位來解釋左移右移，實際應用還是以二進位為主。</font>
```cpp=
// >> 是右移運算子，<< 是左移運算子
int a = 10;
cout << (a << 3) << ' '; // a 左移 3 位，意同 a * 8
cout << (a >> 2) << '\n'; // a 右移 2 位，意同 a / 4
// output: 80 2
```
:::
:::spoiler 延伸
這題的想法是出自大數運算，當運算的數字超出 ```long long``` 能容納的範圍後，就需要使用這個技巧（~~或者是用 python~~），簡單來說就是用陣列去實作 ```+-*/``` 或是更進階的運算，實作過程就跟直式運算差不多，可以先思考一下平常是怎麼用直式去算乘法或加法，再來實作看看。教學的話篇幅可能會過長，這邊直接附上別人的教學文
大數運算教學文：https://hackmd.io/@CLKO/r1KtmuMdf?type=view
大數運算練習題：https://tioj.ck.tp.edu.tw/problems/1507
:::
## p_F DP
> 命題者：高睿(sakinu)
這題分為四個子任務
- 子任務 1：$n \leq 10、a_i \leq 10^3$ ( 15分 )
- 子任務 2：$n \leq 10^2、a_i \leq 10^6$ ( 25分 )
- 子任務 3：$x \neq \%$ ( 25分 )
- 子任務 4：題目範圍 ( 35分 )
子題一：可直接枚舉並計算最佳答案，對一次詢問枚舉 abc 並計算答案的複雜度為 $n^3$，複雜度為$O(qn^3)$
子題二：用子題一的複雜度會TLE，但我們可以先算出所有詢問的組合 $(5 \times 4)=20$ 種，接下來對於每個查詢即可 $O(1)$ 回答，複雜度 $O(20 \times n^3+q)$
子題三是子題四但沒想到 $x=\%$ 的狀況
子題四：觀察到我們想要計算結果盡量的大，所以對於 $a+b$ 與 $a*b$ 的運算，$a$ 和 $b$ 一定都是選數字最大的數，而對於 $a-b$ 與 $a/b$ 的運算， $a$ 都要最大，而 $b$ 都要最小。最後對於 $a\%b$ 的運算，則可以發現 $a$ 選第二大的數，$b$ 選最大的數是最好的。
:::spoiler AC code
```cpp=
#include<iostream>
using namespace std;
signed main(){
int n;
cin >> n;
int mx1=0,mx1_idx;
int mx2=0,mx2_idx;
int mi=2e9,mi_idx;
for(int i=1;i<=n;i++){
int x;
cin >> x;
if(x<mi){
mi=x;
mi_idx=i;
}
if(x>mx2){
mx2=x;
mx2_idx=i;
if(mx2>mx1){
swap(mx1,mx2);
swap(mx1_idx,mx2_idx);
}
}
}
int q;
cin >> q;
while(q--){
char x,y;
cin >> x >> y;
int a,b,c;
if(y=='+'||y=='*') c=mx1_idx;
else c=mi_idx;
if(x=='%') a=mx2_idx,b=mx1_idx;
else if(x=='+'||x=='*') a=b=mx1_idx;
else a=mx1_idx,b=mi_idx;
cout << a << " " << b << " " << c << "\n";
}
}
```
:::
:::spoiler 補充
這題主要是想要讓大家練習觀察能力，透過自己想幾種case後，就會發現其實只需要注意最大、第二大、以及最小的數就好了。
:::
Sign in with Wallet
Connect another wallet