X03A |day4题解加方法笔记
2025-08-06 15:46:44
发布于：上海
第一题：
<连通块问题> 时间限制：1.00s 内存限制：128MB
题目描述
输入一个n个点m条边的图。然后输入两个整数x,y，判断结点x与结点y是否在同一个连通块中。
如果节点x与节点y在一个连通块中，输出该连通块内节点的数量，否则输出0。
输入格式
第一行输入两个整数
n,m (1≤n≤10^5, 1≤m≤2∗10^5)
接下来m行，每行输入两个整数 u,v(1≤u,v≤n)
u,v(1≤u,v≤n) 表示点u与v之间有一条无向边。
最后一行输入两个整数x,y(1≤x,y≤n)
输出格式
输出一个整数。如果节点x与节点y在一个连通块中，输出该连通块内节点的数量，否则输出0。
输入输出样例
输入#1 输出#1
5 3 .......... 3
1 2
1 3
4 5
2 3
输入#2 输出#2
5 3 ........... 0
1 2
1 3
4 5
2 4
先是深搜（dfs）：
#include <bits/stdc++.h>
using namespace std;
int n, m, u, v, x, y, ans;
vector<int> ve[100005];
bool vis[100005];
void dfs(int u){
vis[u] = 1;//当下位置标记为已访问，避免重复访问
ans++;//每当我到达一个新的结点位置时，增加一个数量
for(int i = 0; i < ve[u].size(); i++){//遍历每一个可以扩散到达的结点
//逐一枚举下一步可到达的位置信息
v = ve[u][i];//找到第 i 条从 u 出发可到达的结点
//判断下一步的位置是否处于合法状态
if(vis[v] == 0){//当前这个结点没有被访问过，则进行扩散
dfs(v);//递归搜索下一步的位置
}
}
//若有要求，需要回溯时，写在下方
}
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> u >> v;
ve[u].push_back(v);//无向图
ve[v].push_back(u);//自右向左
}
cin >> x >> y;
dfs(x);//深度优先搜索
// bfs();//广度优先搜索
if(vis[y]){//y结点处于可以被到达位置时
cout << ans;//输出当前连通块，从 x 出发可以连接的结点数量
}else{//否则
cout << "0";//输出 0 用于表示 y 结点无法被到达
}
return 0;
}
再展示广搜做法（bfs）：
#include <iostream>
#include <queue>
using namespace std;
vector <int> g[100010]; // 邻接表存图
bool v[100010]; // 访问标记
int c[100010],s[100010],k; // c:连通块编号 s:连通块大小 k:连通块计数
int n, m, a, b, x, y;
void bfs (int x) {
queue <int> q;
q.push (x);
v[x] = 1;
c[x] = k;
int t = 0; // 当前连通块节点数
while (!q.empty ()) {
int u = q.front ();
q.pop ();
t++;
for (int i : g[u]) {
if (!v[i]) {
v[i] = 1;
c[i] = k;
q.push (i);
}
}
}
s[k++] = t; // 记录连通块大小
}
int main ()
{
cin >> n >> m;
while (m--) {
cin >> a >> b;
g[a].push_back (b);
g[b].push_back (a);
}
for (int i = 1; i <= n; i++) {
if (!v[i]) bfs (i);
}
cin >> x >> y;
cout << (c[x] == c[y] ? s[c[x]] : 0);
return 0;
}
第二题：
<充满希望的课程安排> 时间限制：1.00 内存限制：128MB
题目描述 :
盖亚正在军事学院进修，他需要上完所有的课程，才能获得战争学博士学位。
但是军事学院的课程之间有一定的依赖关系。比如你需要学习了离心机使用课程，才能学习核燃料制备课程。但是有传言说军事学院已经被间谍渗透，所有人都无法学完所有的课程。
现在盖亚已经拿到了所有的课程依赖关系，想知道他是否能学完所有的课程。
输入格式
第一行输入一个整数 n(1≤n≤100000,1≤m≤200000)，n为课程总数， m为依赖关系数量。
第 2 行到第 m+1行,每行输入2个整数 x,y。表示需要先上课程 x 才能上课程 y。
输出格式
如果可以上完所有课程，输出“YES”，否则输出"NO"。
输入输出样例
输入#1 输出#1
5 5 ......... YES
1 2
1 3
2 3
3 5
4 5
输入#2 输出#2
5 4 ............ NO
1 2
2 3
3 1
4 5
先判断题目为搜索类题型，即可用深搜或广搜，这里用深搜举例：
#include <bits/stdc++.h>
using namespace std;
int n, m, u, v, inD[100005], ans;
vector<int> ve[100005];
bool vis[100005];//用于避免深度优先搜中出现重复
void dfs(int u){
vis[u] = 1;//把当下 u 位置标记为访问状态，避免重复
ans++;//计数器在当前位置增加
for(int i = 0; i < ve[u].size(); i++){//解锁以当前为前置其他任务
v = ve[u][i];//找到以 u 为起点第 i 条任务线
inD[v]--;//释放当前这条任务的限制
if(inD[v] == 0) //当前 v 任务已经完成全部的前置任务，
dfs(v);//递归执行下一结点
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> u >> v;//需要先完成任务 u，当 v 的前置任务完成 ，才可以执行任务 v
ve[u].push_back(v);//添加关系网
inD[v]++;//v任务的前置内容增加一条
}
for(int i = 1; i <= n; i++){//遍历每一个结点
if(vis[i] == 0 && inD[i] == 0){//判断其结点前置任务数量是否为 0
dfs(i);//深度优先搜索
}
}
// bfs();//广度优先搜索
if(ans == n)//判断是否所有的任务全部解锁
cout << "YES";
else
cout << "NO";
return 0;
}
第三题：
<拼接质数1> 时间限制：1.00 内存限制：128MB
题目描述：
盖亚为了抵御邪恶敌人的进攻，必须建立一个防护罩。
防护罩可以由若干个魔力水晶组成，每个魔力水晶有一定的魔力值，
而防护罩的总魔力值为所有魔力水晶魔力值之和。
盖亚发现只有当防护罩的总魔力为质数时，才可以保证防护罩的正常运转。
现在盖亚有 n 个魔力水晶，并且知道每个魔力水晶的魔力值 Ai。。他想知道他有多少种构建防护罩的方案。
假设所有魔力水晶都是不同的。只要在一种方案中选择了第 i 个魔力水晶，
在另一种方案中没有选择第 i 个魔力水晶 （1≤i≤n），那么我们就认为这两种方案不同。
输入格式：
输入两行，第一行包含一个整数n（1≤n≤12），表示魔力水晶的数量。
第二行包含n个整数，表示每一个魔力水晶的魔力值Ai（1≤Ai≤1000）。
输出格式：
输出一个整数，表示可以组成质数的方案数量。
输入输出样例：
输入#1 输出#1
4 ................. 8
1 2 2 4
依旧用深搜：
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
int a[20], n, ans;
bool check (int x) { // 定义一个函数用来判断质数
if (x <= 1) return 0;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
void dfs (int now, int sum) { // 套用深搜模版，定义dfs函数
if (now == n + 1) {
if (check (sum)) ans++;
return;
}
dfs (now + 1, sum);
dfs (now + 1, sum + a[now]);
}
int main ()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
dfs (1, 0); // 深搜元素和
cout << ans << endl;
return 0;
}
第四题：
<充满希望的拼接质数2> 时间限制：1.00s 内存限制：128MB
题目描述：
盖亚为了抵御邪恶敌人的进攻，必须建立一个防护罩。
防护罩可以由若干个魔力水晶组成，每个魔力水晶有一定的魔力值，而防护罩的总魔力值为所有魔力水晶魔力值之和。
盖亚发现只有当防护罩的总魔力为质数时，才可以保证防护罩的正常运转。
现在盖亚有 n 个魔力水晶，并且知道每个魔力水晶的魔力值 Ai。他想知道他有多少种构建防护罩的方案。
假设所有魔力水晶除魔力值以外全部相同。
也就是说只有如果两个方案不同，当且仅当每个方案的水晶的魔力值从小到大排序后的序列不同。
输入格式：
输入两行，第一行包含一个整数 n（1≤n≤12），表示魔力水晶的数量。
第二行包含 n 个整数，表示每一个魔力水晶的魔力值 Ai（1≤Ai≤1000）。
输出格式：
输出一个整数，表示可以组成质数的方案数量。
输入输出样例：
输入#1 输出#1
4 ............... 5
1 2 2 4
看似与上题一样，实际用另一种方法能够更便捷，
用冷门的set。
//T6 方法一
#include <bits/stdc++.h>
#include <set>
using namespace std;
int n, a[15];
bool vis[15];
set<vector<int>> se;
bool init(int sum){
if(sum < 2) return 0;//若出现 0 或 1 的情况，则表示非质数
for(int i = 2; i * i <= sum; i++)//从 2 开始遍历到 sum 开算术平方根
if(sum % i == 0)//判断是否能够整除开始，i是否为 sum 因子
return 0;//返回非法
return 1;//返回当前sum为质数
}
void solve(){
vector<int> ve;//用于存储选中的元素
int sum = 0;//用于计算所选择的元素总和
for(int i = 1; i <= n; i++)//遍历每一个下标
if(vis[i]){//判断当前下标是否被选择
sum += a[i]; //选择的元素进行累加
ve.push_back(a[i]);//把选择的元素添加进动态数组
}
if(init(sum))//判断当前和是否为质数
se.insert(ve);//若为质数则添加进set当中
}
void dfs(int id){
if(id > n){//当所有的元素已经全部考虑到了
solve();//计算数值的总和
return ;//返回上一层
}
vis[id] = 1;//当前 id 下标元素选择
dfs(id + 1);//递归下一层
vis[id] = 0;//当前 id 下标元素不选择
dfs(id + 1);//递归下一层
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);//排序便于后续的set去重使用
dfs(1);
cout << se.size();
return 0;
}
如果不会用set，即可用搜索解决：
//T6 方法一
#include <bits/stdc++.h>
using namespace std;
int n, a[15], ans;
bool vis[15];
bool init(int sum){
if(sum < 2) return 0;//若出现 0 或 1 的情况，则表示非质数
for(int i = 2; i * i <= sum; i++)//从 2 开始遍历到 sum 开算术平方根
if(sum % i == 0)//判断是否能够整除开始，i是否为 sum 因子
return 0;//返回非法
return 1;//返回当前sum为质数
}
void dfs(int id, int sum){//当前选择位置的元素下标，当前选择元素之和
if(id > n){//已经访问超过了 n 个元素的下标，没有元素
ans += init(sum);//验证 sum 是否为质数
return; //返回上一层
}
//①与前一个元素数值不同可以直接选择添加
//②与前一个元素数值相同，需要判断前一个是否添加，若添加，则可以继续添加
if(a[id] != a[id - 1] || a[id] == a[id - 1] && vis[id - 1]){
vis[id] = 1;//标记为选择状态
dfs(id + 1, sum + a[id]);//当前下标为 id的元素添加上
}
vis[id] = 0;//标记为取消状态
dfs(id + 1, sum);//当前下标为 id 的元素不添加
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);//按照从小到大的规则进行排序，确保有序
dfs(1, 0);//递归判断验证下一个元素是否需要添加，选择元素之和
cout << ans;//输出答案
return 0;
}
题毕。
2.补充笔记：
① set的使用方法：
//set的使用方法
#include <bits/stdc++.h>
#include <set>
using namespace std;
set<int> se;//①排序②去重
int main(){
se.insert(3);
se.insert(1);
se.insert(9);
se.insert(114514);
se.insert(1949);
se.insert(91191);
//迭代器
// set<int>::iterator it;
// for(it = se.begin(); it != se.end(); it++){
// cout << *it << " ";
// }
for(auto it:se){
cout << it << " ";
}
return 0;
}
② 文件判题：
#include <bits/stdc++.h>
using namespace std;
int main ()
{
freopen ("文件名.in", "r", stdin);
freopen ("文件名.out", "w", stdout); //打开文件读写。
fclose (stdin);
fclose (stdout); //关闭文件读写。
return 0;
}
举个例子：
用文件判题实现A+B：
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main ()
{
freopen ("a+b.in", "r", stdin);
freopen ("a+b.out", "w", stdout); //打开文件读写。
cin >> a >> b;
cout << a + b << endl;
fclose (stdin);
fclose (stdout); //关闭文件读写。
return 0;
}
这里空空如也
有帮助，赞一个