7.12 卷積 | 最小生成樹 prim

lc1900.模擬比賽
算出兩個指定選手最早和最晚能在第幾輪碰到。
還是建議dfs捏

模擬比賽，找出兩個特定選手（firstPlayer和secondPlayer）最早和最晚相遇的輪次。

1.?定義了一個“選手”結構體，包含兩個屬性a（戰斗力）和b（編號），并規定按b值排序。
2.?主函數里，根據總人數n設置模擬次數（人數越多模擬次數越多）。
3.?每次模擬時：
- 給所有選手隨機分配戰斗力，讓兩個特定選手戰斗力最高（確保他們能贏到最后相遇）。
- 模擬比賽：每輪讓第i名和第rest+1-i名選手對決，贏的留下。
- 檢查這一輪是否是兩個特定選手相遇，記錄最早和最晚的輪次。
4.?最后返回這兩個記錄的輪次。

簡單說就是通過多次模擬比賽，算出兩個指定選手最早和最晚能在第幾輪碰到。

struct node
{
int a , b;
bool operator <(const node &p)
{
return b < p.b;
}
}player[30];

class Solution {
public:
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer)?
{
srand(time(NULL));

? ? ? ? // 根據n的大小設置模擬次數
int N;
if(n <= 10)
N = 800;
else if (n <= 20)
N = 8000;
else N = 38000;

? ? ? ? int ans1 = 9999 , ans2 = 0 , rest , now;

while(N--)
{
// 剩余的運動員
rest = n;

? ? ? ? ? ? // 初始化戰斗力
for(int i = 1 ; i <= n ; i++)
{
player[i].a = rand() % 1075943;
player[i].b = i;
}
player[firstPlayer].a = 11000000;
player[secondPlayer].a = 10999999;

// 統計輪次
now = 1;

// 模擬比賽
while(rest > 1)
{
for(int i = 1 ; i <= rest / 2 ; i++)
{
if(player[i].a < player[rest + 1 - i].a)
player[i] = player[rest + 1 - i];

? ? ? ? ? ? ? ? ? ? // 統計firstPlayer和secondPlayer相遇輪次的最大值和最小值
if(player[i].b == firstPlayer && player[rest + 1 - i].b == secondPlayer)
ans1 = min(ans1 , now) , ans2 = max(ans2 , now);
}
now++;
rest = (rest + 1) / 2;
sort(player + 1 , player + rest + 1);
}
}
vector<int> ans = {ans1 , ans2};
return ans;

? ? }
};

dfs

class Solution {
bitset<1 << 15> m;
int the_max = 0, the_min = INT_MAX;

? ? void dfs(int serial, int n, int firstPlayer, int secondPlayer) {
int mask = (n << 10) + (firstPlayer << 5) + secondPlayer;
int ff = n - firstPlayer + 1, fs = n - secondPlayer + 1;
if (ff == secondPlayer) {
the_max = max(the_max, serial);
the_min = min(the_min, serial);
return;
}
if (m[mask]) return;
m.set(mask);

? ? ? ? int arr[] {firstPlayer, secondPlayer, ff, fs};
sort(arr, arr + 4);
int f_index = lower_bound(arr, arr + 4, firstPlayer) - arr;
int s_index = lower_bound(arr, arr + 4, secondPlayer) - arr;
for (int i = 0; i < arr[0]; ++i) {
for (int j = 0; j < arr[1] - arr[0]; ++j) {
int fi = arr[0] - 1 - i;
int fj = arr[1] - arr[0] - 1 - j;
int mid = (arr[2] - arr[1]) / 2;

? ? ? ? ? ? ? ? int val[] { i, i + j, i + j + mid, i + j + mid + fj };

? ? ? ? ? ? ? ? if (f_index == 0 && s_index == 1) {
dfs(serial + 1, (n + 1) / 2, val[0] + 1, val[1] + 2);
} else if (f_index == 2 && s_index == 3) {
dfs(serial + 1, (n + 1) / 2, val[2] + 1, val[3] + 2);
} else if (f_index == 0 && s_index == 2) {
dfs(serial + 1, (n + 1) / 2, val[0] + 1, val[2] + 2);
} else {
assert(f_index == 1 && s_index == 3);
dfs(serial + 1, (n + 1) / 2, val[1] + 1, val[3] + 2);
}
}
}
}

public:
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
dfs(1, n,firstPlayer, secondPlayer);
return { the_min, the_max };
}
};

