---
# System prepended metadata

title: 'Ten Point Round #8 (Div. 2) 題解'

---

# 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;	
} 
```
:::





