# Ten Point Round #16
(Div. 3, based on 台南女中資訊研究社 期末測驗)
賽後題解

<style>
.reveal .slides {
font-size: 28px;
}
</style>

---

## Problem A. 社團旅遊的策略
出題者：ColtenOuO

首殺：Darren0724 - 01:03

----

一年級可以免費參加的人數為 $\lfloor \frac{k_1}{3} \rfloor$

二年級可以免費參加的人數為 $\lfloor \frac{k_2}{3} \rfloor$

三年級可以免費參加的人數為 $\lfloor \frac{k_3}{3} \rfloor$

答案即為 $(k_1 + k_2 + k_3) \times n - (\lfloor \frac{k_1}{3} \rfloor+\lfloor \frac{k_2}{3} \rfloor+\lfloor \frac{k_3}{3} \rfloor) \times n$

時間複雜度： $O(1)$

---

## Problem B. 被重新定義規則的比大小遊戲
出題者：ColtenOuO

首殺：Penguin07 - 05:12

----

特別注意到範圍 $|a|,|b| \le 10^9$ 可能有負數的 case
在負數時，如果該數為奇數，那麼$\mod 2$ 的結果會是$-1$ 而不是 $1$

----

判斷時除了利用餘數也可以利用位元運算的來判斷奇偶性

剩下著就依照題目所要求的進行實作即可

時間複雜度： $O(1)$

---

## Problem C. 冪次的藝術
出題者：ColtenOuO

首殺：Darren0724 - 06:35

----

觀察式子 $n^m > kn^{m-1}$

----

剛剛那個不等式兩邊同除 $n^{m-1}$ 得到 $n > k$

----

所以只需要檢查 $n > k$ 這個式子是否成立即可

不需要真的把數字算出來

每組資料時間複雜度：$O(1)$

---

## Problem D. 想要完美取值的 Colten
出題者：ColtenOuO

首殺：suineGsIneK - 09:25

----

這個概念其實之前有出過 (題目名稱：提問時間)

----

既然我們有 $[L,R]$ 這些數字可以選

那我們就來計算看看我們可以組合出那些數字

----

可以組合出的最小值：$\sum\limits_{i=L}^{L+5}i = L + (L+1) + ... + (L + 5)$

可以組合出的最大值：$\sum\limits_{i=R-5}^{R}i = (R-5) + (R-4) + ... + R$

----

因此只要 $\sum\limits_{i=L}^{L+5}i \le M \le \sum\limits_{i=R-5}^{R}i$

就表示一定可以選出 $6$ 個數字的和等於 $M$

時間複雜度： $O(1)$

----

這題共有 $141$ 個測資

---

## Problem E. 倒水問題
出題者：ColtenOuO

首殺：Penguin07 - 14:51

----

這題是我之前去當 AA 競程的營隊助教時幫忙 dreamoon 出在營末測驗題目

----

顧名思義，是個 Water Problem

只是大家可能都想太多了

----

觀察到兩種操作都只能個使用 $10$ 次

那我就枚舉兩種操作的使用情況

把所有情況枚舉出來後依照題目要求取最好的答案

時間複雜度：$O(10^2)$

---

## Problem F. zhu 的竹子序列
出題者：ColtenOuO

首殺：suineGsIneK - 13:47

----

這題就算你不會 std::sort 或其他排序演算法也可以做

----

題目有一個很重要的限制是：所有元素都只會出現一次

因此如果你想要找第 $k$ 大的元素

假設現在序列的長度為 $n$

那麼這個序列裡會共有 $k-1$ 個元素比第 $k$ 大的元素還要大

----

因此你就可以超級大暴力的枚舉所有元素，看他是不是答案

這題是故意讓不會寫排序的人也可以拿到分數的

時間複雜度： $O(Q^2)$

---

## Problem G. Colten 的 2022 字母加法
出題者：ColtenOuO

首殺：user1519 - 18:08

----

這題主要考驗大家字串轉整數的應用

----

利用 ASCII 碼來判斷該字母為第幾個

並利用字串相加的特性，在最後轉型成整數計算

時間複雜度：$O(|a|+|b|)$

---

## Problem H. XOR 與 OR 的最大值問題
出題者：ColtenOuO

首殺：suineGsIneK - 05:43

----

這題的概念其實之前也出現過 (奇數偶數全排列 Hard)

----

Greedy 會不會很難想

不知道誰要放左邊誰要放右邊比較好

----

觀察到數字只有 $3$ 個

