### 110 學年度師大附中資訊學科能力競賽
# 上機測驗 題解
joylintp / WiwiHo
---
<!-- .slide: data-background="https://i.imgur.com/HruvEmz.jpg" -->
<font color="black">
<font size=7><b> Virtual to LIVE (VTuber) </b></font>
<font size=6><b> joylintp </b></font>
</font>
----
### Virtual to LIVE
單推指數 $B = \max_{x \in v}\frac{c_x}{N}$
→ $max_{x \in v}c_x = N$ 時 $B$ 有最大值
→ 輸出 $N$ 個相同的名字時 $B=1$
<font color="lightgreen">100 / 100</font>
----
```cpp=
#include<bits/stdc++.h>
using namespace std;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
while (N--)
cout << "Ninomae Ina\'nis\n";
return 0;
}
```
----
### Virtual to LIVE - 一些廢話
* 題本內只列出了 $15$ 個 VTuber
* checker 內一共有 $51$ 個可以輸出的 VTuber
* 輸出其中 $20$ 個 VTuber 拿到滿分會得到彩蛋
![](https://i.imgur.com/vMIm2HQ.png)
----
### Virtual to LIVE - 一些廢話
拿到滿分的人輸出的 VTuber:
* Ninomae Ina'nis:10
* Hoshimachi Suisei:3
* Nanashi Mumei:3
* Gawr Gura:2
* Kizuna AI:2
* Tokino Sora:2
---
<!-- .slide: data-background="https://i.imgur.com/9tGEVqH.jpg" -->
<font color="black">
<font size=7><b> 貪吃蛇 (Snake) </b></font>
<font size=6><b> WiwiHo </b></font>
</font>
----
## 貪吃蛇 - Subtask 2
蛇只會往同一個方向移動
→ 在繞一圈回到原點前長度每次增加 $1$
→ 撞到後長度固定為 $N$
→ 第 $i$ 個答案為 $\min(N, i+1)$
<font color="yellow">5 / 100</font>
----
## 貪吃蛇 - Subtask 3
蛇只會往上或往下移動
設目前長度為 $L$
→ 若往前一步的反方向移動,則長度變為 $2$
→ 否則長度變為 $\min(N, L+1)$
<font color="yellow">7 / 100</font>
----
## 貪吃蛇 - Subtask 4
使用 $N \times N$ 的陣列記錄每一格被蛇佔據的時間
→ 若新走到的格子沒有被佔據則將該格的時間更新
→ 若被佔據則掃過每個格子,將佔據時間比該格早的格子清空
時間複雜度 $O(N^2M)$
<font color="yellow">12 / 100</font>
----
## 貪吃蛇 - Subtask 5
使用 $N \times N$ 的陣列記錄每一格被蛇佔據的時間
將目前蛇佔據的格子用 queue 維護
→ 若沒有被佔據則更新該格時間,並 push 進 queue
→ 若被佔據則一直 pop 到該格並同時清空格子
時間複雜度 $O(N^2 + M)$
<font color="yellow">(12 + 21) / 100</font>
----
## 貪吃蛇 - Subtask 6
~~使用陣列記錄每一格被蛇佔據的時間~~
使用 map 或 set 等資料結構維護
時間複雜度 $O(M \log M)$
<font color="lightgreen">100 / 100</font>
----
```cpp=
#include <bits/stdc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
using namespace std;
using pii = pair<int, int>;
int main(){
StarBurstStream
int n, m, x, y;
cin >> n >> m >> x >> y;
x--; y--;
string s;
cin >> s;
set<pii> st;
st.insert(mp(x, y));
map<char, pii> dir;
dir['R'] = mp(0, 1);
dir['L'] = mp(0, -1);
dir['U'] = mp(-1, 0);
dir['D'] = mp(1, 0);
queue<pii> q;
q.push(mp(x, y));
for(char i : s){
x += dir[i].F;
y += dir[i].S;
x = (x % n + n) % n;
y = (y % n + n) % n;
if(st.find(mp(x, y)) != st.end()){
while(true){
pii tmp = q.front();
q.pop();
st.erase(tmp);
if(tmp == mp(x, y)) break;
}
}
st.insert(mp(x, y));
q.push(mp(x, y));
cout << q.size() << "\n";
}
return 0;
}
```
---
<!-- .slide: data-background="https://i.imgur.com/gcnsWQc.jpg" -->
<font color="black">
<font size=7><b> 入社手續 (Procedure)</b></font>
<font size=6><b> WiwiHo </b></font>
</font>
----
### 入社手續
將文件間的關係建成一張有向圖 $G$:
對於節點 $v$,若存在 $a_{u,j,k} = u$,則建一條邊 $(u,v)$
由於文件不會循環,故 $G$ 為一張 DAG
其中邊數 $|E| = \Sigma C_{i,j}$,點數 $|V| = N$
----
### 入社手續 - Subtask 3
$K \le 1$
→ 對於 $K = 0$ 的文件可以直接申請
→ 對於 $K = 1$ 的文件 $u$,只須申請其中一份 $a_{u,1,j}$
→ 求從各 $K=0$ 的文件到 $N$ 的最短路徑
時間複雜度 $O(|E| + |V| \log |V|)$
<font color="yellow">17 / 100</font>
----
### 入社手續 - Subtask 4
$C_{u,j} = 1$
→ 在申請 $u$ 之前需要先申請所有連到 $u$ 的文件
→ 拓樸排序後計算每個節點的答案
時間複雜度 $O(|E| + |V|)$
<font color="yellow">26 / 100</font>
----
### 入社手續 - Subtask 5
設 $dp[u]$ 為拿到第 $u$ 份文件的最早時間,
* 初始化 $dp[u] = \infty$
* $dp[v]=\max_{1\leq i \leq K_v}\{\min_{1 \leq j \leq C_{v,i}} \{ dp[j] \}\} + T_v$
更新 $N$ 輪後即可得到答案
時間複雜度 $O(|V|(|E| + |V|))$
<font color="yellow">(9 + 12) / 100</font>
----
### 入社手續 - Subtask 6
$G$ 為一張 DAG
→ 將 $dp[u]$ 的更新順序改為 $G$ 的拓樸排序
時間複雜度 $O(|E| + |V|)$
<font color="lightgreen">100 / 100</font>
----
```cpp=
#include <bits/stdc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define eb(a) emplace_back(a)
using namespace std;
typedef long long ll;
const ll LLMAX = 1LL << 60;
int main(){
StarBurstStream
int n;
cin >> n;
vector<int> tm(n + 1);
for(int i = 1; i <= n; i++) cin >> tm[i];
vector<vector<vector<int>>> a(n + 1);
vector<vector<int>> g(n + 1);
vector<int> deg(n + 1);
for(int i = 1; i <= n; i++){
int K;
cin >> K;
a[i].resize(K);
for(int j = 0; j < K; j++){
int c;
cin >> c;
a[i][j].resize(c);
for(int k = 0; k < c; k++){
cin >> a[i][j][k];
g[a[i][j][k]].eb(i);
deg[i]++;
}
}
}
queue<int> q;
for(int i = 1; i <= n; i++){
if(deg[i] == 0) q.push(i);
}
vector<ll> dp(n + 1);
while(!q.empty()){
int now = q.front();
q.pop();
for(auto& i : a[now]){
ll mn = LLMAX;
for(int j : i){
mn = min(mn, dp[j]);
}
dp[now] = max(dp[now], mn);
}
dp[now] += tm[now];
for(int i : g[now]){
deg[i]--;
if(deg[i] == 0) q.push(i);
}
}
cout << dp[n] << "\n";
return 0;
}
```
----
### 入社手續 - Extra
如果 $G$ 不是 DAG 要怎麼作?
---
<!-- .slide: data-background="https://i.imgur.com/SpLNDH2.jpg" -->
<font color="black">
<font size=7><b> 船帆 (Sail) </b></font>
<font size=6><b> WiwiHo </b></font>
</font>
----
### 船帆
當角度為 $\theta$ 時
成本為 $f(\theta)=L(a\sin\theta + b\cos\theta)$
----
### 船帆 - Subtask 2
若 $a = 0$
→ $f(\theta) = b\cos\theta$
若 $b = 0$
→ $f(\theta) = a\sin\theta$
可以直接使用反三角函數求出解
<font color="yellow">13 / 100</font>
----
### 船帆 - Subtask 3
$a > b$,且 $\beta \approx \frac{\pi}{4}$
→ $f(\theta)$ 在 $[\alpha, \beta]$ 會是遞增的
→ 對 $\theta$ 二分搜
<font color="yellow">25 / 100</font>
----
### 船帆 - Subtask 4
$a = b$
→ $f(\theta)$ 最大值發生在 $\theta = \frac{\pi}{4}$
→ 分別對最大值兩側二分搜,找出在 $[\alpha, \beta]$ 內的解
<font color="yellow">29 / 100</font>
----
### 船帆 - Subtask 5
$f(\theta)$ 為一個中間高的單峰函數
→ 三分搜找出 $f(\theta)$ 最大值
→ 分別對最大值兩側二分搜,找出在 $[\alpha, \beta]$ 內的解
<font color="lightgreen">100 / 100</font>
----
```cpp=
#include <bits/stdc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long double ld;
ld PI = acos(-1);
double eps = 1e-8;
double anseps = 1e-4;
int L, a, b;
ld c, alp, bt;
ld f(ld x){
return L * (a * sin(x) + b * cos(x));
}
void solve(){
cin >> L >> a >> b >> c >> alp >> bt;
ld l = alp, r = bt;
while(r - l > eps){
ld m1 = (l * 2 + r) / 3;
ld m2 = (l + r * 2) / 3;
if(f(m1) < f(m2)) l = m1;
else r = m2;
}
ld mid = l;
if(f(alp) - anseps <= c && c <= f(mid) + anseps){
l = alp, r = mid;
while(r - l > eps){
ld m = (l + r) / 2;
if(f(m) < c) l = m;
else r = m;
}
if(abs(f(l) - c) <= anseps){
cout << fixed << setprecision(20) << l << "\n";
return;
}
}
if(f(mid) + anseps >= c && c >= f(bt) - anseps){
l = mid, r = bt;
while(r - l > eps){
ld m = (l + r) / 2;
if(f(m) > c) l = m;
else r = m;
}
if(abs(f(l) - c) <= anseps){
cout << fixed << setprecision(20) << l << "\n";
return;
}
}
assert(false);
}
int main(){
StarBurstStream
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
```
----
### 船帆 - 一元二次方程式解
設垂直船桅長度為 $x$,則水平木桿長度為 $\frac{c - ax}{b}$
列出關係式:$x^2 + (\frac{c - ax}{b})^2 = L^2$,
求出 $x$ 後算出 $\theta$,取在 $[\alpha, \beta]$ 內的解即可
----
### 船帆 - 三角函數解
疊合三角函數:
$f(\theta) = L(a\sin\theta + b\cos\theta) = L\sqrt{a^2+b^2}\sin(\theta+\theta')$
($\theta' = \arccos\frac{a}{\sqrt{a^2+b^2}}$)
令 $\gamma = \arcsin\frac{c}{L\sqrt{a^2+b^2}}$,
則兩組解分別為 $\gamma - \theta'$ 及 $\pi - \gamma - \theta'$,
取在 $[\alpha, \beta]$ 內的解即可
---
<!-- .slide: data-background="https://i.imgur.com/UqUBRAv.png" -->
<font color="black">
<font size=7><b> 手鍊 (Bracelet) </b></font>
<font size=6><b> joylintp </b></font>
</font>
----
### 手鍊 - Subtask 2
列出每顆珍珠的顏色
枚舉 $l$,在移動 $r$ 的過程中同時檢查手鍊是否合法
時間複雜度 $O((\Sigma d_i)^2)$
<font color="yellow">9 / 100</font>
----
### 手鍊 - Subtask 3
設 $l$ 在第 $L$ 段,$r$ 在第 $R$ 段,枚舉 $L, R$
若 $L = R$ 則可選擇的方式有 $\frac{d_L(d_L - 1)}{2}$ 種
----
### 手鍊 - Subtask 3 (cond.)
若 $L + 1 = R$,則必須符合 $c_L < c_R$ 才能選擇,
若 $d_L \le d_R$,則可選擇的方式有
$\Sigma_{i=1}^{d_L}(d_R - i + 1) = \frac{d_L(d_R + d_R - d_L + 1)}{2}$ 種
若 $d_L > d_R$,則可選擇的方式有
$\Sigma_{i=1}^{d_R}i = \frac{d_R(d_R + 1)}{2}$ 種
----
### 手鍊 - Subtask 3 (cond.)
若 $L < R$ 則必須符合以下條件才能選擇:
* $c_L < c_{L+1} < \ldots < c_R$
* $d_{L+1} \le d_{L+2} \le \dots \le d_R$
有 $\min(d_L, d_{L+1}) \times (d_R - d_{R - 1} + 1)$ 種選擇方式
總複雜度 $O(K^2)$
<font color="yellow">(9 + 12) / 100</font>
----
### 手鍊 - Subtask 5
$d_i = 1$
→ 對於連續遞增的 $c_i$,可選擇任兩顆作為 $l, r$
→ 設連續遞增的 $c_i$ 長分別為 $x_1, x_2, \ldots, x_k$,
則答案為 $\Sigma_{i=1}^{k}\frac{x_i(x_i - 1)}{2}$
時間複雜度 $O(K)$
<font color="yellow">7 / 100</font>
----
### 手鍊 - Subtask 4
$c_i < c_{i+1}$
→ 不須考慮顏色遞增,只須確保各段珍珠的數量
先假設只有一顆珍珠也是合法的手鍊
設 $dp1[i]$ 為以第 $i$ 段最左側那顆為 $l$ 的數量,則:
$dp1[i] = \begin{cases}
d_i &, i = K \lor d_i > d_{i+1}\\
d_i + (dp1[i+1] - d_i + 1) &, otherwise\\
\end{cases}$
----
### 手鍊 - Subtask 4 (cond.)
設 $dp2[i]$ 為以第 $i$ 段任意一顆為 $l$ 的數量,則:
$dp2[i] = \begin{cases}
\frac{d_i(d_i + 1)}{2} &, i = K\\
(dp1[i+1] + 1) \times d_i &, d_i \le d_{i+1}\\
(dp1[i+1] + 1) \times d_i + \frac{(d_i + d_{i+1} + 1)(d_i - d{i+1})}{2} &, otherwise\\
\end{cases}$
$\Sigma dp2[i]$ 即為答案
時間複雜度 $O(K)$
<font color="yellow">17 / 100</font>
----
### 手鍊 - Subtask 7
將序列拆成各段連續遞增的 $c_i$,
分別進行 Subtask 4 的 DP 即可求出答案
<font color="lightgreen">100 / 100</font>
----
```cpp=
#include<bits/stdc++.h>
using namespace std;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int K;
cin >> K;
int N = 0;
vector<int> c(K), d(K);
for (int i = 0; i < K; i++)
cin >> c[i] >> d[i], N += d[i];
vector<long long> dp1(K);
for (int i = K - 1; i >= 0; i--)
if (i == K - 1 || c[i] > c[i + 1] || d[i] > d[i + 1])
dp1[i] = d[i];
else
dp1[i] = dp1[i + 1] + 1;
vector<long long> dp2(K);
for (int i = K - 1; i >= 0; i--)
if (i == K - 1 || c[i] > c[i + 1])
dp2[i] = dp1[i] * (dp1[i] + 1) / 2;
else if (d[i] <= d[i + 1])
dp2[i] = (dp1[i + 1] + 1) * d[i];
else
dp2[i] = (dp1[i + 1] + 1) * d[i + 1] + (long long)(d[i] + d[i + 1] + 1) * (d[i] - d[i + 1]) / 2;
long long ans = 0;
for (long long i : dp2)
ans += i;
cout << ans - N << '\n';
return 0;
}
```
---
<!-- .slide: data-background="https://i.imgur.com/1ABDhZh.jpg" -->
<font color="black">
<font size=7><b> 快艇骰子 (Yacht) </b></font>
<font size=6><b> joylintp </b></font>
</font>
----
### 快艇骰子 - Subtask 2
$N=3$
→ 投擲結束,選擇能得最高分的役種即可
$S=$`111111000000`
→ 可以選擇的役種只有前六個
輸出 $1$ 到 $6$ 之中點數乘以數量最大者
<font color="yellow">3 / 100</font>
----
### 快艇骰子 - Subtask 3
$N=3$
→ 投擲結束,選擇能得最高分的役種即可
→ 仔細實作各役種判斷
<font color="yellow">(3 + 8) / 100</font>
----
### 快艇骰子 - Subtask 4
$N=2$
→ 選擇要保留哪些骰子
→ 枚舉剩下投擲的骰子的點數情況,計算得分期望值
→ 選擇期望值最高的保留組合
骰子保留組合:$2^5 = 32$
剩餘骰子的點數情況:不超過 $6^5 = 7776$
$32 \times 7776 \approx 2.5 \times 10^5$ → 暴力枚舉
<font color="yellow">(3 + 8 + 24) / 100</font>
----
### 快艇骰子
骰子的順序不重要
→ $[1, 2, 3, 1, 6], [1, 1, 2, 3, 6]$ 是一樣的
實際上一到五顆骰子點數的組合數分別只有
$6, 21, 56, 126, 252$ 種
→ 預處理每種骰子組合的出現機率
----
### 快艇骰子 - Subtask 5
$N=1$
→ 比 $N=2$ 多重複一次選擇及投擲的過程
→ 只枚舉各個組合,再將期望值乘上出現的機率
骰子保留組合:$2^5 = 32$
剩餘骰子的點數情況:不超過 $252$
$(32 \times 252)^2 \approx 6.5 \times 10^7$ → 暴力枚舉
<font color="yellow">(3 + 8 + 24 + 20) / 100</font>
----
### 快艇骰子 - Subtask 7
$N=0$
→ 多枚舉一次骰子的點數組合
→ 儲存每個狀態 $(n, S)$ 的答案
$n$,目前投擲次數:$3$
$S$,骰子點數集合:不超過 $252$
可能的轉移:不超過 $32 \times 252 = 8064$
$3 \times 252 \times 32 \times 252 \approx 6 \times 10^6$
<font color="lightgreen">100 / 100</font>
----
```cpp=
#include<bits/stdc++.h>
using namespace std;
vector<bool> yk(12);
vector<double> ans(566667, -1);
vector<pair<vector<int>, double>> pos[6];
int hh(int n, vector<int> *d)
{
int ret = n;
for (int &i : *d)
ret = ret * 10 + i;
return ret;
}
double solve(int n, vector<int> d)
{
if (ans[hh(n, &d)] > -1)
return ans[hh(n, &d)];
if (n == 3)
{
int ret = 0, cnt[6] = {}, sum = 0;
for (int &i : d)
cnt[i - 1]++, sum += i;
vector<int> vc;
for (int i = 0; i < 6; i++)
if (cnt[i])
vc.push_back(cnt[i]);
sort(vc.begin(), vc.end(), greater<int>());
/// Aces, Deuces, Threes, Fours, Fives, Sixes
for (int i = 0; i < 6; i++)
if (yk[i])
ret = max(ret, cnt[i] * (i + 1));
/// Choice
if (yk[6])
ret = max(ret, sum);
/// 4 of a Kind
if (yk[7])
if (vc[0] >= 4)
ret = max(ret, sum);
/// Full House
if (yk[8])
if (vc[0] == 5 || (vc[0] == 3 && vc[1] == 2))
ret = max(ret, sum);
/// S. Straight
if (yk[9])
if ((cnt[0] && cnt[1] && cnt[2] && cnt[3]) || (cnt[1] && cnt[2] && cnt[3] && cnt[4]) || (cnt[2] && cnt[3] && cnt[4] && cnt[5]))
ret = max(ret, 15);
/// B. Straight
if (yk[10])
if ((cnt[0] && cnt[1] && cnt[2] && cnt[3] && cnt[4]) || (cnt[1] && cnt[2] && cnt[3] && cnt[4] && cnt[5]))
ret = max(ret, 30);
/// Yacht
if (yk[11])
if (vc[0] == 5)
ret = max(ret, 50);
return ans[hh(n, &d)] = ret;
}
if (n == 0)
{
double ret = 0;
for (auto &p : pos[5])
ret += solve(1, p.F) * p.S;
return ans[hh(n, &d)] = ret;
}
if (n == 1 || n == 2)
{
double ret = 0;
for (int i = 0; i < 32; i++)
{
int t = i, cc = 0;
vector<int> nd;
for (int j = 0; j < 5; j++, t /= 2)
if (t % 2)
nd.push_back(d[j]), cc++;
nd.resize(5);
double sum = 0;
for (auto &p : pos[5 - cc])
{
for (int j = cc; j < 5; j++)
nd[j] = p.F[j - cc];
sum += solve(n + 1, nd) * p.S;
}
ret = max(ret, sum);
}
return ans[hh(n, &d)] = ret;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
pos[0].push_back(MP(vector<int>(0), 1));
for (int i = 1; i <= 5; i++)
{
int ttl = 1;
for (int j = 0; j < i; j++)
ttl *= 6;
map<vector<int>, int> cnt;
for (int j = 0; j < ttl; j++)
{
int t = j;
vector<int> v;
for (int k = 0; k < i; k++)
v.push_back(t % 6 + 1), t /= 6;
sort(v.begin(), v.end()), cnt[v]++;
}
for (auto p : cnt)
pos[i].push_back(MP(p.F, (double)p.S / ttl));
}
int N;
cin >> N;
vector<int> d(5);
for (int &i : d)
cin >> i;
string S;
cin >> S;
for (int i = 0; i < 12; i++)
yk[i] = (S[i] - '0');
cout << fixed << setprecision(16) << solve(N, d) << '\n';
return 0;
}
```
{"metaMigratedAt":"2023-06-16T11:17:45.198Z","metaMigratedFrom":"YAML","title":"110 學年度師大附中資訊學科能力競賽 上機測驗 題解","breaks":true,"contributors":"[{\"id\":\"6b95215f-91a7-4eaf-bcfe-d43740108f96\",\"add\":28477,\"del\":12733}]"}