# 2024/8/31 APCS 第八場模擬賽 題解
## 遊戲 (Game)
> 出題者：TLY
> 難度：p1
> 考點：排序、比較運算
### Statement
L 最近在玩一款遊戲，這個遊戲裡有很多美男（這不是重點，等下這個好像是重點欸），這些美男分成三個品級 絕品、妙品、普通，然後他們都有屬於自己的等級和星級。
今天，L 發現遊戲內部的排序功能壞掉了，所以她想請你幫忙寫個程式來排序這些人物的戰力，排序順序如下：
- 絕品 `>` 妙品 `>` 普通 ( `>`是大於 )
- 絕品 → 2
- 妙品 → 1
- 普通 → 0
- 星級越多戰力越強
- 等級越高戰力越強
- 編號大的先輸出
註：輸入在第幾行，編號就是多少
### Input
一個正整數 $N$，代表美男的數量。
接下來 $N$ 行，每行三個正整數 $T, R, S$，分別代表品級、等級和星級。
範圍如下：
$3 \le N \le 10$
$0 \le T \le 2$
$1 \le R \le 500$
$1 \le S \le 100$
### Output
共輸出 $N$ 行，每行輸出四個整數，依序分別是編號、品級、等級和星級。
### Testcase
- Input 1
```
3
2 50 3
1 55 5
2 30 7
```
- Output 1
```
3 2 30 7
1 2 50 3
2 1 55 5
```
### Subtask
- Subtask 1 (30%) - $N = 3$
- Subtask 2 (70%) - 無其他限制
### Solution
使用自定義排序比較多個元素，可以使用內建排序函式，也可以每次從序列中挑出最大的那個，然後一一取出就會是排序狀態。
### Code
- Subtask 1
```cpp
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
using namespace std;
int main() {
fastio;
ll N; cin >> N;
ll T1, R1, S1, A1; cin >> T1 >> R1 >> S1, A1 = T1 * 500000000 + S1 * 50000 + R1 * 500 + 1;
ll T2, R2, S2, A2; cin >> T2 >> R2 >> S2, A2 = T2 * 500000000 + S2 * 50000 + R2 * 500 + 2;
ll T3, R3, S3, A3; cin >> T3 >> R3 >> S3, A3 = T3 * 500000000 + S3 * 50000 + R3 * 500 + 3;
if (A1 > A2 && A1 > A3) cout << 1 << " " << T1 << " " << R1 << " " << S1 << "\n", (A2 > A3 ? cout << 2 << " " << T2 << " " << R2 << " " << S2 << "\n" << 3 << " " << T3 << " " << R3 << " " << S3 << "\n" : cout << 3 << " " << T3 << " " << R3 << " " << S3 << "\n" << 2 << " " << T2 << " " << R2 << " " << S2 << "\n");
else if (A2 > A1 && A2 > A3) cout << 2 << " " << T2 << " " << R2 << " " << S2 << "\n", (A1 > A3 ? cout << 1 << " " << T1 << " " << R1 << " " << S1 << "\n" << 3 << " " << T3 << " " << R3 << " " << S3 << "\n" : cout << 3 << " " << T3 << " " << R3 << " " << S3 << "\n" << 1 << " " << T1 << " " << R1 << " " << S1 << "\n");
else if (A3 > A1 && A3 > A2) cout << 3 << " " << T3 << " " << R3 << " " << S3 << "\n", (A1 > A2 ? cout << 1 << " " << T1 << " " << R1 << " " << S1 << "\n" << 2 << " " << T2 << " " << R2 << " " << S2 << "\n" : cout << 2 << " " << T2 << " " << R2 << " " << S2 << "\n" << 1 << " " << T1 << " " << R1 << " " << S1 << "\n");
return 0;
}
```
- Subtask 2
```cpp
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
using namespace std;
int main() {
fastio;
ll N; cin >> N;
vector < tuple < ll, ll, ll, ll > > p(N + 1);
for (ll i = 1; i <= N; i++) cin >> get < 0 > (p[i]) >> get < 2 > (p[i]) >> get < 1 > (p[i]), get < 3 > (p[i]) = i;
sort(p.begin() + 1, p.end(), greater < tuple < ll, ll, ll, ll > >());
for (ll i = 1; i <= N; i++) cout << get < 3 > (p[i]) << " " << get < 0 > (p[i]) << " " << get < 2 > (p[i]) << " " << get < 1 > (p[i]) << "\n";
return 0;
}
```
## 天旋地轉 (Spinning)
> 出題者：小律
> 難度：p2
> 考點：迴圈、二維陣列
### Statement
因為小律的狗狗太可愛被大律抓走，所以為了拯救他的狗狗必須過一個大關卡才能到大律的城堡。
關卡的規則如下：
地圖是一個 $N \times N$ 的正方形，一開始挑戰者會在左上角的地方按照由左到右，由上而下的路徑移動（每次移動時地圖會旋轉 90 度，挑戰者必須在每次移動時加總自己腳下的數字 $a_i$，最後走完 $N^2-1$ 步的時候輸入正確答案就能過關。
### Input
第一行輸入一正整數 $N$ （$2 \leq N \leq 1000$）代表地圖大小為 $N * N$
第二行輸入 $N^2 - 1$ 個數字 $k_i$：
$0$：代表第 $i$ 步（$1 \leq i \leq N^2-1$）地圖向左轉
$1$：代表第 $i$ 步（$1 \leq i \leq N^2-1$）地圖向右轉
接著輸入地圖上的所有數字 $a_{i,j}$（$1 \leq i, j\leq N$）（$1 \leq a_{i,j}\leq 100$）
### Output
輸出走完地圖（$N^2-1$步）時加總的數字。
### Input Format
$N$
$k_1 \space k_2\space \dots \ \space k_{n^2-1}$
$a_{（1,1）} \space a_{（1,2）} \space \dots \space a_{（1,n）}$
$a_{（2,1）} \space a_{（2,2）} \space \dots \space a_{（2,n）}$
$.$
$.$
$.$
$a_{（n,1）} \space a_{（n,2）} \space \dots \space a_{（n,n）}$
### Output Format
$ans$
### Testcase
- Input 1
```
3
1 1 1 1 1 1 1 1
1 2 3
4 5 6
7 8 9
```
- Output 1
```
37
```
- Input 2
```
4
1 0 1 1 0 1 1 1 1 0 1 1 1 1 1
1 4 2 4
4 2 4 1
1 3 3 3
4 5 5 5
```
- Output 2
```
45
```
### Subtask
- Subtask 1 (50%) - $k_i$ 皆為 $1$
- Subtask 2 (50%) - 無其他限制
### Note
範例一示意圖：
以此類推路途上經過了：$1, 4, 7, 2, 5, 2, 3, 4, 9$，加總為 $37$
### Solution
按照題意實作即可(可將旋轉後的四種可能先列出來)
### Code
- Subtask 1
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n, arr[1005][1005], k[1000005] = {0}, cnt = 0, ans = 0;
int arr2[1005][1005], arr3[1005][1005], arr4[1005][1005];
vector <int> v(1000005);
signed main() {
cin >> n;
for(int i=2; i<=n*n; i++) cin >> k[i];
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cin >> arr[i][j];
v[++cnt] = arr[i][j];
}
}
cnt = 0;
for(int i=n; i>=1; i--){
for(int j=1; j<=n; j++){
arr2[j][i] = v[++cnt];
}
}
cnt = 0;
for(int i=n; i>=1; i--){
for(int j=n; j>=1; j--){
arr3[i][j] = v[++cnt];
}
}
cnt = 0;
for(int i=1; i<=n; i++){
for(int j=n; j>=1; j--){
arr4[j][i] = v[++cnt];
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(((i-1) * n + j) % 4 == 0) ans += arr4[i][j];
else if(((i-1) * n + j) % 4 == 1) ans += arr[i][j];
else if(((i-1) * n + j) % 4 == 2) ans += arr2[i][j];
else if(((i-1) * n + j) % 4 == 3) ans += arr3[i][j];
}
}
cout << ans;
return 0;
}
```
- Subtask 2
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n, arr[1005][1005], k[1000005] = {0}, cnt = 0, ans = 0, step = 0, now = 0;
int arr2[1005][1005], arr3[1005][1005], arr4[1005][1005];
vector <int> v(1000005);
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i=2; i<=n*n; i++){
cin >> k[i];
if(k[i] == 0) k[i] = -1;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cin >> arr[i][j];
v[++cnt] = arr[i][j];
}
}
cnt = 0;
for(int i=n; i>=1; i--){
for(int j=1; j<=n; j++){
arr2[j][i] = v[++cnt];
}
}
cnt = 0;
for(int i=n; i>=1; i--){
for(int j=n; j>=1; j--){
arr3[i][j] = v[++cnt];
}
}
cnt = 0;
for(int i=1; i<=n; i++){
for(int j=n; j>=1; j--){
arr4[j][i] = v[++cnt];
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
int it = n*(i-1) + j;
step = (step + k[it] + 4) % 4;
if(step == 0) ans += arr[i][j];
if(step == 1) ans += arr2[i][j];
if(step == 2) ans += arr3[i][j];
if(step == 3) ans += arr4[i][j];
}
}
cout << ans;
return 0;
}
```
## 澳洲來的客人 (Customers From Australia)
> 出題者：小麥
> 難度：p3
> 考點：遞迴、二分搜
### Statement
有一天小麥打算在澳洲開一間飯店，在開店之前小麥就有聽說這裡的客人有一個非常特別的習慣。
飯店的第一層樓會按照下方的規則入住：
- 第一位客人一定會住在 $1$ 號房
- 第二位客人開始只能住在離有住人的房間最遠的房間
- 所有客人開始離最近的其它客人的距離一定要至少要 $m$ 間
- 如果入住的人剛好在中間，則那位客人會住在偏左的房間
小麥對當地的做了仔細的調查，因此保證入住的人不會超過 $n$ 個客人，請問依照此規則第一層最少需要準備幾個房間才夠。
### Input
第一行包含 $2$ 個正整數 $n$、$m$。
- $n$ 代表多會有幾個客人入住
- $m$ 每個客人想要保持的最小距離
## 題目測資範圍
- $2 \leq n \leq 2 \times 10^5$
- $1 \leq m \leq 2 \times 10^5$
### Output
輸出最少需要幾個房間才夠所有的客人入住。
### Testcase
- Input 1
```
7 2
```
- Output 1
```
23
```
- Input 2
```
5 1
```
- Output 2
```
9
```
### Subtask
| 分數 | 條件限制 | 附加條件 |
|------|:---------------------------------:|:--------:|
| 25% | $n,m \leq 10^3$ | |
| 100% | 題目測資範圍 | |
### Solution
#### Subtask 1
這題要分成兩個部份，第一個部份是要怎麼樣知道一定房間數量可以住多少人（例如準備 $100$ 個房間，間隔為 $2$），而這個部分可以使用遞迴來模擬即可。
想像一下在最一開始的時候往左右兩邊塞人，之後分成一半可以發現跟一開始的問題相同，處理的時候注意一下最一開始是兩個人這個細節就行了。第二個部份是要怎麼樣知道需要準備多少房間，如果這裡你選擇枚舉可以拿到 $25$ 分。
#### Subtask 2
這個時候就可以發現到越多房間可以住的人越多，所以找到剛好對應的房間數量即可，這裡使用二分搜就可以拿到滿分。
### Code
```cpp=
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio; cin.tie(0); cout.tie(0);
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef vector<v2i> v3i;
typedef vector<string> vs;
typedef vector<vs> v2s;
typedef vector<pii> vp;
typedef vector<vp> v2p;
typedef vector<bool> vb;
typedef vector<vb> v2b;
int n, m;
int f(int l, int r) {
int mid = (l + r) / 2;
if (r - mid - 1 < m) {
return 0;
}
if (mid - l - 1 < m) {
return 0;
}
return 1 + f(l, mid) + f(mid, r);
}
bool check(int count) {
int sum;
if (count - 2 < m) {
sum = 1;
}
else if (count - 2 == m) {
sum = 2;
}
else {
sum = f(0, count - 1) + 2;
}
return sum >= n;
}
int binary_search() {
int l = 1, r = n * ((m * 2) + 1);
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
return l;
}
void solve() {
cin >> n >> m;
cout << (binary_search()) << '\n';
}
signed main() {
fastio;
solve();
return 0;
}
```
## 滑雪道 II (Ski Runs II)
> 出題者：rickytsung
> 難度：p4
> 考點：分治
### Statement
今天 Chung 教授決定繼續擴大他的滑雪場，又有一座山有 $n$ 個山峰，編號為 $1 \sim n$，第 $i$ 個山峰高度為 $h_i$（$1 \leq i \leq n$），而且每個山峰的高度都不一樣 （如果 $i \neq j$ 則 $h_i \neq h_j$），這次開發的是挑戰型路線，和上次不同的是 Chung 不需要考慮滑雪道的高度是否滿足單調的條件，可以一下是下坡一下是上坡，不過因為 Chung 也是物理大師，他發現如果一個滑雪道路線是在山峰 $l$ 到 $r$ 之間，但中間如果有山峰比兩端 (也就是 $h_l$ 和 $h_r$ ) 都還高那一定會滑不上去，所以 Chung 想請寫個程式計算有幾種路線滿足中間沒有比兩端還高的山峰。更明確的說，請你算整數數對 $(l,r)\ (1\leq l< r \leq n)$ 能使得對於所有 $j$ 滿足 $l < j < r$ ，$h_j \leq max(h_l, h_r)$ 都成立的數量。
當 $n = 6, h = (9,3,6,1,7,10)$ 時如下圖 :
如果在山脈 1 和 4 之間蓋滑雪道，兩端比較高的那端高度為 9，夾在中間的山脈 2 和 3 沒有比 9 來的高，所以是滿足條件的。
如果在山脈 2 和 4 之間蓋滑雪道，兩端比較高的那端高度為 3，夾在中間的山脈 3 比 3 來的更高，所以是不滿足條件的。
### Input
第一行有一個正整數 $n$，代表山峰的數量。
接下來有一行 $n$ 個整數中間以空白隔開，代表山峰的高度，第 $i\ (1 \leq i \leq n)$ 個數代表 $a_i$。
$1 \leq n \leq 2 \times 10^5$
$1 \le h_i \le 10^9\ (1 \leq i \leq n)$
$i \neq j$ 則 $h_i \neq h_j$
### Output
輸出一個數代表答案，請注意答案有可能超過 $2^{32}$ 但保證不會超過 $2^{60}$。
### Sample
- Input 1
```
4
1 3 2 5
```
- Output 1
```
5
```
其中 $(1,2)$、$(1,4)$、$(2,3)$、$(2,4)$、$(3,4)$ 符合條件。
- Input 2
```
6
9 3 6 1 7 10
```
- Output 2
```
14
```
### Subtask
- Subtask 1 (20%) - $n \leq 80$
- Subtask 2 (30%) - $n \leq 1500$
- Subtask 3 (50%) - 如題
### Solution
### Subtask 1
枚舉 $l, r$，加上 $O(n)$ 判斷 $[l,r]$ 是否為一組解，總時間複雜度 $O(n^3)$
### Subtask 2
觀察我們可以枚舉每個點當最大值那邊，接著往另一邊(左 or 右)拿直到遇到比他更大的，直接實作是 $O(n^2)$。
### Subtask 3
利用分治，定義 divide(l, r) 代表維護區間 [l,r] 的解，可以分成divide(l,mid) 和 divide(mid+1,r) 加上所有包含 mid, mid+1 這兩點的區間，我們需要計算的是這個地方，先假設剛好分開的兩邊高度都是從 mid 往外遞增，那解就會是枚舉目前最高的點，去另一邊拿所有比他小的點，這個數量就是以該點為高點的答案數量，接著把最高點移除，可以用雙指針逐漸往內移。
如果不是單調的話，可以每次只存比前面更大的數、也就是一個單調遞增序列，高點在這上面找，因為前面的定義，所有低點不需要被枚舉，最後就可以照前面方法做，時間和空間複雜度都是 $O(n\ log\ n)$。
另解 (已超綱) : 請參考 Subtask 2 的 code，中間有一段 $O(r-l) = O(n)$ 找該區間最大值，固態區間最大值可以使用線段樹/稀疏表等維護，時間複雜度同官解。
另解 2: $O(n)$ 單調隊列 by 橘子
### Code
- Subtask 1
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
long long int ans = 0;
cin >> n;
int h[n];
for(int i = 0; i < n; i++){
cin >> h[i];
}
for(int l = 0; l < n; l++){
for(int r = l + 1; r < n; r++){
int height = max(h[l], h[r]);
bool valid = 1;
for(int i = l + 1; i < r; i++){
if(h[i] > height){
valid = 0;
}
}
ans += valid;
}
}
cout << ans << '\n';
}
```
- Subtask 2
```cpp
#include<bits/stdc++.h>
using namespace std;
long long int ans = 0;
void find_max(int* h, int l, int r){
if(l >= r) return;
ans += (r - l); // += size - 1
int ma = -1, cut = 0;
for(int i = l; i <= r; i++){
if(h[i] > ma){
ma = h[i];
cut = i;
}
}
find_max(h, l, cut - 1);
find_max(h, cut + 1, r);
}
int main(){
int n;
cin >> n;
int h[n];
for(int i = 0; i < n; i++){
cin >> h[i];
}
find_max(h, 0, n - 1);
cout << ans << '\n';
}
```
- Subtask 3
```cpp
#include<bits/stdc++.h>
using namespace std;
long long int ans = 0;
void divide(int* h, int l, int r){
if(l == r) return;
int mid = (l + r) / 2;
divide(h, l, mid);
divide(h, mid+1, r);
vector<pair<int,int>> lv = {{-1, 0}} , rv = {{-1, 0}};
int lmax = -1, rmax = -1;
for(int i = mid, j = 0; i >= l; i--, j++){
if(h[i] > lmax){
lmax = h[i];
lv.push_back({h[i], j});
}
}
for(int i = mid + 1, j = 0; i <= r; i++, j++){
if(h[i] > rmax){
rmax = h[i];
rv.push_back({h[i], j});
}
}
int lsz = mid - l + 1, rsz = r - mid;
int lptr = lv.size() - 1, rptr = rv.size() - 1;
while(lptr >= 1 || rptr >= 1){
if(lv[lptr].first > rv[rptr].first){
ans += rsz;
lsz = lv[lptr].second;
lptr--;
}
else{
ans += lsz;
rsz = rv[rptr].second;
rptr--;
}
}
}
int main(){
int n;
cin >> n;
int h[n];
for(int i = 0; i < n; i++){
cin >> h[i];
}
divide(h, 0, n - 1);
cout << ans << '\n';
}
```
Sign in with Wallet
Connect another wallet