---
tags: 初階班
---
# 110學年度上學期初階班期中考
## 考試須知
### 時間
考試開始時間:$2021/11/5\; 17:00\; (GMT+8)$
考試結束時間:$2021/11/5\; 20:30\; (GMT+8)$
### 範圍
- 輸入輸出 ~ 陣列
### 配分
- 基本輸入輸出 : $1*100$
- 資料型態 : $1*100$
- if、迴圈 : $4*100$
- 陣列 : $3*100 +1*90$
- 防破台 : $1*10$
- 共 $1000$ 分
### 注意事項
- 考試期間會切網路且不可以使用手機等3C產品
- 可以使用紙筆、計算機
- 考試期間不可以和他人討論考試內容
- 如果對題目內容有問題都可以問幹部
- 吃飯時間可以使用手機但不能查程式相關東西
## 題解
考完應該就會公布，如果我來得及打完 :poop:
### 競賽用hello world
[.](http://203.64.191.163/ShowProblem?problemid=a196)
老樣子，送分題
:::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")
```
:::
### I. 為各位的期中考獻上祝福
這題就只是輸入$a, b$
輸出$a + b$
不過有個陷阱
$a, b\in int$不代表$a+b \in int$
所以要用$long\; long$存
不然會$59$% :poop:
:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
long long a, b;
cin >> a >> b;
cout << a + b;
}
```
:::
### H. 空間向量
[.](http://203.64.191.163/ShowProblem?problemid=a692)
就是簡單的 if 跟 while
有上課應該就會寫
公式我都很好心的附上了
:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
int m, x1, y1, z1, x2, y2, z2;
while (cin >> m >> x1 >> y1 >> z1 >> x2 >> y2 >> z2) {
if (!m) cout << (x1 * x2) + (y1 * y2) + (z1 * z2) << '\n';
else cout << (y1 * z2) - (y2 * z1) << ' ' << (z1 * x2) - (z2 * x1) << ' ' << (x1 * y2) - (x2 * y1) << '\n';
}
}
```
:::
### G. 哭啊，無情沒收
[.](http://203.64.191.163/ShowProblem?problemid=a703)
這一題也是簡單的 if 跟 for
有很多種方法
我自己是將放學時間和睡覺時間都轉為分鐘
那就比較方便計算
只是如果睡覺時間是0點以後
記得分鐘數要加$1440$
:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
int h1, m1, h2, m2, n, t;
cin >> h1 >> m1 >> n >> h2 >> m2;
int min1 = h1 * 60 + m1;
for (int i = 0; i < n; i++) {
cin >> t;
min1 += t;
}
int min2 = 0;
if (h2 < 6 || (h2 == 6 && m2 == 0)) min2 += h2 * 60 + m2 + 1440;
else min2 += h2 * 60 + m2;
if (min2 - min1 > 0) cout << min2 - min1;
else cout << "那我也要睡啦";
return 0;
}
```
:::
### F. さあ、ゲームを始めよう！
[.](http://203.64.191.163/ShowProblem?problemid=a706)
這題是本次考試最需要動腦的題目
~~其實只是簡單的數論~~
防止考試時你們看不到照片，我把照片丟上來了
如果看懂題目
你可以先把總天數轉為二進位
轉為二進位就很好理解了
例如$7$轉為二進位就是
$0111$
那如果要將2付出去，需要找回1
如果要將4付出去，需要找回3，也就是2加1
以此類推
公式就是$\log_2 總天數$，然後向下取整
:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
int n;
while (cin >> n) cout << __lg(n) << '\n';
}
```
:::
### E. 所謂曖昧
[.](http://203.64.191.163/ShowProblem?problemid=a690)
~~這題應該是初階教學暈船時出的題目~~
就是需要閱讀理解的題目
看懂以後用很多 if 就可以過了
**若此時 k 超出範圍則回到端點值進行下次運算**
然後$1 \leq k \leq 9$
所以這句會的意思是說
當$k$小於$1$時，把$k$設為$1$
當$k$大於$9$時，把$k$設為$9$
:::spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
int n;
while (cin >> n) {
int m, t = 0, k = 5;
int plus = 0, minus = 0;
while (n--) {
cin >> m;
k += (m - 5);
if (k > 3 && k < 7) plus++;
else minus++;
if (plus >= 3) t++, plus -= 3;
else if (minus >= 3) t--, minus -= 3;
if (k > 9) k = 9;
else if (k < 1) k = 1;
}
cout << t << '\n';
}
}
```
:::
### D. 拿餐大作戰
[.](http://203.64.191.163/ShowProblem?problemid=a685)
這一題就是簡單的二維陣列
可是要小心題目有陷阱
便當位置的表示是
**從上數下來第幾排，從右數到左第幾個**
不是從左到右 :poop:
:::spoiler code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
int n, m, x, y;
cin >> n >> m >> x >> y;
int arr[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> arr[i][j];
cout << arr[x - 1][m - y];
}
```
:::
### C. 一筆畫問題
[.](http://203.64.191.163/ShowProblem?problemid=a695)
這一題是用到陣列
~~很佛心了吧，一筆畫規則都給你說了~~
就是開一個陣列
存這個點被通過的次數
最後再判斷是否符合條件
::: spoiler `code`
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
int t;
cin >> t;
while (t--) {
int m, n;
cin >> m >> n;
int arr[m + 1] = {0};
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
arr[x]++, arr[y]++;
}
bool flag = false;
int ans = 0;
for (int i = 1; i <= m; i++) {
if (arr[i] % 2 != 0) ans++;
else if (arr[i] == 0) {
flag = true;
break;
}
}
if (!flag && (ans == 0 || ans == 2)) cout << "yes\n";
else cout << "no\n";
}
}
```
:::
### B. 吳乙己
[.](http://203.64.191.163/ShowProblem?problemid=a681)
這一題就只是區間和
~~只是被我用很油的題序包裝~~
一樣怕你們看不到照片
就是給你一串數字
問你某一段的數字總和
然後答案記得用 unsigned long long 存
然後這題有一個很機車的東西
因為它會詢問很多次
用for迴圈慢慢跑會只有80%
想要AC的話要用```前綴和```
一般來說
陣列是用來存每一項題目給你的數字
但```前綴和```是把前n項的和存在第n格陣列
這樣就會快上不少
::: spoiler `一般解 (80%)`
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
int main () {
int n, m;
cin >> n >> m;
ULL arr[n + 1];
int a;
cin >> a;
arr[0] = 0, arr[1] = a;
for (int i = 2; i < n + 1; i++) {
cin >> arr[i];
}
int x, y;
for (int i = 0; i < m; i++) {
ULL ans = 0;
cin >> x >> y;
for (int i = x; i <= y; i++) ans += arr[i];
cout << ans << '\n';
}
}
```
:::
~~然後80%的解如果加上io優化就可以到90%~~
::: spoiler `前綴和 (AC)`
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
int main () {
int n, m;
cin >> n >> m;
ULL arr[n + 1];
int a;
cin >> a;
arr[0] = 0, arr[1] = a;
for (int i = 2; i < n + 1; i++) {
cin >> a;
arr[i] = arr[i - 1] + a;
}
int x, y;
for (int i = 0; i < m; i++) {
cin >> x >> y;
cout << arr[y] - arr[x - 1] << '\n';
}
}
```
:::
### A. 果然我的高一平凡生活搞錯了。完
[.](http://203.64.191.163/ShowProblem?problemid=a680)
這一題就是防破台題
能30%的，為什麼要用遞迴ㄚㄚㄚ
能60%的，還算不錯
能90%的，非常電 ~~或有認真聽我之前的題解~~
能100%的，我嚴重懷疑你平常在裝弱，~~因為這題也是進階班的防破台題~~
**以下題解來自進階教學**
#### NA 30%
我們可以知道：$Hank$ 若經歷第 $i$ 個事件，他前一個事件必定是第 $(i - n - 1)$ ~ $(i - 1)$ 個事件。
而且他必經歷第 $0$ 個事件$\implies dp[0] = 1$
因此：
$\displaystyle \begin{cases} dp[0] = 1\\dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[1] + dp[0]\quad\quad if\quad 1\leq i\leq n + 1\\dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[i - n - 1]\quad\quad if\quad i > n + 1\\ \end{cases}$
然後用複雜度很高的遞迴寫(不包含$DP$ )
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
LL fib(int n, int k) {
if (n == 1) {
if (k < 0) return 0;
else if (k <= 1) return 1;
return (fib(n, k - 1) + fib(n, k - 2)) % mod;
}
else if (n == 2) {
if (k < 0) return 0;
else if (k <= 1) return 1;
else if (k == 2) return 2;
return (fib(n, k - 1) + fib(n, k - 2) + fib(n, k - 3)) % mod;
}
return 0;
}
int main() {
//cin.tie(nullptr), ios_base::sync_with_stdio(false);
int t, n, k;
cin >> t;
while (t--) {
cin >> n >> k;
cout << fib(n, k) << '\n';
}
}
```
:::
#### NA 60%
在 $dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[1] + dp[0]\quad\quad if\quad 1\leq i\leq n + 1$ 時
我們可以發現：
$dp[0] = 1 = 2^0,dp[1] = 1 = 2^0, dp[2] = dp[0] + dp[1] = 2 = 2^1\implies dp[i] = 2^{i - 1}$
然後這次用迴圈做：
:::spoiler `code_1`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
LL arr[100001];
LL sum(int l, int r) {
LL ret = 0;
for (; l <= r; l++) ret = (ret + arr[l]) % mod;
return ret;
}
int main() {
//cin.tie(nullptr), ios_base::sync_with_stdio(false);
int T, n, k;
cin >> T;
while (T--) {
cin >> n >> k;
for (int x = 0; x <= n; x++) arr[x] = pow(2, x);
for (int x = n + 1; x < k; x++)
arr[x] = sum(x - n - 1, x - 1);
cout << arr[k - 1] << '\n';
}
}
```
:::
:::spoiler `code_2`
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int main () {
ios::sync_with_stdio(0), cin.tie(0);
int m;
cin >> m;
while (m--) {
ll n, k;
cin >> n >> k;
vector <ll> vec(k + 1, 0);
vec[0] = 1;
for (ll i = 1; i < k + 1; i++) {
for (ll j = 1; j < min(i, n + 1) + 1; j++) {
vec[i] += vec[i - j];
vec[i] %= mod;
}
}
cout << vec[k] << '\n';
}
}
```
:::
#### NA 90 %
$i>n+1$ 時
$dp[i] = dp[i - 1] + dp[i - 2] + .............. + dp[i - n - 1]$
$dp[i-1] = \quad\quad\quad\; dp[i - 2] + dp[i - 3] + ... + dp[i-n-1]+dp[i - n - 2]$
兩式相扣
$\implies dp[i] - dp[i - 1] = dp[i - 1] - dp[i - n - 2]$
$\implies dp[i] = dp[i - 1]\times 2 - dp[i - n - 2]$
實作可以兩種：
1. 把空間滾動，只開長度為 $n + 2$ 的陣列
2. 開一個長度 $10^7$ 的陣列，不過注意資料型態要是 $int\implies$每次運算都要 $mod\;10^9 + 7$
注意 $(dp[i - 1]\times 2 - dp[i - n - 2]) \% mod$ 可能是負的。(因為 $dp[i - 1]$ 取完餘數後可能很小)
:::spoiler `code_1`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
int main() {
//cin.tie(nullptr), ios_base::sync_with_stdio(false);
int T, n, k;
cin >> T;
while (T--) {
cin >> n >> k;
LL arr[n + 2];
for (int x = 0; x <= n; x++) arr[x] = pow(2, x);
arr[n + 1] = 1;
for (int x = n + 1; x < k; x++) {
arr[x % (n + 2)] -= arr[(x - 1) % (n + 2)] * 2;
arr[x % (n + 2)] *= -1;
arr[x % (n + 2)] = (arr[x % (n + 2)] + mod * 2) % mod;
}
cout << arr[(k - 1) % (n + 2)] << '\n';
}
}
```
:::
:::spoiler `code_2`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int mod = 1e9 + 7;
int arr[10000001];
int main() {
//cin.tie(nullptr), ios_base::sync_with_stdio(false);
int T, n, k;
cin >> T;
while (T--) {
cin >> n >> k;
arr[0] = 1;
for (int x = 1; x <= n + 1; x++) arr[x] = pow(2, x - 1);
for (int x = n + 2; x <= k; x++)
arr[x] = ((2 * arr[x - 1] - arr[x - n - 2]) % mod + mod) % mod;
cout << arr[k] << '\n';
}
}
```
:::
#### AC
把前面幾個轉移式的條件整合一下：
$M = \left [ \begin{array}{ccc} 2^0 & 2^1 & 2^2 & ... & 2^n\end{array}\right]\left [ \begin{array}{ccc} 0 & 1 & 0 & 0 & 0 & ...\\0 & 0 & 1 & 0 & 0 & ...\\0 & 0 & 0 & 1 & 0 & ...\\ ⋮\\1 & 1& 1& 1& 1&...\end{array}\right]^{k - 1}$
(右陣列是一個大小為 $(n + 1)\times (n + 1)$ 的陣列)
然後用矩陣的方式運算，答案為 $M[0]$
:::spoiler `code_進階班`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr LL m = 1e9 + 7;
LL n;
vector<vector<LL>> I(21, vector<LL> (21, 0));
vector<vector<LL>> mat(const vector<vector<LL>> &x, const vector<vector<LL>> &y) {
vector<vector<LL>> ret(n + 1, vector<LL> (n + 1, 0));
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++)
ret[i][j] = (ret[i][j] + x[i][k] * y[k][j]) % m;
}
}
return ret;
}
vector<vector<LL>> mpow(vector<vector<LL>> x, LL y) {
vector<vector<LL>> ret = I;
for (; y; y >>= 1, x = mat(x, x)) {
if (y & 1) ret = mat(ret, x);
}
return ret;
}
int main() {
cin.tie(nullptr), ios_base::sync_with_stdio(false);
LL T, k;
cin >> T;
while (T--) {
cin >> n >> k;
vector<vector<LL>> A(n + 1, vector<LL> (n + 1, 0));
vector<vector<LL>> B(n + 1, vector<LL> (n + 1, 0));
for (int x = 0; x <= n; x++) {
A[0][x] = pow(2, x), I[x][x] = 1;
if (x < n) B[x + 1][x] = 1;
B[x][n] = 1;
}
A = mat(A, mpow(B, k - 1));
cout << A[0][0] << '\n';
}
return 0;
}
```
:::
:::spoiler `code_初階班`
```cpp=
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int m = 1000000007;
int main() {
LL T, n, k;
cin >> T;
while (T--) {
cin >> n >> k;
k--;
LL A[21][21], B[21][21], I[21][21], tmp[21][21];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
A[i][j] = B[i][j] = I[i][j] = 0;
}
for (int x = 0; x <= n; x++) {
A[0][x] = pow(2, x), I[x][x] = 1;
if (x < n) B[x + 1][x] = 1;
B[x][n] = 1;
}
while (k != 0) {
if (k % 2 == 1) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
tmp[i][j] = 0;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++)
tmp[i][j] = (tmp[i][j] + I[i][k] * B[k][j]) % m;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
I[i][j] = tmp[i][j];
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
tmp[i][j] = 0;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++)
tmp[i][j] = (tmp[i][j] + B[i][k] * B[k][j]) % m;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
B[i][j] = tmp[i][j];
}
k /= 2;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
tmp[i][j] = 0;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++)
tmp[i][j] = (tmp[i][j] + A[i][k] * I[k][j]) % m;
}
}
cout << tmp[0][0] << '\n';
}
return 0;
}
```
:::
::: spoiler `code_副初階教學`
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
vector <vector <ll>> quick (vector <vector <ll>> vec1,vector <vector <ll>> vec2, int n) {
vector <vector <ll>> tmp (n, vector<ll>(n, 0));
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++)
tmp[i][j] = (tmp[i][j] + (vec1[i][k] * vec2[k][j])) % mod;
return tmp;
}
int main () {
ios::sync_with_stdio(0), cin.tie(0);
int m;
cin >> m;
while (m--) {
ll n, k;
cin >> n >> k;
vector <vector <ll>> base (n + 1, vector<ll>(n + 1, 0));
vector <vector <ll>> pro (n + 1, vector<ll>(n + 1, 0));
for (int i = 0; i < n; i++)
base[0][i] = 1, base[i + 1][i] = 1, pro[i][i] = 1;
base[0][n] = 1, pro[n][n] = 1;
ll x = k - n - 1;
if (x <= 0) {
ll ans = 1;
for (int i = 0; i < k - 1; i++)
ans = ans * 2 % mod;
cout << ans << '\n';
}
else {
while (x != 1) {
if (x % 2 == 0) {
base = quick (base, base, n + 1);
x /= 2;
}
else {
pro = quick (pro, base, n + 1);
x--;
}
}
base = quick (base, pro, n + 1);
ll ans = 0;
for (int i = 0; i < n + 1; i++) {
ans = (ans + base[0][i] * (ll)pow(2, n - i)) % mod;
}
cout << ans << '\n';
}
}
}
```
:::
Sign in with Wallet
Connect another wallet