上機測驗 題解

Virtual to LIVE

單推指數 \(B = \max_{x \in v}\frac{c_x}{N}\)
→ \(max_{x \in v}c_x = N\) 時 \(B\) 有最大值
→ 輸出 \(N\) 個相同的名字時 \(B=1\)

100 / 100

#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 拿到滿分會得到彩蛋

Virtual to LIVE - 一些廢話

拿到滿分的人輸出的 VTuber：

• Ninomae Ina'nis：10
• Hoshimachi Suisei：3
• Nanashi Mumei：3
• Gawr Gura：2
• Kizuna AI：2
• Tokino Sora：2

貪吃蛇 - Subtask 2

蛇只會往同一個方向移動
→ 在繞一圈回到原點前長度每次增加 \(1\)
→ 撞到後長度固定為 \(N\)
→ 第 \(i\) 個答案為 \(\min(N, i+1)\)

5 / 100

貪吃蛇 - Subtask 3

蛇只會往上或往下移動

設目前長度為 \(L\)
→ 若往前一步的反方向移動，則長度變為 \(2\)
→ 否則長度變為 \(\min(N, L+1)\)

7 / 100

貪吃蛇 - Subtask 4

使用 \(N \times N\) 的陣列記錄每一格被蛇佔據的時間
→ 若新走到的格子沒有被佔據則將該格的時間更新
→ 若被佔據則掃過每個格子，將佔據時間比該格早的格子清空

時間複雜度 \(O(N^2M)\)

12 / 100

貪吃蛇 - Subtask 5

使用 \(N \times N\) 的陣列記錄每一格被蛇佔據的時間
將目前蛇佔據的格子用 queue 維護
→ 若沒有被佔據則更新該格時間，並 push 進 queue
→ 若被佔據則一直 pop 到該格並同時清空格子

時間複雜度 \(O(N^2 + M)\)

(12 + 21) / 100

貪吃蛇 - Subtask 6

使用陣列記錄每一格被蛇佔據的時間
使用 map 或 set 等資料結構維護

時間複雜度 \(O(M \log M)\)

100 / 100

#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;
}

入社手續

將文件間的關係建成一張有向圖 \(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|)\)

17 / 100

入社手續 - Subtask 4

\(C_{u,j} = 1\)
→ 在申請 \(u\) 之前需要先申請所有連到 \(u\) 的文件
→ 拓樸排序後計算每個節點的答案

時間複雜度 \(O(|E| + |V|)\)

26 / 100

入社手續 - 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|))\)

(9 + 12) / 100

入社手續 - Subtask 6

\(G\) 為一張 DAG
→ 將 \(dp[u]\) 的更新順序改為 \(G\) 的拓樸排序

時間複雜度 \(O(|E| + |V|)\)

100 / 100

#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 要怎麼作？

船帆

當角度為 \(\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\)

可以直接使用反三角函數求出解

13 / 100

船帆 - Subtask 3

\(a > b\)，且 \(\beta \approx \frac{\pi}{4}\)
→ \(f(\theta)\) 在 \([\alpha, \beta]\) 會是遞增的
→ 對 \(\theta\) 二分搜

25 / 100

船帆 - Subtask 4

\(a = b\)
→ \(f(\theta)\) 最大值發生在 \(\theta = \frac{\pi}{4}\)
→ 分別對最大值兩側二分搜，找出在 \([\alpha, \beta]\) 內的解

29 / 100

船帆 - Subtask 5

\(f(\theta)\) 為一個中間高的單峰函數
→ 三分搜找出 \(f(\theta)\) 最大值
→ 分別對最大值兩側二分搜，找出在 \([\alpha, \beta]\) 內的解

100 / 100

#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]\) 內的解即可

手鍊 - Subtask 2

列出每顆珍珠的顏色
枚舉 \(l\)，在移動 \(r\) 的過程中同時檢查手鍊是否合法

時間複雜度 \(O((\Sigma d_i)^2)\)

9 / 100

手鍊 - 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)\)

(9 + 12) / 100

手鍊 - 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)\)

7 / 100

手鍊 - 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)\)

17 / 100

手鍊 - Subtask 7

將序列拆成各段連續遞增的 \(c_i\)，
分別進行 Subtask 4 的 DP 即可求出答案

100 / 100

#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;
}

快艇骰子 - Subtask 2

\(N=3\)
→ 投擲結束，選擇能得最高分的役種即可

\(S=\)111111000000
→ 可以選擇的役種只有前六個

輸出 \(1\) 到 \(6\) 之中點數乘以數量最大者

3 / 100

快艇骰子 - Subtask 3

\(N=3\)
→ 投擲結束，選擇能得最高分的役種即可
→ 仔細實作各役種判斷

(3 + 8) / 100

快艇骰子 - Subtask 4

\(N=2\)
→ 選擇要保留哪些骰子
→ 枚舉剩下投擲的骰子的點數情況，計算得分期望值
→ 選擇期望值最高的保留組合

骰子保留組合：\(2^5 = 32\)
剩餘骰子的點數情況：不超過 \(6^5 = 7776\)
\(32 \times 7776 \approx 2.5 \times 10^5\) → 暴力枚舉

(3 + 8 + 24) / 100

快艇骰子

骰子的順序不重要
→ \([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\) → 暴力枚舉

(3 + 8 + 24 + 20) / 100

快艇骰子 - 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\)

100 / 100

#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;
}