课堂习题&考试代码
2026-07-01 17:02:51
发布于：广东
55阅读
0回复
0点赞
填涂颜色
#include <iostream>
using namespace std;
// 因为 n <= 30，这里开 35 足够。
// 数组下标会用到 0 到 n + 1，所以要比 n 稍微大一点。
const int N = 35;
// a[i][j] 表示地图中的格子：
// 0 表示空白区域
// 1 表示闭合圈的边界
// -1 表示已经确定是“圈外”的 0
int a[N][N], n;
// 四个方向：右、左、上、下
// dx[i], dy[i] 配合使用，表示从当前位置走到相邻格子
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
// 判断坐标 (x, y) 是否在我们扩展后的地图范围内
// 原图范围是 1 ~ n
// 这里额外加了一圈边界，范围变成 0 ~ n + 1
bool inMap(int x, int y) {
return x >= 0 && x <= n + 1 && y >= 0 && y <= n + 1;
}
// 从位置 (x, y) 开始进行 DFS 搜索
// 作用：把所有和“外部”连通的 0 都标记成 -1
void dfs(int x, int y) {
// 枚举四个方向
for(int i = 0; i < 4; i++) {
// 计算相邻格子的坐标
int nx = x + dx[i], ny = y + dy[i];
// 如果相邻格子在地图范围内，并且它是 0，
// 说明它和外部连通，需要标记为 -1
if(inMap(nx, ny) && a[nx][ny] == 0) {
// 标记为 -1，表示这是圈外的 0
a[nx][ny] = -1;
// 继续从这个格子往外扩展
dfs(nx, ny);
}
}
}
int main() {
cin >> n;
// 读入原始 n * n 方阵
// 注意原图从下标 1 开始存储
// 这样可以在外面留出一圈 0，方便从外部开始搜索
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> a[i][j];
// 从扩展地图的左上角 (0, 0) 开始搜索
// (0, 0) 一定在原图外部，所以从这里 DFS 可以找到所有圈外的 0
a[0][0] = -1;
dfs(0, 0);
// 处理原图范围内的所有格子
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
// 如果是 -1，说明它是从外部能到达的 0
// 输出时要恢复成 0
if(a[i][j] == -1) a[i][j] = 0;
// 如果仍然是 0，说明它没有被外部 DFS 搜到
// 也就是说它被 1 围住了，是闭合圈内部的 0
// 所以改成 2
else if(a[i][j] == 0) a[i][j] = 2;
// 输出当前格子
// " \n"[j == n] 是一种简写：
// 如果 j != n，输出空格；
// 如果 j == n，输出换行。
cout << a[i][j] << " \n"[j == n];
}
return 0;
}
观星
#include <iostream>
#include <set>
#include <map>
using namespace std;
// N, M 最大为 1500
// 这里开到 1505，防止边界越界
const int N = 1505;
// v[i][j] 表示星空矩阵中的字符
// '*' 表示当前位置有星星
// '.' 表示当前位置为空
char v[N][N];
// f[i][j] 表示当前位置是否已经被访问过
// true 表示访问过
// false 表示还没有访问过
bool f[N][N];
// n 表示行数，m 表示列数
int n, m;
// mp 用来统计每种“星座大小”对应的“星系大小”
// key：某个星座中星星的数量
// value：所有大小为 key 的星座包含的星星总数
//
// 例如：
// 有 3 个星座，它们的大小都是 4
// 那么 mp[4] = 12
map<int, int> mp;
// 八个方向
// 分别表示：上、右上、右、右下、下、左下、左、左上
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
// 从位置 (x, y) 开始 DFS
// 作用：找到与 (x, y) 相连的整个星座，并返回这个星座中星星的数量
int dfs(int x, int y) {
// 当前这个位置本身就是一颗星星，所以初始数量为 1
int cnt = 1;
// 标记当前位置已经访问过
// 防止之后重复访问同一颗星星
f[x][y] = true;
// 枚举当前位置周围的 8 个方向
for(int i = 0; i < 8; i++) {
// 计算相邻位置的坐标
int nx = x + dx[i], ny = y + dy[i];
// 判断这个相邻位置是否可以继续搜索：
// 1. nx >= 0 && nx < n：行坐标没有越界
// 2. ny >= 0 && ny < m：列坐标没有越界
// 3. v[nx][ny] == '*'：这个位置上有星星
// 4. f[nx][ny] == false：这个星星还没有被访问过
if(nx >= 0 && nx < n && ny >= 0 && ny < m && v[nx][ny] == '*' && f[nx][ny] == false)
// 如果满足条件，说明这颗星星和当前星星属于同一个星座
// 继续 DFS，并把搜索到的星星数量累加到 cnt 中
cnt += dfs(nx, ny);
}
// 返回当前连通星座中星星的总数量
return cnt;
}
int main() {
// 输入星空矩阵的行数和列数
cin >> n >> m;
// 读入星空矩阵
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> v[i][j];
// 枚举整个矩阵中的每一个位置
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
// 如果当前位置是星星，并且还没有被访问过，
// 说明找到了一个新的星座
if(v[i][j] == '*' && f[i][j] == false) {
// DFS 求出这个星座中星星的数量
int res = dfs(i, j);
// 包含星星数量相同的星座属于同一个星系
// 星系大小 = 这个星系中所有星座包含的星星总数
//
// 如果当前星座大小为 res，
// 就把这个星座的 res 颗星星加入 mp[res]
mp[res] += res;
}
// mp 中有多少个不同的 key，
// 就说明有多少种不同大小的星座，
// 也就是有多少个星系
cout << mp.size() << ' ';
// ans 用来记录最大的星系大小
int ans = 0;
// 遍历所有星系
// it.first 是星座大小
// it.second 是该星系的总大小
for(auto it : mp)
ans = max(ans, it.second);
// 输出最大的星系大小
cout << ans;
return 0;
}
封锁阳光大学
#include <bits/stdc++.h>
using namespace std;
int main() {
// n 表示点数，m 表示边数
// ans 表示最终答案：最少需要多少只河蟹
// cnt 表示当前处理到了第几个连通块
int n, m, ans = 0, cnt = 0;
cin >> n >> m;
// g[u] 存储和点 u 相邻的所有点
// 因为是无向图，所以每条边要存两次
vector<vector<int>> g(n + 1);
// sta[i] 表示点 i 的染**况：
// -1 表示还没有染色
// 0 表示染成第 0 类
// 1 表示染成第 1 类
//
// 这道题本质上要判断图是不是二分图。
// 如果是二分图，那么每条边的两个端点一定在不同颜色集合中。
vector<int> sta(n + 1, -1);
// siz[k] 表示第 k 个连通块中一共有多少个点
vector<int> siz(n + 1);
// 读入所有道路
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
// 无向图，u 连 v，v 也连 u
g[u].push_back(v);
g[v].push_back(u);
}
// dfs 用来给一个连通块染色，并统计其中一种颜色的点数
//
// 返回值含义：
// 如果返回 -1，表示当前连通块不是二分图，无法满足要求
// 否则返回当前连通块中 sta 为 1 的点数
auto dfs = [&](auto &&self, int u) -> int {
// res 初始为 sta[u]
// 如果 sta[u] == 1，说明当前点属于颜色 1，贡献 1
// 如果 sta[u] == 0，说明当前点属于颜色 0，贡献 0
int res = sta[u];
// 当前连通块的点数加 1
siz[cnt]++;
// 枚举点 u 的所有相邻点
for(int v : g[u]) {
// 如果相邻两个点颜色相同，
// 说明这张图不是二分图。
//
// 因为如果两个相邻点都放河蟹，会冲突；
// 如果要选一边作为封锁点，就必须能把图分成两边。
if(sta[v] == sta[u]) return -1;
// 如果点 v 还没有染色
if(sta[v] == -1) {
// 给 v 染成和 u 相反的颜色
sta[v] = 1 - sta[u];
// 继续 DFS 处理 v 所在的部分
int tmp = self(self, v);
// 如果子搜索发现不是二分图，直接向上传递 -1
if(tmp == -1) return -1;
// 把子树中颜色 1 的点数累加到 res
res += tmp;
}
}
// 返回当前连通块中颜色 1 的点数
return res;
};
// 枚举所有点
// 因为图不一定连通，所以要对每个连通块分别处理
for(int i = 1; i <= n; i++) {
// 如果这个点已经染过色，说明它所在的连通块已经处理过
if(sta[i] != -1) continue;
// 开始处理一个新的连通块
// 先把当前点染成颜色 1
sta[i] = 1;
// 连通块编号加 1
++cnt;
// 对这个连通块进行 DFS 染色
// tmp 表示当前连通块中颜色 1 的点数
int tmp = dfs(dfs, i);
// 如果 tmp == -1，说明当前连通块不是二分图
// 也就是说存在奇环，例如三角形
//
// 这种情况下无论怎么放河蟹，
// 都无法做到既封锁所有道路，又不让相邻点同时放河蟹
if(tmp == -1) {
cout << "Impossible";
return 0;
}
// 当前连通块一共有 siz[cnt] 个点
// 颜色 1 的点数是 tmp
// 颜色 0 的点数就是 siz[cnt] - tmp
//
// 对于一个二分图连通块：
// 选颜色 1 的所有点，可以覆盖这个连通块中的所有边；
// 选颜色 0 的所有点，也可以覆盖这个连通块中的所有边。
//
// 为了让河蟹数量最少，选择点数更少的那一边。
ans += min(tmp, siz[cnt] - tmp);
}
// 输出最少需要的河蟹数量
cout << ans << endl;
return 0;
}
公共祖先
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
// g[u] 存储树上与 u 相邻的所有节点
vector<int> g[N];
// ans[r] 表示以 r 为根时，所有有序点对 (i, j) 的 LCA 编号之和
ll ans[N];
// cnt[u] 表示在以 1 为根时，节点 u 作为 LCA 出现的次数
// 注意这里统计的是有序点对 (i, j)
ll cnt[N];
// siz[u] 表示在以 1 为根时，u 的子树大小
ll siz[N];
// n 表示节点数量
ll n;
// 第一次 DFS：
// 1. 求出每个节点的子树大小 siz[u]
// 2. 求出以 1 为根时，每个节点 u 作为 LCA 出现的次数 cnt[u]
void dfs1(int u, int fa) {
// 当前节点 u 本身算一个节点
siz[u] = 1;
// 遍历 u 的所有相邻节点
for(auto v : g[u]) {
// fa 是 u 的父节点，不能往回走
if(v == fa) continue;
// 先递归处理子节点 v
dfs1(v, u);
// 加上子树 v 的大小
siz[u] += siz[v];
// 如果两个点都在同一个儿子 v 的子树中，
// 那么它们的 LCA 一定不会是 u，
// 所以要减去 siz[v] * siz[v]
//
// 因为统计的是有序点对：
// 第一个点有 siz[v] 种选法，
// 第二个点也有 siz[v] 种选法，
// 所以共有 siz[v] * siz[v] 对
cnt[u] -= siz[v] * siz[v];
}
// siz[u] * siz[u] 表示：
// 两个点都在 u 的子树中的有序点对数量
//
// 减去所有“两个点都在同一个儿子子树中”的情况后，
// 剩下的点对，它们的 LCA 就是 u
cnt[u] += siz[u] * siz[u];
}
int main() {
cin >> n;
// 读入 n - 1 条边
// 因为是无根树，所以每条边要双向存储
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
// 先默认以 1 为根，计算 siz[u] 和 cnt[u]
dfs1(1, 0);
// 计算 ans[1]
//
// cnt[u] 表示以 1 为根时，u 作为 LCA 出现的次数
// 每次出现都会贡献 u
// 所以总贡献为 cnt[u] * u
for(int u = 1; u <= n; u++)
ans[1] += cnt[u] * u;
// 接下来用换根思想，从 ans[1] 推出其他 ans[r]
queue<int> q;
q.push(1);
// BFS 遍历整棵树
// ans[x] 已经有值，表示 x 作为根时的答案已经算出来
while(!q.empty()) {
int u = q.front();
q.pop();
// 枚举 u 的相邻节点
for(auto v : g[u]) {
// 如果 ans[v] 已经被计算过，说明 v 已经访问过
// 直接跳过，防止往回走
if(ans[v]) continue;
// 现在要从“以 u 为根”的答案推出“以 v 为根”的答案
//
// 设原来以 1 为根时，v 是 u 的儿子。
// siz[v] 表示 v 这一侧的节点数量。
//
// 当根从 u 换到 v 时：
// 对于跨过边 u-v 的点对：
// 一个点在 v 子树内，另一个点在 v 子树外。
//
// 这些点对的 LCA 会从 u 变成 v。
//
// v 子树内有 siz[v] 个点，
// v 子树外有 n - siz[v] 个点。
//
// 因为统计的是有序点对，所以数量是：
// 2 * siz[v] * (n - siz[v])
//
// 每个这样的点对，LCA 编号从 u 变成 v，
// 贡献变化量是 v - u。
//
// 所以总变化量为：
// 2 * siz[v] * (n - siz[v]) * (v - u)
ans[v] = ans[u] + 2 * siz[v] * (v - u) * (n - siz[v]);
// 把 v 加入队列，继续向下换根
q.push(v);
}
}
// 按顺序输出每个节点作为根时的答案
for(int i = 1; i <= n; i++)
cout << ans[i] << ' ';
return 0;
}
有帮助，赞一个