# Ten Point Round #8 (Div. 2) 題解
希望大家喜歡這場比賽 OuO
## pA 採買任務
**Prepared by Colten**
CBD 身上會有 $c$ 元，買菜總共會花掉 $ae + bf$ 元。
那麼當 $c - ( ae + bd) < 0$ 時，代表 CBD 身上的錢不足以採買所需的蔬菜，輸出 $-1$。
反之，如果有剩下的錢，那麼 CBD 能買的冰淇淋數量為 $\frac{c-(ae+bd)}{d}$。
:::spoiler 參考解答 (C++)
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int a,b,c,d;
cin >> a >> b >> c >> d;
int e,f;
cin >> e >> f;
if( a * e + b * f > c )
{
cout << -1 << "\n";
exit(0);
}
else
{
int l = c - ( a * e + b * f );
cout << l / d << "\n";
}
return 0;
}
```
:::
## pB 重複的話語
**Prepared by Colten**
讓大家練習迴圈使用的題目 ><
:::spoiler 參考解答 (C++)
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int q;
string s;
cin >> s;
cin >> q;
while(q--)
{
cout << s << "\n";
}
return 0;
}
```
:::
## pC Last Christmas
**Prepared by Colten**
這題我們可以一邊輸入一邊紀錄目前的最大值，當發現新輸入的數字比紀錄的最大值大時，則更新最大值。
:::spoiler 參考解答 (C++)
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int mx = -1e9;
while(n--)
{
int input;
cin >> input;
mx = max(mx,input);
}
cout << mx << "\n";
return 0;
}
```
:::
## pD 公園調查
**Prepared by Colten**
這題主要會給一個區間 $h_1,h_2$，會在第 $h_1$ 的時間進入公園，第 $h_2$ 的時間離開公園。
那麼我們可以用兩個陣列分別紀錄在第 $i$ 時間進入的人數，以及離開的人數。
並用兩個變數 $now,ans$，分別記錄第 $i$ 小時的人數，以及更新人數最大值。
**那麼在第 $i$ 小時的人數為 $now + enter[i] - leave[i]$**
:::spoiler 參考解答 (C++)
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
int enter[10005],leave[10005];
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int q;
int n;
cin >> n;
for(int i=0;i<n;i++)
{
int h1,h2;
cin >> h1 >> h2;
enter[h1]++;
leave[h2]++;
}
int now = 0,ans = 0;
for(int i=0;i<=10000;i++)
{
now = now + enter[i] - leave[i];
ans = max(ans,now);
}
cout << ans << "\n";
return 0;
}
```
:::
## pE 位數刪除
**Prepared by Colten**
這題其實我們可以從子任務來獲取一些提示。
既然這題沒有限制操作的次數，那麼我們可以知道，只要這兩個數字的所有位數之中，只要有其中一個位數的數字兩邊數字中都有出現，那麼答案必為 $Yes$。
:::spoiler 參考解答 (C++)
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
string a,b;
cin >> a >> b;
bool check = false;
for(int i=0;i<a.size();i++)
{
for(int k=0;k<b.size();k++)
{
if( a[i] == b[k] )
{
check = true;
break;
}
}
if( check == true ) break;
}
if( check == true )
{
cout << "Yes\n";
}
else
{
cout << "No\n";
}
return 0;
}
```
:::
## pF Presentation Error
**Prepared by Colten**
這題其實本來是 1 月實體賽要用的題目，但放上 CMS 出了點問題，於是就拿掉了。
- 輸出格式錯誤的狀況，我們可以知道，只要我們將兩個字串所有的空白字元都忽略掉，組合出兩個新的字串，假如新組合的字串兩兩相同但是不忽略空白字元的字串兩兩不相同，那麼這個狀況則是 Presentation Error 的情況。
- 那麼另一個狀況為，兩個字串組合後兩兩不相同，且不忽略空白字元的字串也兩兩不相同，那麼這麼狀況極為 Wrong Answer。
- 假設一開始的字串即兩兩相等，那麼這個狀況則為 Accepted。
## pG 鬼滅之刀無限湯瑪士
**Prepared by Troy (大灣高中首次做事XD)**
這題我們觀察發現，當這個數列被操作 $n$ 次時，那麼這個數列又會變回跟原本一樣的數列。
我們可以發現，當 $a[i-1] > a[i]$ 這個情況出現 $2$ 次以上，那麼這個數列不可能操作成非嚴格遞增的數列。
**有個部分要注意，當假設上面這個情況出現過剛好 $1$ 次，那麼要順便檢查 $a[0] < a[n-1]$ 這個情況，假如成立，那麼這組數列也無法藉由操作變成非嚴格遞增的數列。**
像是這組測資就是上面第二個所說的情況
```
1
4
1 2 1 2
```
**(假如序列的所有數字都一樣，那麼以上兩種情況都不會出現)**
:::spoiler 參考解答 (C++)
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int q;
cin >> q;
while(q--)
{
int n;
cin >> n;
vector <int> a(n);
int check = 0,index = 0,mn = 3e9;
for(int i=0;i<n;i++)
{
cin >> a[i];
if( i != 0 )
{
if( a[i] < a[i-1] )
{
check++;
}
}
if( check != 0 && a[i] < mn )
{
index = i;
mn = a[i];
}
}
if( check != 0 && a[0] < a[n-1] )
{
check++;
}
if( check >= 2 )
{
cout << "No Nut\n";
}
else
{
cout << "Oh Yes " << index << "\n";
}
}
return 0;
}
```
:::
## pH 名次數列
**Prepared by Colten**
這題其實是純離散化實作，不太了解離散化是什麼的人可以去網路上找一下 ><
離散化的實作有數種方式，二分搜或 set 搭配 map 都是常見的。
我們這邊提供的做法是 set + map 的作法。
我們先將元素都加入 set 裡面，再把 set 裡面的元素拿出 **(set 裡的元素預設依序由小到大)**，並多利用一個變數 $rk$ 紀錄名次，並把 $mp[拿出的元素]$ $=$ $rk$。
接著將依序輸出 $mp[a[i]]$ 就是 $a[i]$ 轉換為名次的結果。
:::spoiler 參考解答 (C++)
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int q;
cin >> q;
while(q--)
{
memset(a,0,sizeof a);
int n;
cin >> n;
set <int> s;
map <int,int> mp;
for(int i=0;i<n;i++)
{
cin >> a[i];
s.insert(a[i]);
}
int rk = 1;
for( auto i : s )
{
mp[i] = rk;
rk++;
}
for(int i=0;i<n;i++)
{
cout << mp[a[i]];
if( i != n - 1 ) cout << " ";
}
cout << "\n";
}
return 0;
}
```
:::
## pI 隊友的選擇
**Prepared by Colten**
我們可以將這題分成三個部分來討論。
我們定義 $dp[i][k]$ 為，在第 $i$ 直行時，選擇第 $k$ 排的人時，能達到的最大值。
**如果這次要選擇第 $k$ 排的人，那麼我們上次的選擇就不能是 $k$**
- 當 $k = 1$ 時，$dp[i][1] = max(dp[i-1][2],dp[i-1][3]) + a[i][1]$
- 當 $k = 2$ 時，$dp[i][2] = max(dp[i-1][1],dp[i-1][3]) + a[i][2]$
- 當 $k = 3$ 時，$dp[i][3] = max(dp[i-1][1],dp[i-1][2]) + a[i][3]$
:::spoiler 參考解答 (C++)
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[100005][4],a[100005][4];
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i=1;i<=3;i++)
{
for(int k=1;k<=n;k++)
{
cin >> a[k][i];
}
}
dp[1][1] = a[1][1];
dp[1][2] = a[1][2];
dp[1][3] = a[1][3];
for(int i=2;i<=n;i++)
{
dp[i][1] = max(dp[i-1][2],dp[i-1][3]) + a[i][1];
dp[i][2] = max(dp[i-1][1],dp[i-1][3]) + a[i][2];
dp[i][3] = max(dp[i-1][1],dp[i-1][2]) + a[i][3];
}
cout << max({dp[n][1],dp[n][2],dp[n][3]}) << "\n";
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet