---
# System prepended metadata

title: 112 學年度 竹科實中校內賽題解
tags: [CompetitiveProgramming]

---

# 112 學年度 竹科實中校內賽題解


## pA. 區間第k大 
#### writer: PixelCat
#### 定位：水

:::warning
:::spoiler 滿分
因為題目有保證陣列 $A$ 是嚴格遞增，所以 $[L,R]$ 範圍中第k大的數字就是 $A[R-k+1]$。直接輸出即可。
:::

:::info
:::spoiler sample code
```cpp=
#include<iostream>
using namespace std;
 
int n,arr[105],l,r,k;
int main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>arr[i];
    cin>>l>>r>>k;
    cout<<arr[r-k+1]<<endl;
}
```
:::

## pB. 構造LIS
#### writer: Cookie197
#### 定位：中

:::warning
:::spoiler subtask 2
$n=2$ 的只有兩種可能的 $p$，即 $1,2$ 或 $2,1$。
:::

:::warning
:::spoiler subtask 3,4
$n\le 8$，可以利用 `next_permutation` 枚舉所有可能的答案，並利用經典算法計算出每個位置的 LIS 長度。例如 $O(n^2)$ DP。
找到其中一組合法答案即可輸出。
:::

:::warning
:::spoiler subtask 3,5 0.5倍
可以發現 $a$ 為非嚴格遞增，且會呈現 $1,1, \cdots 2,2, \cdots 3,3, \cdots$ 的形式。我們可以在每次換數字的地方讓 $p_i$ 遞增，不是換數字的地方就讓 $p_i$ 遞減。
例如：$a=[1,1,2,2,2,3,3,3]$ 可以構造 $p=[6,5,7,4,3,8,2,1]$。其中 $a_1=6,a_3=7,a_6=8$ 為遞增，$a_2=5,a_4=4,a_5=3,a_7=2,a_8=1$ 為遞減。
:::

:::warning
:::spoiler 滿分
1. 首先發現 「從根節點到 $i$ 的 $LIS$ 長度」 必定大於等於 「從根節點到 $i$ ，並最後一項元素是 $p_i$ 的 $LIS$ 長度」，$a_i \ge b_i$，a 陣列只是 b 陣列的前綴最大值，所以滿足 b 必定會滿足 a。
2. 觀察 $b_i$ 相同的 $i$，可以發現同一條鏈上越深者（or數線上越右邊） $p_i$ 會越小。
3. 接著，以$\ge 2$ 的 $b_i$ 而言，必須存在至少一個 $i$ 的祖先節點 $j$ 使得 $b_j = b_i - 1$ 且 $p_i > p_j$ ，因為在算LIS時 $i$ 才可以接在 $j$ 後面。
4. 我們可以建立大小關係的有向圖，從 $p_i$ 大的指向小的。第3點中，每個點找到一個 $b$  小1且離他最近的祖先節點建邊。第2點則是 $b$ 相同的祖孫互相連接。最後只要依拓撲序給節點們 $p_i$ 就好。

* 這題還有很多不同的解法，大家可以想想看
:::

:::info
:::spoiler 滿分另解 (code)
其實這題有看起來像唬爛的超短解。
```cpp=
int main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++) {cin>>b[i]; v[b[i]].push_back(i);}
    for (int i=2;i<=n;i++) int x, cin>>x;
 
    int x = n;
    for (int i=n;i>=1;i--){
        for (int u:v[i]) {
            ans[u] = x;
            x--;
        }
    }
 
    for (int i=1;i<=n;i++) cout<<ans[i]<<" ";
    cout<<endl;
}
```
:::



## pC. 核電廠
#### writer: PixelCat
#### 定位：中

:::warning
:::spoiler subtask 2
假如是第一天那一定要拿。假如不是第一天的話，要嘛拿起來獲得 $a_i - p$ 元，要嘛放棄然後什麼都拿不到，因為前一天亂乘之後會立刻變零。每一天的決策之間不會互相影響，greedy 就好。

時間複雜度 $O(n)$。這個子題的目的是讓你有機會撈分，順便告訴你 greedy 是錯的。
:::

:::warning
:::spoiler subtask 3
暴搜。

時間複雜度 $O(n 2^n)$。這個子題的目的是讓你有機會撈分。
:::

:::warning
:::spoiler subtask 4

注意到一根燃料棒被使用到的時間是一個連續區間，賺到的收入是從這個區間的第一天開始往後面一直乘加起來的總和。令 $f(i, j)$ 代表如果第 $i$ 天買的燃料棒一直用，會在第 $j$ 天獲得多少收入；$S(i, j)$ 帶表第 $i$ 天買的燃料棒一路用到第 $j$ 天的賺錢總和：

