<style>
.reveal .slides {
font-size: 28px;
}
</style>
# TPR 30 題解
based on SCIST 演算法練習賽 #1
----
----
## 預期難度
### A < B < C < D < E < F
----
## 實際難度
### B < A < C < D < E < F
---
## PA. CDC 的九宮格政策
原題發想：Ateto
----
### 子任務 1（20 %）
$n, m \le 1000, x = 1$
----
- 每個人確診之後都只有自己需要隔離
- 答案就是 $n \times m$
----
### 子任務 2（50 %）
$n, m \le 1000$
----
- 假設最後需要 $a \times b$ 個人確診
- 使用圖解法，可以發現：
- 當 $x \mid n$ 時，$a = \frac{n}{x}$
- 否則，$a = \frac{n}{x} + 1$
- $b$ 的算法也同理
----
所以我們可以得出一個結論：
$(a, b) = (\lceil \frac{n}{x} \rceil, \lceil \frac{m}{x} \rceil)$
至於算法的部分，你可以使用：
- if 判斷式
- bool 轉 int
- 數學解
----
#### if 判斷式
```cpp=
int n, m, x, a, b;
cin >> n >> m >> x;
a = n / x, b = m / x;
if (n % x)
a++;
if (m % x)
b++;
cout << a * b << '\n';
```
----
#### bool 轉 int
```cpp=
int n, m, x, a, b;
cin >> n >> m >> x;
a = n / x + (n % x != 0);
b = m / x + (m % x != 0);
cout << a * b << '\n';
```
----
#### 數學解
```cpp=
int n, m, x;
cin >> n >> m >> x;
cout << ((n + x - 1) / x) * ((m + x - 1) / x) << '\n';
```
----
### 子任務 3（30 %）
無額外限制
----
- 注意到原題的範圍：$1 \le n, m, x \le 10^9$
- 因此最終答案會超過 32-bit int 所能儲存的範圍
- 需要使用 long long（64-bit int）
----
```cpp=
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
signed main() {
long long n, m, x;
cin >> n >> m >> x;
cout << ((n + x - 1) / x) * ((m + x - 1) / x) << '\n';
return 0;
}
```
---
## PB. 必做題勾選
原題發想：fishhh
----
這其實是一個很經典的賽局理論 - Nim game
----
但是如何推導出必勝策略並不是我們希望考的
因此我們把策略都寫在了範測裡
----
只需要觀察到一個性質：
當 $3 \mid n$ 時，先手必輸，否則先手必贏
因此我們只需要寫一個判斷式就好了
----
```cpp=
int n;
cin >> n;
if (n % 3)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
```
----
或是用更高級的三元運算子
```cpp=
int n;
cin >> n;
cout << (n % 3 ? "Yes" : "No") << '\n';
```
----
```cpp=
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
if (n % 3)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
```
---
## PC. 交換禮物
原題發想：fishhh
----
給定每個人準備的禮物編號（編號不重複），求經過 $m$ 次交換後，有幾個人拿到的禮物是自己原本準備的
----
### 子任務 1（23 %）
$a_i = i, m = 1$
----
紀錄 $p_{1, j} = j$ 的數量即可
----
### 子任務 2（11 %）
$m = 1$
----
做法跟子任務 1 基本一致，不過由於 $a_i \neq i$，因此需要額外紀錄 $a_i$
最終紀錄 $p_{1, j} = a_j$ 的數量即可
----
### 子任務 3（15 %）
$a_i = i$
----
~~這個子任務其實沒什麼用~~
----
- 開一個二維陣列 $gift[n][m]$，$gift[i][j]$ 代表第 $i$ 輪結束後第 $j$ 人的編號
- $gift[0][j]$ 代表最一開始的禮物編號
- 利用陣列模擬交換的過程
- 最後紀錄 $gift[m][j] = j$ 的數量
----
```cpp=
#include <iostream>
using namespace std;
const int MAXN = 1005;
int a[MAXN], gift[MAXN][MAXN];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
gift[0][i] = a[i];
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int p;
cin >> p;
gift[i][p] = gift[i - 1][j];
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (gift[m][i] == i)
ans++;
}
cout << ans << '\n';
return 0;
}
```
----
### 子任務 4（51 %）
無額外限制
----
作法基本上跟子任務 3 一樣，只是最後是用禮物編號來判斷
----
```cpp=
#include <iostream>
using namespace std;
const int MAXN = 1005;
int a[MAXN], gift[MAXN][MAXN];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
gift[0][i] = a[i];
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int p;
cin >> p;
gift[i][p] = gift[i - 1][j];
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (gift[m][i] == a[i])
ans++;
}
cout << ans << '\n';
return 0;
}
```
----
### 補充技巧：滾動陣列
----
- 可以發現到，第 $i$ 次操作其實只跟第 $i-1$ 次操作的結果有關
- 所以可以不用開到 $n \times m$ 的陣列
- 只需要紀錄第 $i-1, i$ 次操作的結果即可
- 維護 $gift[0][j]$ 為上一次操作的結果，$gift[1][j]$ 為這一次
- 操作完之後再將 $gift[1][j]$ 的內容搬到 $gift[0][j]$ 即可
- 這個技巧可以讓陣列大小幾乎少了一維
----
```cpp=
#include <iostream>
using namespace std;
const int MAXN = 1005;
int a[MAXN], gift[2][MAXN];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
gift[0][i] = a[i];
}
for (int i = 0; i < m; i++) {
for (int j = 1; j <= n; j++) {
int p;
cin >> p;
gift[1][p] = gift[0][j];
}
for (int j = 1; j <= n; j++)
gift[0][j] = gift[1][j];
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (gift[0][i] == a[i])
ans++;
}
cout << ans << '\n';
return 0;
}
```
----
### 小趣事
其實輸入的第一行根本沒有用 hehe
剛剛電老鼠提醒我才發現的 orz
---
## PD. 恐龍語言分析
原題發想：fishhh
----
主要有三個步驟：
1. 將大寫轉換為小寫
2. 去除多餘的字母
3. 計算 yee 的次數
不過 2、3 其實是可以合併進行的
----
#### 將大寫轉換為小寫
- 可以使用 `isupper(c)` 函式，或是使用 ascii 碼判斷是否為大寫（`'A' <= c && c <= 'Z'`）
- 轉為小寫可以使用 `tolower(c)`，或是 `c = 'a' + c - 'A'`
----
#### 計算答案
- 由左而右一個一個掃過去
- 用類似"收集"的概念，紀錄目前收集到 "yee" 中的第幾個了
- 如果符合下一個要收集的，就記錄下來
- 當三個字元都收集完之後，答案 +1、重新記錄收集到的字元
----
- 有不少人都以為是連續的子字串才算
- 但其實不是，根據題目提到的 "過濾"，其實要求的是子序列
----
```cpp=
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
cin >> s;
int ans = 0, now = 0;
string tar = "yee";
for (int i = 0; i < s.size(); i++) {
if (isupper(s[i])) // if ('A' <= s[i] && s[i] <= 'Z')
s[i] = tolower(s[i]); // s[i] = s[i] - 'A' + 'a'
now += (s[i] == tar[now]);
ans += now / 3;
now %= 3;
}
cout << ans << endl;
return 0;
}
```
---
## PE. 取餘遊戲
原題發想：Jun-an
----
~~這題其實是數學題~~
----
### 子任務 1（15 %）
$b = 0$
~~這個子任務其實沒有意義~~
----
### 子任務 2（20 %）
$a = 2, P = 10$
----
紀錄 $2^1 \sim 2^4 \mod P$，如果洽有一個為 $b$，代表有答案，否則輸出 $-1$
----
### 子任務 3（20 \%）
$a = 3, P = 10$
----
做法跟子任務 2 一樣，就不多說了
----
### 子任務 4（45 %）
無額外限制
----
這部分就要有一些數論的知識了
----
首先我們要先了解幾個性質：
1. $a \mod P$ 至多只會有 $P$ 個餘數
2. $(a \times b) \mod P = ((a \mod P) \times (b \mod P) )\mod P$
根據以上兩個性質，我們可以得出一個結論：
**對於所有$1 \le i \le P, i \in \mathbb{N}^+$ 以內，a^i 一定會循環**
----
意思就是，我們只需要找 $a^1 \sim a^P$，如果沒找到的話，答案就是 $-1$
有了這個結論，就很簡單了
----
```cpp=
#include <iostream>
using namespace std;
int main()
{
int a, b, P;
cin >> a >> b >> P;
int tmp = 1;
bool find_ans = false;
for (int i = 1; i <= P; i++) {
tmp = (tmp * a) % P;
if (tmp == b) {
cout << i << '\n';
find_ans = true;
break;
}
}
if (!find_ans)
cout << -1 << '\n';
return 0;
}
```
---
## PF. 一個二維迷宮
原題發想：Koying
----
很明顯的實作題(O
----
### 子任務 1（5 %）
$n \le 750, m = 0$
----
- 當沒有任何道具時，唯一的路徑就是按照順序走
- 所以答案就是 $n \times n$
----
### 子任務 2（20 \%）
$n \le 750$
----
主要會有兩大實作重點：
1. 建立地圖（每格的編號）
2. 走迷宮
----
#### 建立地圖
- 我們可以先建立一個二維陣列，分別為往下、左、上、右走一格的移動量
```cpp=
int p[4][2] = {
{1, 0},
{0, -1},
{-1, 0},
{0, 1}
};
```
- 接著一直重複下左上右的步驟，每次遇到邊界或是有標過的格子就轉彎，直到標到 $n \times n$ 格為止
- 如此一來就可以將每一格標上編號了！
----
```cpp=
int now = 0;
int x = -1, y = n - 1;
while (now < n * n) {
for (int i = 0; i < 4 && now < n * n; i++) {
while (1) {
int tmpx = x + p[i][0], tmpy = y + p[i][1];
if (tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < n && !maze[tmpx][tmpy]) {
x = tmpx;
y = tmpy;
now++;
maze[x][y] = now;
}
else
break;
}
}
}
```
----
#### 走迷宮
- 從起點開始，每次往四個方位搜索
- 接著有兩種情況
- 沒道具：往編號為目前編號 +1 的格子走
- 有道具：往最大編號的格子走
- 走的同時記錄格數，就完成了！
----
```cpp=
int ans = 0;
x = 0, y = n - 1;
while (maze[x][y] != n * n) {
ans++;
int mx = 0, pos = 0;
for (int i = 0; i < 4; i++) {
int tmpx = x + p[i][0], tmpy = y + p[i][1];
if (tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < n) {
if ((maze[tmpx][tmpy] > mx && spe[maze[x][y]]) || (maze[tmpx][tmpy] == maze[x][y] + 1 && maze[tmpx][tmpy] > mx)) {
mx = maze[tmpx][tmpy];
pos = i;
}
}
}
x += p[pos][0];
y += p[pos][1];
}
```
----
### 子任務 3（15 %）
$m = 0$
----
一樣輸出 $n \times n$ 就好了
----
### 子任務 4（60 %）
----
做法跟子任務 2 一模一樣
只是範圍比較大
----
#### 為什麼只是範圍有差還要另外出一個子任務？
----
- 其實這並不是為了要卡你們 TLE
- 如果你將陣列開在了 main 裡面，應該會得到 RE 的結果
- 這是因為區域變數會有大小限制
- 如果開在全域就沒問題了！
- 因為這個問題在各大比賽都可能會遇到，所以特別設計了這個範圍
----
完整程式碼：
```cpp=
#include <iostream>
using namespace std;
const int MAXN = 7505;
int maze[MAXN][MAXN];
bool spe[MAXN * MAXN];
int p[4][2] = {
{1, 0},
{0, -1},
{-1, 0},
{0, 1}
};
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int k;
cin >> k;
spe[k] = true;
}
int now = 0;
int x = -1, y = n - 1;
while (now < n * n) {
for (int i = 0; i < 4 && now < n * n; i++) {
while (1) {
int tmpx = x + p[i][0], tmpy = y + p[i][1];
if (tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < n && !maze[tmpx][tmpy]) {
x = tmpx;
y = tmpy;
now++;
maze[x][y] = now;
}
else
break;
}
}
}
int ans = 0;
x = 0, y = n - 1;
while (maze[x][y] != n * n) {
ans++;
int mx = 0, pos = 0;
for (int i = 0; i < 4; i++) {
int tmpx = x + p[i][0], tmpy = y + p[i][1];
if (tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < n) {
if ((maze[tmpx][tmpy] > mx && spe[maze[x][y]]) || (maze[tmpx][tmpy] == maze[x][y] + 1 && maze[tmpx][tmpy] > mx)) {
mx = maze[tmpx][tmpy];
pos = i;
}
}
}
x += p[pos][0];
y += p[pos][1];
}
cout << ans + 1 << endl;
return 0;
}
```
---
## 總結
----
- 題目好像有點太難了 \\|/
- 大家都不怎麼撈部分分 QQ
- 其實題目都有一些關鍵性質，如果能觀察到就會變很簡單
- 還有一堆人都忘記看題目範圍，沒開 long long
- 希望大家聽完題解有豁然開朗，也希望有學到新東西 ><
- 為了讓我們可以辦更好的比賽，請幫我們填寫回饋表單
- https://forms.gle/qGH4BTQUStVzyp2a7
----
### 程式碼釋出
本次比賽的所有程式碼（官解、生成器）都會放在 GitHub 上
歡迎大家參考（~~也可以幫我們案一顆星星~~）
連結：https://github.com/NHDK-Ten-Point-Round/ten-point-round-30
{"metaMigratedAt":"2023-06-17T13:38:00.078Z","metaMigratedFrom":"YAML","title":"TPR 30 題解","breaks":true,"slideOptions":"{\"transition\":\"slide\",\"transitionSpeed\":\"fast\"}","contributors":"[{\"id\":\"73093035-99f8-4a9b-b033-c17f49e2d490\",\"add\":10495,\"del\":40}]"}