藍橋杯拿了個省三，天梯沒進1隊，睿抗是我最后的機會

RC-u4 章魚圖的判斷

題目描述

對于無向圖 $G=(V,E)$，我們定義章魚圖為：

有且僅有一個簡單環（即沒有重復頂點的環），且所有其余邊和點都構成附著在該環上的樹結構。換言之，是一個環作為“身體”，多個樹作為“觸手”的連通圖。

給定一個無向圖，請判斷圖中是否存在且僅存在一個章魚子圖。

---

輸入格式

• 第一行是一個正整數 $T$，表示數據的組數，$1\le T\le 5$。
• 每組數據的第一行是兩個正整數 $N,M$，表示圖中有 $N$ 個頂點和 $M$ 條邊，$1\le N,M\le 10^5$。
• 接下來的 $ M $ 行中，每行包含兩個整數 $u,v$，表示頂點 $u$ 與頂點 $v$ 之間有一條無向邊。
• 所有頂點編號從 $1$ 開始。輸入中不會包含重復邊或自環。

輸出格式

對于每組數據，輸出一行結果：

• 如果圖中存在且僅存在一個章魚子圖，輸出：Yes x，其中 x 是該章魚圖中環的大小（即環中頂點數）。
• 否則，輸出：No y，其中 y 是圖中滿足章魚圖結構的連通子圖個數。

輸入樣例

3
10 10
1 3
3 5
5 7
7 9
1 2
2 4
2 6
3 8
9 10
1 9
10 10
1 3
3 5
5 7
7 9
9 1
1 2
2 4
4 8
8 10
10 1
10 10
1 3
3 5
5 7
7 9
9 1
2 4
4 8
8 10
10 2
10 6

---

輸出樣例

Yes 5
No 0
No 2

第一版 （2 分）

想到并查集，題目理解錯了題目要求是 ：則在一行中輸出 ``Yes 和章魚子圖環的大小（及環中頂點數要求的環的大小，而我第一次直接求的連通分量的大小，所以不該用并查集的，直接暴搜

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int fa[N];
int n, m;int find(int x)
{return fa[x] == x ? x : fa[x] = find(fa[x]);
}int main()
{int k, cnt = 0, num = 0;cin >> k;while(k --){cnt = 0;cin >> n >> m;vector<int> siz(n + 1, 1);for (int i = 0; i <= n +1; i ++)fa[i] = i;for (int i = 1; i <= m; i ++){int a, b;cin >> a >> b;a = find(a);b = find(b);if (a == b) {cnt ++;if (cnt == 1) {num = siz[a];}}else if (a != b){if (siz[a] > siz[b]) swap(a, b);fa[a] = b;siz[b] += siz[a];} }if (cnt == 1) {cout << "Yes" << " " << num << endl;}else{cout << "No" << " " << cnt << endl;}}return 0;}  

正確的思路應該是：

先分出連通塊，然后在連通快里面去 dfs 看是不是章魚圖了

第二版(100)

面對這道題可以直接進行搜索，我們先對每個點找到他的連通分量，然后在這個連通分量里面去找有沒有環，如果有環，再去這個環中找 環的節點個數

代碼加了注釋

