---
tags : 初階班
---
# 10th 初階班上學期期末考 題解
## 競賽用hello world
老樣子，送分題
:::spoiler `c`
```c=
#include<stdio.h>
int main() {
printf("hello, world\n");
return 0;
}
```
:::
:::spoiler `c++`
```cpp=
#include <iostream>
using namespace std;
int main() {
cout << "hello, world\n";
return 0;
}
```
:::
:::spoiler `python`
```python=
print("hello, world")
```
:::
## A. 為各位的期中考獻上祝福
這題直接用 `long long` 或 `unsigned long long` 都是 `NA 59%`
正解：
1. 兩數同號，用 `unsigned long long`
2. 兩數異號，直接 `a + b`
3. 若 $a = b = -2^{63}$，需要特判，因為 `unsigned long long` 裝不下。
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main() {
LL a, b;
cin >> a >> b;
if (a < 0 ^ b < 0) cout << a + b;
else {
if (a == b && a == LLONG_MIN) cout << "-18446744073709551616";
else {
unsigned LL pa = abs(a), pb = abs(b);
if (a < 0) cout << '-';
cout << pa + pb;
}
}
return 0;
}
```
:::
另解：
使用毒瘤資料型態 `__int128` :poop:
為了讓各位覺得它有使用的價值，
先給各位看一下 `main()` 函數裡面的程式碼。
```cpp=
int main() {
__int128 a, b;
cin >> a >> b;
cout << a+b << '\n';
}
```
是不是很簡短!!!
但是它全部的程式碼卻有點複雜，
有興趣的可以參考看看。
:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
namespace int128IO {
istream& operator>>(istream& is, __int128& i) {
string s; is>>s; i = 0;
auto c=s.begin(); c+=(s[0]=='-');
for(; c!=s.end(); ++c) i=i*10+(*c-'0');
if(s[0]=='-') i=-i;
return is;
}
ostream& operator<<(ostream& os, __int128 i) {
string s; bool neg=false; if(i<0) neg=true, i=-i;
while(i) s+=('0'+i%10), i/=10;
if(neg) os<<'-';
for(auto c=s.rbegin();c!=s.rend();++c) os<<*c;
return os;
}
}
using namespace int128IO;
int main() {
__int128 a, b;
cin >> a >> b;
cout << a+b << '\n';
}
```
:::
## B.小青蛙吃蒼蠅
這題應該非常簡單
只是有個小陷阱
那就是每隻青蛙每分鐘吃的蒼蠅數不一定是整數
所以可以先把所有數乘起來
最後再除
:::spoiler code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
int a1, a2, a3, b1, b2;
cin >> a1 >> a2 >> a3 >> b1 >> b2;
cout << a3 * b1 * b2 / a1 / a2;
}
```
:::
## C.《關於台民想建一棟叫台民館的台民館這件事》
這是一提水題
不過有個小陷阱
那就是要判斷**台民館是否能被順利建造**
如果面積是0
那就代表不會被建造 :poop:
:::spoiler code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
long long a, b, c;
while (cin >> a >> b >> c) {
long long maxn = a * b / 100;
cout << maxn << ' ';
if (max >= c && c != 0) cout << "yes\n";
else cout << "no\n";
}
}
```
:::
## D. 金斧頭一砍八
#### NA 60%
照著題敘一個一個把人砍掉即可
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
int main() {
int T, n;
cin >> T;
while (T--) {
cin >> n;
bool alive[n + 1];
memset(alive, 1, sizeof(alive));
bool flag = true;
for (int i = 1, tmp = 0; tmp < n - 1; i == n ? i = 1 : i++) {
if (alive[i]) {
flag = !flag;
if (flag) alive[i] = 0, tmp++;
}
}
for (int i = 1; i <= n; i++) {
if (alive[i]) {cout << i << '\n'; break;}
}
}
return 0;
}
```
:::
#### AC
##### solve 1
其實砍人有其規律：
如果把編號 $1\sim n$ 砍完一圈算一輪，
假設現在是第 $r$ 輪，還有 $p$ 人未蹲下，且未蹲下的人中，編號最小的是 $k$，則：
1. 未蹲下的人中，相鄰編號差距為 $2^{r - 1}$
2. 從編號 $1\sim n$ 砍完，人會剩 $[\cfrac p2]$ 人
3. 若 $p$ 為奇數，則砍完人後，最小編號會變成 $k + 2^r$
如此就可以省去 `for` 迴圈從 $1$ 跑到 $n$ 的過程。
有趣的是，如果 $2^r$ 用 `pow` 的話，不僅慢，還可能有精度問題 (他是浮點數)
因此我們可以把 $2^0\sim 2^{30}$ 次方建出來，加快速度。
(由於 $n\in int$ 及第 3. 點證明，因此可以得知 $r\leq 30$)
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
#define mem(x) memset(x, 0, sizeof(x))
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
constexpr int mod = 1e9 + 7;
int main() {
cin.tie(0), ios_base::sync_with_stdio(false);
int pow[31] = {1};
for(int i = 1; i <= 30; i++) pow[i] = pow[i - 1] * 2;
int T, n;
cin >> T;
while (T--) {
cin >> n;
int k = 1, r = 1;
while (n > 1) {
if (n % 2 == 1) { // if(n & 1)
k += pow[r]; // k += (1 << r)
}
n /= 2, r++; // n >>= 1, r++
}
cout << k << '\n';
}
return 0;
//上方程式碼註解是給進階班的 code，初階班可以不用建表就 AC
}
```
:::
##### solve 2
如果你花了很久的時間找數列的規律，
可以發現答案是：${1}, \{1, 3\}, \{1, 3, 5, 7\}, \{1, 3, 5, 7, 9, 11, 13, 15\}...$
可以轉換成數學式：$(n - 2^{[{\log_2}^n]})\times 2 + 1$
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
int main() {
cin.tie(0), ios_base::sync_with_stdio(false);
int pow[31] = {1};
for (int i = 1; i <= 30; i++) pow[i] = pow[i - 1] * 2;
int T, n;
cin >> T;
while (T--) {
cin >> n;
cout << (n - pow[__lg(n)]) * 2 + 1 << '\n';
//cout << (n - (1 << __lg(n)) << 1 | 1) << '\n';
}
return 0;
//上方程式碼註解是給進階班的 code，進階班可以不用建表就 AC
}
```
:::
## E.夏天
沒錯
又是暈船題
就照著題目所說的打就會過
:::spoiler code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
int q;
cin >> q;
while (q--) {
int n, m, k, x, y;
string str;
cin >> n >> m >> k >> x >> y >> str;
n %= 360;
if (n == 0 || n >= 270) {
int nowx = k / 2 + 1, nowy = k / 2 + 1;
x = k / 2 + 1 - x, y = k / 2 + 1 - y;
for (int i = 0; i < str.length(); i++) {
if (str[i] == 'U') nowx--;
else if (str[i] == 'D') nowx++;
else if (str[i] == 'L') nowy++;
else nowy--;
if (nowx == 0) nowx = 1;
else if (nowx == k + 1) nowx = k;
if (nowy == 0) nowy = 1;
else if (nowy == k + 1) nowy = k;
}
if (abs(nowx - x) <= 1 && abs(nowy - y) <= 1) cout << "You will find your true love!\n";
else cout << "Fxxk, I am lost\n";
}
else cout << "You should go home\n";
}
}
```
:::
## F.Q怎麼還在暈
這題是難得幾乎只能用遞迴的題目
如果$p>q$，那$n$必為偶數
如果$p<q$，那$n$必為奇數
所以只要這此規則遞迴到 $p=q$ 即可
:::spoiler code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int trans(int p, int q) {
if (p == q) return 1;
else if (p < q) return 1 + trans(q, p);
else if (p > q) return trans(p - q, q) * 2;
}
int main() {
int p, q;
while (cin >> p >> q)
cout << trans(p, q) << '\n';
}
```
:::
## G.陣列刪除
這題應該需要小小的動腦
花費最少的情況就是優先刪最小的數
所以先把陣列sort一遍
找出最少的那些數即可
:::spoiler code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int arr[n];
for(int i = 0 ; i < n; i++) cin >> arr[i];
sort (arr, arr + n);
int sum = 0 ;
for(int i = 0 ; i < n/2 ; i++) sum += arr[i];
cout << sum << '\n';
}
```
:::
## H.矩陣加密
這題稍微難上不少
首先你要知道矩陣乘法的規則
但這個從題目應該就可以觀察出規律
但要實踐它又有些難度
過了這兩關
應該就沒問題了
:::spoiler code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
string str;
int a, b, c, d;
cin >> str >> a >> b >> c >> d;
int l = str.length();
int arr[2][l / 2];
int key[2][2];
int ans[2][l / 2];
key[0][0] = a, key[0][1] = b, key[1][0] = c, key[1][1] = d;
for (int i = 0; i < l; i++) {
if (i < l / 2) arr[0][i] = (int)(str[i] - 65);
else arr[1][i - l / 2] = (int)(str[i] - 65);
}
for (int i = 0; i < 2; i++) for (int j = 0; j < l / 2; j++) ans[i][j] = 0;
for (int i = 0; i < 2; i++) for (int j = 0; j < l / 2; j++) for (int k = 0; k < 2; k++)
ans[i][j] += (key[i][k] * arr[k][j]);
for (int i = 0; i < 2; i++) for (int j = 0; j < l / 2; j++) cout << (char)(ans[i][j] % 26 + 65);
}
```
:::
## I. 持續演奏，直至心願實現
#### NA 10%
很簡單，把整個音譜跑過去，符合規則就是 $1$，不符合就是 $0$
#### NA 20%
暴搜 $w[i] = ?$ 的所有可能性
但是暴搜時，要記得：
1. 一個音符不能跨越兩個小節 $\implies$ `DFS` 時要有一個變數 `cur` 記錄當前拍數
2. 避免有「小數」拍子，可以將每個音節設定為 $\cfrac {16n}{m}$ 個十六分音符拍
3. 相對地，$k$ 分音符變 $\cfrac {16} k$ 拍
綜合以上 $3$ 點，我們可以知道 `check` 機制是：$cur \leq \cfrac{16n}{m}$
而這個 `DFS` 可以剪枝，如果當前節拍已經不符音譜規定，
那也不需要繼續遞迴後面的節拍了。
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
int sum = 0, n, m, len, check;
string str;
void dfs(int i, int cur) {
if (i == len && cur == check) {sum++; return;}
cur %= check;
if (str[i] != '?') {
if (str[i] == 'M' && cur + 8 <= check) dfs(i + 1, cur + 8);
else if (str[i] == 'C' && cur + 4 <= check) dfs(i + 1, cur + 4);
else if (str[i] == 'Q' && cur + 2 <= check) dfs(i + 1, cur + 2);
else if (str[i] == 'S' && cur + 1 <= check) dfs(i + 1, cur + 1);
else return;
}
else {
if (cur + 8 <= check) dfs(i + 1, cur + 8);
if (cur + 4 <= check) dfs(i + 1, cur + 4);
if (cur + 2 <= check) dfs(i + 1, cur + 2);
if (cur + 1 <= check) dfs(i + 1, cur + 1);
}
}
int main() {
cin >> n >> m;
cin.get(), cin >> str;
len = str.size(), check = 16 / m * n;
dfs(0, 0), cout << sum;
return 0;
}
```
:::
#### NA 40%
從這裡開始就是使用 `DP` 了
在剛剛的 NA 20% 解中，我們可以發現：當前節拍數 `cur` 是很重要的，
所以我們可以建一個陣列，存下當前音符之下，各種拍數的可能數各為多少。
前 $20\%$ 的 `DP` 測資只有 $?$，所以只要知道 $?$ 的轉移式即可：
$dp[i][j] = dp[i - 1][j - 8] + dp[i - 1][j - 4] + dp[i - 1][j - 2] + dp[i - 1][j - 1]$
$i$ 是指當前第幾音符，$j$ 是指第幾節拍，
但是要注意溢位問題喔！
需判斷 $j - 8,\;j - 4,\;j - 2,\;j - 1\geq 0$
#### AC
先說一下，NA 60% 是給複雜度歪掉的人用的
直接來講如何 AC。
從 NA 40% 的解法可以知道：只差 $w[i]\neq \;?$ 的轉移式就 AC 了。
不難理解，其實 $?$ 的轉移式就是把 $\{M,\;C,\;Q,\;S\}$ 的轉移式相加
把他們分開就好。
因此，所有 $DP$ 轉移式如下：
$\displaystyle \begin{cases} \displaystyle \begin{cases} dp[i][j] = 0\\
dp[i][j] = dp[i][j] + dp[i - 1][j - 8]
\quad\quad if\quad j \geq 8\\
dp[i][j] = dp[i][j] + dp[i - 1][j - 4]
\quad\quad if\quad j \geq 4\\
dp[i][j] = dp[i][j] + dp[i - 1][j - 2]
\quad\quad if\quad j \geq 2\\
dp[i][j] = dp[i][j] + dp[i - 1][j - 1]
\quad\quad if\quad j \geq 1\\
\end{cases}
\quad\quad if\quad w[i] =\;?\\\\
dp[i][j] = dp[i - 1][j - 8]
\quad\quad if\quad (j \geq 8\quad and\quad w[i]=\;M)\\
dp[i][j] = dp[i - 1][j - 4]\quad\quad if\quad (j \geq 4\quad and\quad w[i]=\;C)\\
dp[i][j] = dp[i - 1][j - 2]\quad\quad if\quad (j \geq 2\quad and\quad w[i]=\;Q)\\dp[i][j] = dp[i - 1][j - 1]\quad\quad if\quad (j \geq 1\quad and\quad w[i]=\;S)\\dp[i][j] = 0\quad\quad\quad\quad\quad\;\;\;\quad\quad else \end{cases}$
:::spoiler `code_直觀`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
LL dp[2][145] = {1}; //dp[0][0] = 1, 16 * n / m <= 144
int main() {
int n, m;
cin >> n >> m;
int p = 16 * n / m;
string w; cin >> w;
const int len = w.size();
for (size_t i = 0; i < w.size(); i++) {
for (int j = 1; j <= p; j++) {
if(w[i] == '?'){
dp[~i & 1][j] = 0;
if(j >= 8) dp[~i & 1][j] += dp[i & 1][j - 8];
if(j >= 4) dp[~i & 1][j] += dp[i & 1][j - 4];
if(j >= 2) dp[~i & 1][j] += dp[i & 1][j - 2];
if(j >= 1) dp[~i & 1][j] += dp[i & 1][j - 1];
dp[~i & 1][j] %= mod;
}
else if(w[i] == 'M' && j >= 8)
dp[~i & 1][j] = dp[i & 1][j - 8];
else if(w[i] == 'C' && j >= 4)
dp[~i & 1][j] = dp[i & 1][j - 4];
else if(w[i] == 'Q' && j >= 2)
dp[~i & 1][j] = dp[i & 1][j - 2];
else if(w[i] == 'S' && j >= 1)
dp[~i & 1][j] = dp[i & 1][j - 1];
else dp[~i & 1][j] = 0;
}
dp[~i & 1][0] = dp[~i & 1][p];
}
cout << dp[len & 1][0];
return 0;
}
```
:::
:::spoiler `code_稍微包裝`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
int dp[2][145] = {1}; //dp[0][0] = 1, 16 * n / m <= 144
int main() {
int n, m; const int num[4] = {1, 2, 4, 8};
const string tile = "SQCM";
cin >> n >> m;
int p = 16 * n / m;
string w; cin >> w;
const int len = w.size();
for (size_t i = 0; i < w.size(); i++) {
for (int j = 1; j <= p; j++) {
bool flag = false;
if (w[i] == '?') dp[~i & 1][j] = 0, flag = true;
for (int k = 0; k < 4; k++) {
if (w[i] == tile[k] && j >= num[k]) {
dp[~i & 1][j] = dp[i & 1][j - num[k]];
flag = true; break;
}
else if (w[i] == '?' && j >= num[k]) {
dp[~i & 1][j] += dp[i & 1][j - num[k]];
dp[~i & 1][j] %= mod;
}
}
if (!flag) dp[~i & 1][j] = 0;
}
dp[~i & 1][0] = dp[~i & 1][p], dp[~i & 1][p] = 0;
}
cout << dp[len & 1][0];
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet