我从这里抄的
题目网址
B - Call the ID Number
题目大意
有 N 个人，编号为 1∼N。每个人都有一张卡片，第 i 个人的卡片上写的是 Ai。 现在从第一个人开始，如果这个人没有被喊过，就喊一下他卡片上写着的人。 问最终有多少个人从没被喊过。
解题思路
使用桶进行标记，方便从小到大输出
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
bool t[200005];
signed main() {
int n,sum = 0;
cin >> n;
for(int i =1; i <= n; i++){
int x;
cin >> x;
if(t[i]!=1) {//没有被报过ID的进行标记
t[x] = 1;
}
}
for(int i =1; i <= n ; i++){//记录有多少个没有报
if(t[i]==0) sum++;
}
cout << sum << "\n";
for(int i =1; i <= n ; i++){
if(t[i]==0) cout << i <<" ";
}
return 0;
}
C - Make Takahashi Happy
题目大意
给定一个 H 行 W 列的矩阵，每次可以往右或往下走，问从 (1,1) 走到 (H,W) 有多少条路径满足下面的要求：“路径上的数没有重复的”
解题思路
使用一个set变量检验重复数字，进行爆搜
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
set<int> t;//用于检验是否有过重复数字
int h,w,sum;
int a[15][15];
int dx[3] = {0,1,0};
int dy[3] = {0,0,1};
void dfs(int x, int y) {
if(x==h&&y==w){//达到终点
sum++;
return;
}
for(int i=1;i<=2;i++){
int nx = x + dx[i];
int ny = y + dy[i];
// cout <<nx<<" "<< ny <<"\n";
if(a[nx][ny]!=0 && !t.count(a[nx][ny])){//确认是否越界，是否重复
t.insert(a[nx][ny]);
dfs(nx,ny);
t.erase(t.find(a[nx][ny]));
}
}
}
signed main() {
cin >> h >> w;
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
cin >> a[i][j];
}
}
t.insert(a[1][1]);//!!!一定要加入原点数字
dfs(1,1);
cout << sum;
return 0;
}
D - Tying Rope
题目大意
给 N 根绳子，每根绳子的两端分别为蓝色与红色。 有 M 次操作，第 iii 次操作为：ai,bi,ci,di ，表示把第 ai 根绳子的 bi 颜色端和第 ci 根绳子的 di 颜色端连在一起。保证每根绳子的每个颜色端最多被连接一次。问最终有多少个环，和多少个链。
解题思路
使用并查集算法，先把两根绳子连接，如果某两根绳子被连接之前已经联通了，就构成了环，分别进行累加 不懂并查集的可以先学习一下
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int fa[200005];
int bcj(int x)//并查集模板
{
if (fa[x] == x)
return x;
else{
fa[x] = bcj(fa[x]);
return fa[x];
}
}
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)// 初始化不要忘了！！查了半天 QWQ
fa[i] = i;
int x = 0;
int y = n;//不要忘记初始化
for (int i = 1; i <= m; i++)
{
int a, c;
char b, d;//类型要定义对 T_T
cin >> a >> b >> c >> d;
int aa = bcj(a), cc = bcj(c);//避免重复调用
if (aa == cc)// 形成了循环的连接绳子
x++;//多了一组循环的绳子
else// 没有形成循环的连接绳子
fa[aa] = cc;//把两个绳子相连
y--; //单根的绳子少了一根
}
cout << x << " " << y << "\n";
return 0;
}