#include<bits/stdc++.h>
using namespace std;
// 存圖 
vector<vector<int>> g; // 從每個節點開始找連通塊、連通塊中找環的狀態數組 
vector<bool> visited, vis2;
// 連通量節點數、父節點、環節點數 
vector<int> comNodes,  parent, circleNodes;// 找到連通分量 
void dfs1(int u)
{visited[u] = true;comNodes.push_back(u);for (int v : g[u]){if (!visited[v]) {dfs1(v);}} } void dfs2(int u , int p)
{vis2[u] = true;for (int v : g[u]){if (v == p) continue;if (!vis2[v]) {parent[v] = u;dfs2(v, u);if (!circleNodes.empty()) return ;} else {// 找到回邊（u, v），說明存在一個環int x = u;circleNodes.push_back(v);while (x != v) {circleNodes.push_back(x);x = parent[x];  // 一步一步回找，找出環的節點個數 } return ;}}
}int main()
{int t;cin >> t;while(t --){int n, m;cin >> n >> m;g.assign(n + 1, {});  // 清空 for (int i = 1; i <= m; i ++){int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}// cnt1:第一個環中的節點數量， // cnt2:表示的是環的數量 int cnt1 = 0, cnt2 = 0; // visited.assign(n + 1, false);for (int i = 1; i <= n; i ++){if (!visited[i]){comNodes.clear();dfs1(i);// 統計頂點數和邊數long long sumDeg = 0;for(int u:comNodes)sumDeg += g[u].size();int  V = comNodes.size();int E = sumDeg / 2;  // 無向圖// 判斷是否是環的條件 if (E == V && V > 2) {cnt2 ++;if (cnt2 == 1) {// 統計第一個章魚圖的環的大小vis2.assign(n + 1, false);circleNodes.clear();parent.assign(n + 1, -1);dfs2(comNodes[0], -1);cnt1 = circleNodes.size(); }} }}if (cnt2 == 1) {cout << "Yes" << " " << cnt1 <<endl;} else {cout << "No" << " " << cnt2 << endl;}}return 0;
}

RC-u3 暖爐與水豚

題目描述

在一個 $(N\times M)$ 的矩陣中，有若干只水豚和若干個暖爐。暖爐可以輻射其中心為中心的 $(3\times 3)$ 區域（上下左右斜對角一共9格），使其中的水豚變得暖和。

現在你得到了一個矩陣，其中：

• "w" 表示暖和的水豚；
• "c" 表示很冷的水豚；
• "m" 表示暖爐；
• "." 表示一個空格（可能是真的空，或者被擋住的暖爐）。

問題：

由于圖像被遮擋，最多只有一只水豚的狀態是錯誤的（比如周圍沒有暖爐卻是暖和的），請你判斷：

在哪些空格位置放一個暖爐，可以讓整個狀態變得合法？

一個位置 ((r, c)) 被認為可能藏有暖爐，當在此位置放置暖爐后，所有水豚的狀態都與周圍暖爐情況一致（至多一處例外）。

---

輸入格式

• 第一行兩個正整數 (N, M)$（(1\le N,M\le 1000)）$，表示矩陣行列數；
• 接下來 (N) 行，每行 (M) 個字符，表示矩陣中的內容，字符含義如下：
  • .：空格或疑似空格；
  • c：很冷的水豚；
  • w：暖和的水豚；
  • m：暖爐。

---

輸出格式

輸出若干行，每行兩個正整數 (r, c)，表示該位置可能藏有暖爐。多個可能位置需要按 行號升序、列號升序 輸出。

如果沒有任何可能位置，輸出一行：

Too cold!

---

輸入樣例

6 8
wm....mw
.w..ww..
..wm.wwm
w.w....w
.m.c.m..
w.....w.

---

輸出樣例

2 7
3 5
4 6
4 7

算法思路

按照題目一步一步模擬即可，先把 c 周圍的格子全部標記（不可能藏有火爐），然后枚舉 m，把所有 m 周圍的 w 都溫暖， 最后枚舉沒有被溫暖的 w，火爐就可能藏在它周圍。

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
char g[N][N];
bool st[N][N];
int n, m;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; void bfs(int x, int y)
{queue<pair<int, int>> q;st[x][y] = 1;q.push({x, y});while (q.size()){auto t = q.front();q.pop();for (int i = 0; i < 8;i ++){int a = t.first + dx[i];int b = t.second + dy[i];if (a < 1 || b < 1 || a > n || b > m) continue;if (st[a][b]) continue;st[a][b] = 1;}} 
}
int cnt = 0;
bool flag = 1;
signed main()
{cin >> n >> m;// 讀圖 for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++)cin >> g[i][j];for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++){// 如果是c，說明周圍的所有都不能是火爐 if (g[i][j] == 'c'){st[i][j] = 1;for (int k = 0; k < 8; k ++){int a = i + dx[k];int b = j + dy[k];if (g[a][b] == '.') {st[a][b] = 1;g[a][b] = '#';  // 防止后面誤判 }}}else if (g[i][j] == 'm'){bfs(i, j); // 把火爐周圍的溫暖 }}for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++){if (!st[i][j] && g[i][j] == 'w')  // 找到沒有被溫暖的，火爐可能藏在它周圍 {for (int k = 0; k < 8; k++ ){int a  = i + dx[k];int b = j + dy[k];if (g[a][b] == '.'){cout << a << " " << b << endl;flag = 0;  // 說明至少一個隱藏火爐 }}}}if(flag) cout << "Too cold!" ;return 0;
}

RC-u5 工作安排

題目描述

小 K 有 $ N $ 項工作等待完成，每項工作有以下三個屬性：

• $t_i$：完成這項工作所需的時間；
• $d_i$：這項工作的截止時間（必須在這個時間之前或剛好完成）；
• $p_i$：完成這項工作可以獲得的報酬。

工作從時間 $ 0 $ 開始，每個時間點只能做一項工作，且工作不可中斷、不可切換。

目標：

請你幫小 K 規劃安排，選擇若干項工作，在不違反時間安排的前提下，獲得盡可能多的報酬。

---

輸入格式

• 第一行是一個正整數 $T$（$1\le T\le 5$），表示測試數據的組數；
• 對于每組數據，第一行是一個整數 $N$（$1\le N\le 5000$），表示工作數量；
• 接下來的 $N$ 行，每行 3 個非負整數 $t_i,d_i,p_i$（均 $\le 5000$），表示第 $i$ 項工作的耗時、截止時間和報酬。

---

輸出格式

每組數據輸出一行，表示在最優安排下小 K 可以獲得的最大報酬。

---

輸入樣例

3
5
1 2 50
3 3 100
1 5 1
3 2 5000
4 5 30
5
1 2 50
3 3 20
1 5 1
3 2 5000
4 5 30
5
1 2 50
3 3 100
1 5 1
3 2 5000
5 5 800

---

輸出樣例

101
80
800

算法思路

盡可能多的獲得報酬，很容易想到背包問題，這里 d 是截止時間，那么我們可以用 m 來記錄最大的截止時間，然后我們可以把所有物品按照 d 排序，從小到大枚舉所有物品就 OK 了

code

#include<bits/stdc++.h>
using namespace std;
const int N  = 5050;
int t[N], d[N], p[N];
int n, m ;
int f[N];struct node
{int t, d, p;
};
node a[N];
bool cmp(node a, node b)
{return a.d < b.d;} 
int main()
{int k;cin >> k;while(k --){m = 0;cin >> n;for (int i = 1;i <= n; i ++){cin >> a[i].t >> a[i].d >> a[i].p;m = max(m, a[i].d); }sort(a + 1, a + 1 + n, cmp);for (int i = 0; i <= m; i ++)f[i] = 0;for (int i = 1;i <= n; i ++){for (int j = a[i].d; j >= a[i].t; j --){f[j] = max(f[j], f[j - a[i].t] + a[i].p);}}int ans = 0;for (int i = 0; i <= m; i++)ans = max(ans, f[i]);cout << ans << endl;}return 0;}