# 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)$ ---- 可以把那一串公式寫成一個函式 這樣就不用一直複製貼上了 ---- ```cpp= 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 參考程式 ```cpp= #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 參考程式 ```cpp= #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: `題解`