PCCA Winter Camp Day1
===
##### 2021.02.01
##### tags: `PCCA` `NCTU` `NYCU`
##### link: https://vjudge.net/contest/420760#overview
題解
===
## RPG Protagonist
> 兩人分別可帶重量不多於$p$、$f$的物品，
> 現有$cnt_{a}$件$A$物品，每件重$w_{a}$，
> $cnt_{b}$件$B$物品，每件重$w_{b}$，
> 求能帶走物品總數（無論種類）的最大值。
$p$、$f$、$w_{a}$、$w_{b}$數據範圍皆到$1e9$，因此能判斷多半不是背包問題。
觀察可發現$cnt_{a}$、$cnt_{b}$數據範圍僅到$2e5$，是可以枚舉的範圍。
枚舉第一個人拿幾個$A$物品（$[0, \frac{p}{w_{a}}]$），剩餘空間貪心拿盡量多的$B$物品，而第二個人則先拿剩餘物品中較輕的物品，拿完再拿較重的物品。
## Perfect party
> 有$m$個物品，每件有重量$w_{i}$跟價值$v_{i}$兩個屬性，
> 且有$k$組關係，說明$X$物品跟$Y$物品在同一個集合中。
> 現可帶走重量不多於$n$的物品，
> 但要求每個集合至少要帶走一個物品，
> 求可獲取價值的最大值。
> 若無解，則輸出"trash problem"。
先用並查集判別物品集合，再做背包取物品。
分組背包：（至少選一個）
- $dp[i][j]$表示，前$i$組物品，重量上限為$j$時的最大獲利。
- 初始化：（$-1$代表無解）
- $dp[0][j] = 0$, $j \in [0, n]$
- $dp[i][j] = -1$, $i \in [1, group]$, $j \in [0, n]$（$group$為組別數量）
- 轉移：
- 要決定$dp[i][j]$，為確保此組別有選，轉移一定要選擇物品，不能直接從$dp[i - 1][j]$轉移，也不能從無解的轉移。
- $dp[i][j] = max(dp[i][j], dp[i - 1][j - w[k]] + v[k], dp[i][j - w[k]] + v[k])$，$j \geq w[k]$
- 遍歷順序：
```cpp
for (int i = 1; i <= 組別數量; i++)
for (int k = 0; k < 組內物品數量; k++)
for (int j = n; j > -1; j--)
轉移;
```
- $dp[group][n]$即為答案。
## Perfect walker
> 給一個樹形圖，
> 從任意點出發遍歷，
> 求最短路徑。
對一樹形圖，從任意點出發遍歷再回到原點的路徑長為兩倍的路徑和。
因題目不用回到原點，故考慮省下最長距離為樹形圖中最遠點距離。
最短路徑 = 2 * 路徑和 - 樹的直徑
## Perfect student
> 給一個$n$個點、$m$個邊的有向圖，
> 若點$A$被標記，
> 則點$A$指向的點也被標記，
> 求選擇標的最少幾個點，
> 可使所有點都被標記。
由題意可知，一個強聯通分量中任意點被標記，等價於全部點被標記，因此可用kosaraju或tarjan將一個強聯通分量縮為一點。
縮點後可得一有向無環圖，入度為0的點一定會被選擇，不然該點不可能被標記，反之入度不為0的點，一定會透過其他點被標記，因此入度為0的點數即為答案。
## Intervals
> 給定$n$個區間，
> 每個區間$[a_{i}, b_{i}]$上至少有$c_{i}$個不重複的點屬於集合$s$，
> 要滿足所有條件，
> 求問$s$中最少點數。
令$d[i]$，為前$i$個點選擇的點數，則條件轉化為差分約束的形式：
1. $d[b_{i}] - d[a_{i} - 1] \geq c_{i}$
2. $d[i] - d[i-1] \geq 0$
3. $d[i-1] - d[i] \geq -1$
由於為$\geq$，故差分約束建圖後做最長路即為解。
## Radar Installation
> 給$n$個點和雷達距離$d$，
> 之後給$n$個點的$x$跟$y$，
> 雷達站都要建在$X$軸，
> 輸出總共需要幾個雷達站才能完全覆蓋所有點，
> 如果無法覆蓋則輸出$-1$。
可以先判如果有點的$y$座標絕對值$\geq d$的話就無法完全覆蓋。
算出每個點的覆蓋區間，對所有點的區間左界做排序，之後由左到右做Greedy。
Greedy的方法：（令$cur$為現在建雷達站的座標）
1. 如果此點的左區間$\leq cur$，則$cur$取此點的右區間和$cur$的最小值。
2. 如果此點的左區間$> cur$，表示要新建一個雷達站，且建立在此點的右區間。
## Stacking Boxes
> 有$n$個$m$維度的箱子，
> 要找出最多層的巢狀箱子，
> 裡面的箱子每個維度的邊長都要小於外面的箱子的邊長。
> 輸出最多幾層以及由內而外的順序。
先把每個箱子的維度做排序，如果$A$箱可以放進$B$箱的話，表示重新排序後，$B$的每個維度都要大於$A$。
可以利用 $O(n^2m)$ 方法建圖，如果$A$可以放進$B$，則建立一條邊由$A$指向$B$，最後再從入度為$0$的點開始移除，並記錄連結，即可得最長路徑。
## Walk Through the Forest
> 有$n$個點、$m$條邊的有權無相圖，
> 從$V_1$出發走到$V_2$有條件地走，有幾種走法。
> 條件為如果要從$A$點走到$B$點，
> 則必須存在一條$B$走回$V_2$的路徑比$A$走回$V_2$的所有路徑都短。
這題先求出所有點到$V_2$的最短路，由於圖無向，也就是$V_2$到所有點的最短路。然後再建立新的圖如果$A$到$V_2$的最短路大於$B$到$V_2$的最短路，則建立一條有向邊$A$到$B$。之後再用$dfs$來計算總共有幾種走法。
## Knight Moves
> 給兩個西洋棋上的座標，
> 看騎士從一個點到另外一個點最少需要幾步。
騎士可以走$(2, 1) (2, -1) (-2, 1) (-2, -1) (1, 2) (1, -2) (-1, 2) (-1, -2)$，用$queue$做$bfs$即可得到答案。
## Collectors Problem
> 有$N$個人(含Bob)和$M$種貼紙，
> 每個人手上都有不同種類及張數的貼紙，
> Bob要和別人交換使他有最多種類的貼紙。
> 交換規則：Bob給其他人的貼紙是其他人沒有的，其他人給Bob的貼紙是其他人多餘的(至少$2$張)，且其他人只與Bob交換。
把題目轉成網路圖：
1. 源點(Bob) → 每種貼紙：容量為Bob所擁有的貼紙數。
2. 每種貼紙 → 其他人：如果那個人沒有此貼紙的話容量為$1$，否則為$0$。
3. 其他人 → 每種貼紙：如果那個人貼紙的數量$\geq 2$，則容量為此人所擁有的此貼紙數$-1$，否則為$0$。
4. 每種貼紙 → 匯點：容量為$1$。
找出圖的最大流就是答案了。
## Lucky array
> 維護一個array，
> 如果數字裡沒有$4$跟$7$以外的數字就是幸運數字，
> $count\ a\ b$：要找$a$到第$b$個數有幾個幸運數字。
> $add\ a\ b\ c$：要把第$a$到第$b$個數都加上$c$
用$fenwick\ tree$紀錄每個數字是否為$lucky\ number$，是為$1$、不是為$0$。
區間修改時用$O(n)$的方法修改。
經hank55663指正：
幸運數總共有$30$個，每次用線段樹作區間加值，然後紀錄每個數離下一個幸運數的距離，若超過的話直接更改，因此每個數最多被硬改$30$次。
複雜度：$O((30n+q)logn)$。
用線段樹的方法請參考原題解：https://codeforces.com/blog/entry/2956
Sign in with Wallet
Connect another wallet