---
# System prepended metadata

title: 110 北市賽熱身賽 題解
tags: [比賽題解]

---

---
tags: 比賽題解
title: 110 北市賽熱身賽 題解
---

- 比賽連結: https://oj.lscsc.club/contest/1

:::info
# A. 病毒傳播
- 題目連結: https://oj.lscsc.club/contest/1/problem/1
:::
:::success
## 子測資一
(如果你會暴搜的話就能解這筆測資ww)
- bfs搜索
    - 每筆查詢裡面，對於每個帶原者，用bfs花 $O(m)$ 的時間找出與p的距離。距離p最近的，就是答案。
    - 複雜度: $O(nmq)$
- floyd-warshall
    - 三層for迴圈，直接找出所有點之間的距離:)
    - 複雜度: $O(n^3+q)$
:::

:::success
## 子測資二
我也不知道為啥要有這筆子測資www
- dijkstra
    - 如果有人不會用bfs但是會dijkstra的話，也可以過這筆測資喔XDD
:::

:::success
## 子測資三
- 還是bfs搜索
    - 預處理：把所有帶原者當作起點，使用bfs找到所有點到最近帶原者的距離。
    - 對於查詢，直接輸出答案：）
    - 複雜度: $O(n+m+q)$
:::

:::info
# B. 又被坑了
- 題目連結: https://oj.lscsc.club/contest/1/problem/2
:::

:::success
## 子測資一
- 枚舉+bfs
    - 如果今天只要你驗證一個有空缺的矩陣是否能被還原...
    - 驗證的方法，就是用bfs從只有必定能還原的地方出發，看看能不能還原整個矩陣，驗證複雜度 $O(nm)$
    - 那我們對於所有空缺，枚舉給高麗菜復原跟不給高麗菜復原兩種可能，所以一共有 $O(2^{nm})$ 種可能，驗證是否能復原以及計算給高麗菜的復原成本:)
    - 複雜度: $O(nm\times2^{nm})$
:::

:::success
## 子測資二
- 圖+dfs
    - 嘗試著把矩陣 $A$ 變成一個二分圖:如果 $A[i][j]=-1$，那我們就在圖中把兩個點 $x_i, y_j$ 中間連一條邊，邊權是 $B[i][j]$
    - 這樣我們得到一個帶權無向圖，有 $O(n+m)$ 個節點，還有 $O(nm)$ 條邊
    - 我們會發現，如果圖上有環，就沒辦法自行復原
    - 所以我們開始找環，找到環之後，就復原環上最便宜的那個邊:)
    - 找到一個環花時間 $O(nm)$ ，我們最多找 $O(nm)$ 次環，因為最差況下我們復原最多 O(nm) 個邊
    - 複雜度: $O(n^2m^2)$
:::

:::success
## 子測資三
- 圖+mst
    - 嘗試著把矩陣 $A$ 變成一個二分圖:如果 $A[i][j]=-1$，那我們就在圖中把兩個點 $x_i, y_j$ 中間連一條邊，邊權是 $B[i][j]$
    - 這樣我們得到一個帶權無向圖，有 $O(n+m)$ 個節點，還有 $O(nm)$ 條邊
    - 換個方式想，我們嘗試著找出最後要保留哪一些邊給自己復原。當然，這些點的邊權和盡可能大。
    - 然後我們發現，因為我們找到的圖不能有環，所以它是一棵樹。想到甚麼呢？就是最大生成樹啦！
    - 複雜度: $O(nm\times\log(nm))$
:::

:::info
# C. 基本傳染數
- 題目連結: https://oj.lscsc.club/contest/1/problem/3
:::

:::success
## 子測資一
- 直接計算
    - 用for迴圈分別計算所有 $R_0^i$ ，再用for迴圈把它們加起來
    - 複雜度: $O(n^2)$
:::
:::success
## 子測資二
- 普通優化計算
    - 用for迴圈與遞迴式 $R_0^i=R_0^{i-1}\times R_0$ 直接計算所有 $R_0^i$ ，再用for迴圈把它們加起來
    - 複雜度: $O(n)$
:::
:::success
## 子測資三
- 折半優化計算（快速冪）
    - 遞迴式如下:
        - 如果是奇數項，也就是 $N+1$ 是奇數的時候，就剪掉一項變成偶數項: $$\sum_{i=0}^NR_0^i=1+R_0\times\sum_{i=0}^{N-1}R_0^i$$
        - 如果是偶數項，也就是 $N+1$ 是偶數的時候，就直接拆半計算: $$\sum_{i=0}^NR_0^i=(R_0^{(N+1)/2}+1)\times\sum_{i=0}^{(N-1)/2}R_0^i$$
    - 複雜度: $O(\log{n})$
:::

:::info
# D. 電力公司經理的私心
- 題目連結: https://oj.lscsc.club/contest/1/problem/4
:::

:::success
## 子測資一、二
*子測資一二可能差別在一堆小優化ㄅ...不然我也不知道了XD*

- 模擬
    - 直接開個陣列模擬一下XD
    - 枚舉$m=\{2,3,4,5,...,N\}$，看看哪個能跑出$f(N,m)=1$
    - 複雜度: $O(n^3)$
:::
:::success
## 子測資三
- dp (約瑟夫問題)
    - 遞迴式 $f(N,m)=(f(N−1,m)+m)\%N$
    - 枚舉$m=\{2,3,4,5,...,N\}$，看看哪個能跑出$f(N,m)=1$
    - 複雜度: $O(n^2)$
:::

:::info
# E. 猴子去買菜
- 題目連結: https://oj.lscsc.club/contest/1/problem/5
- 這題很容易卡在輸入，可以用stringstream更直觀的輸入:)
:::

:::success
## 子測資一
- dp (背包問題)
    - 就是最經典的一維無限背包問題阿，只是做了點變化
    - $dp[i][j]$ 表示前i項組合包中買到至少j個份食材最少花錢數
    - $dp[i][j] = min\{dp[i-1][j-package[i].a\times x]+package[i].cost\}$
    - 記得用往後轉移的方式才不會超時喔！
    - 複雜度 $O(n\cdot a)$
:::
:::success
## 子測資二
- dp (還是背包問題)
    - 就是解三次背包問題XD
    - 複雜度 $O(n\cdot (a+b+c))$
:::
:::success
## 子測資三
- dp (還是背包問題)
    - 就是三個背包的背包問題XD
    - dp[i][j][k][l]表示前i項組合包中買到至少j個份a食材,至少k個份b食材,跟至少l個份c食材最少花錢數
    - $dp[i][j] = min\{dp[i-1][j-package[i].a\times x][k-package[i].b\times x][l-package[i].c\times x]+package[i].cost\}$
    - 複雜度 $O(n\cdot a\cdot b\cdot c))$
:::