計算兩個特定選手（firstPlayer和secondPlayer）在比賽中最早和最晚相遇的輪次。

1.?用深度優先搜索（dfs）模擬比賽過程，不是真的比勝負，而是追蹤兩個選手的位置變化。

2.?每次遞歸代表一輪比賽，選手按規則配對后，勝者進入下一輪，位置會重新排列。

3.?代碼通過記錄狀態（當前總人數、兩個選手的位置）避免重復計算，高效找出兩人相遇的最早和最晚輪次。

簡單說，就是用遞歸模擬每一輪比賽，追蹤兩個指定選手的位置變化，最終得出他們最早和最晚能碰上的輪次。

找回自信dp

class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
//初始化一個dp表
vector<int> dp(n+1,0);
//初始化
dp[0]=dp[1]=0;
//填表
for(int i=2;i<n+1;i++)
//根據狀態轉移方程得
dp[i]=min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2]);
//一步兩步當中，勇敢取小
return dp[n];

? ? }
};

在 C++ 中， queue ?可以存儲 vector ，因為 queue ?是一種容器適配器，它可以容納任何符合要求的元素類型，包括標準容器（如 vector ）。

accumulate()累加求和

accumulate ?是 C++ 標準庫 <numeric> ?里的一個實用工具，專門用來做累加求和

accumulate(vec開始位置, vec結束位置, 0);

eg.(nums.begin(),nums.end(),0)

最小成本的聯通所有點

兩個算法的相同點：每次都是加min 邊

?prim? 加點法? if(未加點 && 最小邊)

每次選最近的村子修路，修好再看其他村子經新路會不會更近，

?kruskal 加邊法? if(未連通 && 最小邊)

lc1584.連接所有點

?解決“連接所有點的最小費用”問題的，用Prim算法（一種求最小生成樹的算法）

核心思路

把點想象成“城市”，連接點的費用是“修路成本”，目標是用最少成本把所有城市連通。

Prim算法的思路是**“貪心”**：從一個起點出發，每次選當前離已連通區域最近的新城市，把它連進來，直到所有城市連通。

代碼

class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
// 定義一個極大值，代表初始“無限遠”的距離
const int inf = INT_MAX;?

int n = points.size();?
int ans = 0;?
// 標記點是否已加入“已連通區域”（城市是否已連通）
vector<bool> visited(n,false);?
// 記錄每個點到“已連通區域”的最小距離（每個城市到當前連通區的最低修路成本）
vector<int> dist(n,inf);?
// 選第一個點當起點，它到自己的距離是0（自己和自己連通不要錢）
dist[0] = 0;?

? ? ? ? // 要把n個點都連通，循環n次（每次連一個新點）
for(int i = 0; i < n;i++){?
// 找當前離“已連通區域”最近的點（找最低成本的城市）
int u = -1;?
for(int j = 0;j < n;j ++){
// 沒訪問過，且是當前找到的距離最小的點
if(!visited[j]&&(u ==-1||dist[u] > dist[j])){?
u = j; // 選中這個點
}
}
// 把這個點標記為“已連通”（加入修路計劃）
visited[u] = true;?

? ? ? ? ? ? // 更新其他未連通點到“已連通區域”的最小距離
for(int j =0; j < n; j++){
if(!visited[j]){?
// 計算當前點u和點j的曼哈頓距離（修路成本）
int newDist = abs(points[j][0]-points[u][0]) + abs(points[j][1]-points[u][1]);?
// 如果經u連接更便宜，就更新“j到連通區的最小成本”
dist[j] = min(dist[j],newDist);?
}
}
}
// 把所有“最小距離”加起來，就是總費用（總修路成本）
return accumulate(dist.begin(),dist.end(),0);?
}
};

1.?初始化：選第一個點當起點，記錄每個點到“已連通區”的距離（初始時只有起點自己，所以起點距離是0，其他是“無限遠”）。
2.?選最近點：每次從“未連通”的點里，挑離“已連通區”最近的點，把它加入連通區。
3.?更新距離：加入新點后，重新算其他未連通點到“新連通區”的距離（因為可能經新點連接更便宜）。
4.?算總費用：把所有點到連通區的最小距離加起來，就是連通所有點的最小總費用。

就像“修路包工頭”，每次選最近的村子修路，修好再看其他村子經新路會不會更近，最后把修路的錢全加起來，就是最省錢的方案～