$$
f(i, j) = 
\begin{cases}
a_i, & \text{if $i = j$} \\
f(i, j - 1) \cdot c, & \text{otherwise}
\end{cases} \\
S(i, j) = \sum_{k = i}^j f(i, k)
$$

我們考慮動態規劃：`dp[i]` 代表第 $i$ 天結束的時候你能賺幾元，我們有以下轉移式：

$$
dp_0 = 0 \\
dp_i = \max_{0 < j \le i} \left( dp_{j - 1} + S(j, i) \right)
$$

枚舉 $i, j$ 之後暴力算 $S(j, i)$ 可以在 $O(n^3)$ 時間算完。

:::

:::warning
:::spoiler subtask 5

**作法一**

剛剛的 $S(j, i)$ 可以預處理建表，$O(1)$ 查詢，複雜度是 $O(n^2)$。

**作法二**

剛剛是枚舉每一段和前一段的結尾，但因為 $S$ 函數比較容易由前往後算，這次我們枚舉每一段的開頭、往後枚舉結尾，更新後面的答案。

```cpp=
auto f = [&](long long x) { return (x * c) / 1000; };

for(int i = 1; i <= n; i++) {
    long long cur = a[i];
    long long sum = a[i] - pen;
    for(int j = i; j <= n; j++) {
        dp[j] = max(dp[j], dp[i - 1] + sum);
        cur = f(cur);
        sum += cur;
    }
}
```

複雜度同樣是 $O(n^2)$。

改成由後往前做也可以做到 $O(n^2)$，可能有人會覺得比較直覺一點。留給讀者做為練習。

:::

:::warning
:::spoiler subtask 6

觀察到 $c < 1$，所以 $f(i, j) > 0 \Rightarrow f(i, j) > f(i, j + 1)$，在 $\max \left(a_i\right)$ 天後一根燃料棒將不再提供收入。也就是說，$S(i, j)$ 在 $j > 100 \geq \max \left(a_i\right)$ 時是定值，不用一個一個更新，可以丟進某個地方存起來，以後查最大值就好。

沿用上一個子任務的作法，每次我們往後轉移 100 天，時間複雜度 $O(n \cdot \max{a_i})$。

:::

:::warning
:::spoiler subtask 7

觀察到奇怪的條件 $c \le 0.95$，不會太大。

$$
\log_{1/c}\left( \max a_i \right) = \log_{1/0.95}10^9 < 405
$$

也就是說，在這麼多回合之後，所有燃料棒都會失效。時間複雜度 $O(n \cdot \log_{1/c}\left( \max a_i \right))$。

:::

:::info
:::spoiler Model Solution
```cpp=
#include<bits/stdc++.h>
#define int LL
using namespace std;
using LL = long long;

const int MAXN = 200'000;

int a[MAXN + 10];
int dp[MAXN + 10];
int mx[MAXN + 10];

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	// =^-w-^=
	int n, c, pen; cin >> n >> c >> pen;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		dp[i] = -1e18;
	}
	for(int i = 0; i <= n; i++) {
		mx[i] = -1e18;
	}

	auto f = [&](int x) { return (x * c) / 1000; };

	for(int i = 1; i <= n; i++) {
		int cur = a[i];
		int sum = a[i] - pen;
		for(int j = i; j <= n; j++) {
			if(cur == 0) {
				mx[j] = max(mx[j], dp[i - 1] + sum);
				break;
			}
			dp[j] = max(dp[j], dp[i - 1] + sum);
			cur = f(cur);
			sum += cur;
		}
		mx[i] = max(mx[i], mx[i - 1]);
		dp[i] = max(dp[i], mx[i]);
	}

	cout << dp[n] << "\n";
	return 0;
}

```
:::


## pD. 通行證
#### writer: Cookie197
#### 定位：中

:::warning
:::spoiler subtask 2
$n,m$ 都很小，可以暴力枚舉所有可能的 $1$ 到 $n$ 的路徑，並算出所有路徑中的最少花費。
:::

:::warning
:::spoiler subtask 3
$f \le 7$，可以 $2^f$ 枚舉所有幫派的 subset，只考慮那個 subset 對應的合法邊，看看能不能從 $1$ 走到 $n$。最後再從所有合法的 subset 找出最小花費。
複雜度 $O((n+m)2^f)$
:::