那我們就枚舉所有的排列取最好的答案就好了呀！！！

----

$(a_1,a_2,a_3)$
$(a_1,a_3,a_2)$
$(a_2,a_1,a_3)$
$(a_2,a_3,a_1)$
$(a_3,a_1,a_2)$
$(a_3,a_2,a_1)$

----

可以把那一串公式寫成一個函式

這樣就不用一直複製貼上了

----

int solve(int a,int b,int c)
{
	return ( (a^b^c) | ( a | ( b ^ c ) ) ) + ( a ^ c ) + ( a | b | c ) + ( ( ( c | a ) ^ ((a+b)|c) ) );	
}

---

## Problem I. 差不多先生的高鐵打工記
出題者：Koying

首殺：suineGsIneK - 36:35

----

由於題目有提到距離一定可以被 $lcm(1, 2, 3)=6$ 整除，
因此在時刻表上不會出現有小數點的情況

----

在實作上我們需要紀錄以下幾點數據

- 車站距離的前綴和
- 每種車輛的速度以及停靠時間
- 該班車輛在上一個停靠點的發車時間

有了以下三點數據，我們就可以利用上一個停靠點的停靠時間

以 (車站間的距離 $\div$ 車輛的速度) 即可算出下一座車站的停靠時間

----

至於沒有停靠的車站，
我們可以在一開始將其設為 $-1$ 並於輸出時一併判斷即可

時間複雜度：$O(n \times m)$

----

:::spoiler 參考程式

#include <bits/stdc++.h>

using namespace std;

#define MAXN 1005
#define MAXM 105

int n, m;
int d[MAXM], pre[MAXM];
int id[MAXN], t[MAXN], s[MAXN], c[MAXN];
int p[MAXN][MAXM], ans[MAXN][MAXM];
const int speed[4] = {0, 3, 2, 1}, stop[4] = {0, 6, 4, 2};

int main() {
    cin >> n >> m;
    for (int i = 2; i <= m; i++) {
        cin >> d[i];
        pre[i] = pre[i - 1] + d[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> id[i] >> t[i] >> s[i] >> c[i];
        for (int j = 1; j <= m; j++) 
            ans[i][j] = -1;
        
        ans[i][1] = s[i];
        int tmp = s[i], now = 1;
        for (int j = 0; j < c[i]; j++) {
            cin >> p[i][j];
            ans[i][p[i][j]] = tmp + (pre[p[i][j]] - pre[now]) / speed[t[i]];
            tmp = ans[i][p[i][j]] + stop[t[i]];
            now = p[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        cout << id[i] << " ";
        for (int j = 1; j <= m; j++) {
            if (ans[i][j] < 0) cout << "-- ";
            else cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    // system("pause");
    return 0;
}

:::

---

## Problem J. Colten 採菱角
出題者：Koying

首殺：suineGsIneK - 21:08

----

可以觀察到，題目要求的就是在某個區間內的菱角變化量總和最大值

也就是區間最大連續和

----

在前綴和的應用中，$[L,R]$ 的前綴和為 $pre[R]-pre[L-1]$

因此對於每個以 $R$ 為結尾的區間，其最大前墜連續和就是 $pre[R]-min_{pre[i]},i<R$

----

所以我們可以記錄一個變數為目前的最小前綴和，
即可求出以目前位置為結尾的的最大連續和

最後取最大值即可

時間複雜度 $O(n)$

----

這題有 121 筆測資

----

:::spoiler 參考程式

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main() {
    int n;
    cin >> n;
    ll ans = 0;
    ll sum = 0;
    ll mn = 0;
    for (ll i = 0, a; i < n; i++) {
        cin >> a;
        sum += a;
        ans = max(ans, sum - mn);
        mn = min(mn, sum);
    }
    cout << ans << endl;
    return 0;
}

:::

---

## Special Thanks

----

### 驗題者
dreamoon_love_AA, LittleCube, Fysty, yungyao, YIEC2538,
zhu., diexuan, a_ahui, YeZ, springyu, annie_yeh, hanaaa, Tamilala, Chopper_226

----

### 協辦單位 - AA 競程

----

## 主辦單位 - 臺南女中資訊研究社

----

## 主辦單位 - NHDK Ten Point Round

---

## 賽中的有趣情況

----

還記得 PJ 賽中的 Rejudge 嗎

後來補強的測資長這樣
你有被星爆到嗎?

----

讓我們為 WA on Test 101 的參賽者們默哀

----

---

###### tags: `題解`