110 北市賽熱身賽題解

--- 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))$ :::