当前位置：首页 > news >正文

2024睿抗CAIP-编程技能赛-本科组（省赛）题解

news 2025/7/4 19:21:40

~~蓝桥杯拿了个省三，天梯没进1队，睿抗是我最后的机会~~

RC-u4 章鱼图的判断

题目描述

对于无向图 $G = (V, E)$ ，我们定义章鱼图为：

有且仅有一个简单环（即没有重复顶点的环），且所有其余边和点都构成附着在该环上的树结构。换言之，是一个环作为“身体”，多个树作为“触手”的连通图。

给定一个无向图，请判断图中是否存在且仅存在一个章鱼子图。

输入格式

第一行是一个正整数 $T$ ，表示数据的组数， $\le T \le 5$ 。
每组数据的第一行是两个正整数 $N, M$ ，表示图中有 $N$ 个顶点和 $M$ 条边， $\le N, M \le 10^5$ 。
接下来的 $ M $ 行中，每行包含两个整数 $u, v$ ，表示顶点 $u$ 与顶点 $v$ 之间有一条无向边。
所有顶点编号从 $1$ 开始。输入中不会包含重复边或自环。

输出格式

对于每组数据，输出一行结果：

如果图中存在且仅存在一个章鱼子图，输出：Yes x，其中 x 是该章鱼图中环的大小（即环中顶点数）。
否则，输出：No y，其中 y 是图中满足章鱼图结构的连通子图个数。

输入样例

输出样例

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 暖炉与水豚

题目描述

在一个 $\times M)$ 的矩阵中，有若干只水豚和若干个暖炉。暖炉可以辐射其中心为中心的 $\times 3)$ 区域（上下左右斜对角一共9格），使其中的水豚变得暖和。

现在你得到了一个矩阵，其中：

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

问题：

由于图像被遮挡，最多只有一只水豚的状态是错误的（比如周围没有暖炉却是暖和的），请你判断：

在哪些空格位置放一个暖炉，可以让整个状态变得合法？

一个位置 ((r, c)) 被认为可能藏有暖炉，当在此位置放置暖炉后，所有水豚的状态都与周围暖炉情况一致（至多一处例外）。

输入格式

第一行两个正整数 (N, M) $\leq N, M \leq 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.

输出样例

算法思路

按照题目一步一步模拟即可，先把 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$ （ $\leq T \leq 5$ ），表示测试数据的组数；
对于每组数据，第一行是一个整数 $N$ （ $\leq N \leq 5000$ ），表示工作数量；
接下来的 $N$ 行，每行 3 个非负整数 $t_i, d_i, p_i$ （均 $\leq 5000$ ），表示第 $i$ 项工作的耗时、截止时间和报酬。

输出格式

每组数据输出一行，表示在最优安排下小 K 可以获得的最大报酬。

输入样例

输出样例

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;}