:::warning
:::spoiler subtask 4,5
題目有說明 $a_i \ge 2$，也就是說 $c_i$ 會 $\ge c_1 + c_2 + \cdots c_{i-1}$。
所以我們可以從最大的 $c$ 考慮「有沒有辦法不選他」。對於某個 $i$，如果忽略含有 $i$ 幫派的道路時仍能從 $1$ 走到 $n$，那就可以不付 $c_i$ 的錢，並要記得隨後的檢查都不能再走含有 幫派 $i$ 的道路。反之，我們就一定要選 $c_i$。
複雜度 $O((n+m)f)$
:::

:::warning
:::spoiler subtask 5 另解
其實就是 bitwise-or 最短路，$f\le 256$ 可以用 bitset 做。
:::

## pE. 叫外送
#### writer: Cookie197
#### 定位：難

:::warning
:::spoiler subtask 2
$n=1$ 分成兩個情形：
* 由左到右為 + -：直接走到底
* 由左到右為 - +：先拿披薩再走回住家
:::

:::warning
:::spoiler subtask 3
利用`next_permutation`暴力枚舉所有 $(2n)!$ 種可能的路線，在所有合法路線中找出距離最小值。
複雜度：$O(n(2n)!)$
:::

:::warning
:::spoiler subtask 4
1. 若不是在結尾，「拿一個披薩，送一個披薩」一定比「拿兩個披薩，送兩個披薩」好。（因為你送完要往右走，會有更大一個區塊被多算到）

畫一些圖就會發現（也可以參考 subtask 6 的圖），最佳解一定是「拿一個披薩，送一個披薩，拿一個披薩，送一個披薩...最後拿 $k$ 個披薩，送 $k$ 個披薩」
對於每個詢問枚舉這個 $k$ 就好。
複雜度：$O(nq)$
:::

:::warning
:::spoiler subtask 5
2. 最佳解的回頭點一定是發生在「住家數量前綴 = 店家數量前綴」的地方，因此我們可以把一串東西「簡化」成一個「- +」或「+ -」（剩下左右兩個「重要點」）然後再套 subtask 4 的作法。
例如：「- - + - + +」 $\Rightarrow$ 「- +」
3. 「+ -」可以直接從左邊走到右邊，因此可以直接忽略，但是如果是在結尾就要小心

簡化完就跟 subtask 4 一樣了

複雜度：$O(nq)$
:::

:::warning
:::spoiler subtask 6
4. 我們把 subtask 4 中，$k=1$ 到 $n$，「每個區間被算到幾次」寫出來，發現會是一串 1 和 3 交替，最後是一個 1 和一串 2，如下圖
![](https://hackmd.io/_uploads/H1P8efwJp.png =50%x)
5. 我們把 $k=x$ 時的答案稱為 $f(x)$。當某個區間的長度增加 $val$ 時，會存在某個 $p$ 使得以下兩者之一成立：
    *  $f(1)$ 到 $f(p)$ 都 增加 $3v$ ，$f(p+1)$ 到 $f(n)$ 都增加 $v$ (當區間編號為偶數)
    *  $f(1)$ 到 $f(p)$ 都 增加 $v$ ，$f(p+1)$ 到 $f(n)$ 都增加 $2v$ (當區間編號為奇數)
6. 因此我們可以用一個支援區間加值，全域最小值的線段樹來維護這個答案。一個建築的座標變動時，會有兩個區間的距離改變。

複雜度：$O(q\log(n))$
:::

:::warning
:::spoiler subtask 7
7. 根據 subtask 5，我們可以把建築物的排列「簡化」。簡化完再套剛剛的線段樹就好了！如果修改的建築不是「重要點」那可以直接忽略此次修改。
8. 若結尾是「+ -」請特別注意。在此不贅述。

複雜度：$O(q\log(n))$
:::

## pF. 夏日祭
#### writer: Cookie197
#### 定位：易

:::warning
:::spoiler 滿分
擷取高木，西片，和觀景台的座標。接著分成以下幾個情形來討論：
* 沒有觀景台：答案就是兩人的曼哈頓距離。
* 有觀景台：
    * 高木西片觀景台的 x 座標相同：
        * $n=1$：若觀景台的 y 座標在兩人中間，則答案為 -1，否則答案為兩人的曼哈頓距離 +2。
        * $n>1$：答案為兩人的曼哈頓距離 +2。
    * 高木西片觀景台的 y 座標相同：答案為兩人的曼哈頓距離 +2。
    * 以上皆非：答案為兩人的曼哈頓距離。
:::

:::warning
:::spoiler 滿分另解
使用 BFS。
:::