文章目录
- 【蓝桥杯专题】 （C++ | 洛谷 | acwing | 蓝桥）
- 1249. 亲戚
- 836. 合并集合
- 837. 连通块中点的数量
- 238. 银河英雄传说 【带权并查集】
- 145. 超市 【并查集 + 贪心】
- 4793. 危险程度 (连通块并查集 ）
- 普通oi 读文件
- 对拍程序
【蓝桥杯专题】 （C++ | 洛谷 | acwing | 蓝桥）
1249. 亲戚
链接 链接
- 并查集模板 题 ：
- 合并
f[find(a)] = find(b); - 查询
int find (int x) {
if(x != f[x]) {
f[x] = find(f[x]); // 路径压缩
}
return f[x];
}
- 必须初始化
f[i] = i
#include <iostream>
#include <cstring>
#include <algorithm>
#define debug cout<<"debug"<<"\n"
using namespace std;
const int N = 20000 + 10;
int n, m, q;
int f[N];
int find (int x) {
if(x != f[x]) {
f[x] = find(f[x]);
}
return f[x];
}
int main () {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) f[i] = i;
while (m -- ) {
int a, b;
scanf("%d%d", &a, &b);
f[find(a)] = find(b);
}
scanf("%d", &q);
while (q -- ) {
int x , y;
scanf("%d%d", &x, &y);
if(find(x) == find(y)) {
puts("Yes");
} else {
puts("No");
}
}
return 0;
}
836. 合并集合
链接 链接
include<iostream>
using namespace std;
const int N=100010;
int p[N];//定义多个集合
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
/*
经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:
p[x]=x;
*/
return p[x];
//找到了便返回祖宗节点的值
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) p[i]=i;
while(m--)
{
char op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(*op=='M') p[find(a)]=find(b);//集合合并操作
else
if(find(a)==find(b))
//如果祖宗节点一样,就输出yes
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
837. 连通块中点的数量
链接 链接
- 初始化每个节点
size == 1 - 合并更新大小 需要加上
x的数量 sz[y] += sz[x];
#include<bits/stdc++.h>
#define read(x) scanf("%d",&x)
using namespace std;
const int N = 1e5+5;
int n,m,a,b,fa[N], sz[N];
string act;
void init() {
for(int i = 1; i <= n; i ++) {
fa[i] = i;
sz[i] = 1;
}
}
int find(int x) {
if(fa[x] != x) {
fa[x] = find(fa[x]);
}
return fa[x];
}
void merge(int a,int b) {
int x = find(a);
int y = find(b);
fa[x] = y;
sz[y] += sz[x];
}
bool ask(int a,int b) {
if(find(a) == find(b)) return true;
return false;
}
int main() {
read(n),read(m);
init();
while(m--) {
cin>>act;
if(act=="C") {
read(a),read(b);
if(!ask(a,b)) merge(a,b);
} else if(act=="Q1") {
read(a),read(b);
ask(a,b) ? printf("Yes\n") : printf("No\n");
} else {
read(a);
printf("%d\n",sz[find(a)]);
}
}
return 0;
}
238. 银河英雄传说 【带权并查集】
链接 链接
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30010;
int n = 30000,m;
int p[N],d[N],s[N];
int find (int x) {
if(p[x] != x) {
int rx = find(p[x]);
d[x] += d[p[x]];
p[x] = rx;
}
return p[x];
}
int main () {
cin >> m;
for (int i = 1;i <= n;i++) p[i] = i,s[i] = 1;
while (m--) {
char op;
int a,b;
cin >> op >> a >> b;
int ra = find (a),rb = find (b);
if (op == 'M') {
if (ra != rb) { // 如果是一样的话就不需要更新了
p[ra] = rb;
d[ra] = s[rb];
s[rb] += s[ra];
}
}
else {
if (ra != rb) puts ("-1");
else cout << max (0,abs (d[a] - d[b]) - 1) << endl;
}
}
return 0;
}
145. 超市 【并查集 + 贪心】
链接 链接
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\n"
#define endl "\n"
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 1e4 + 10;
const int M = N * 2;
#define x first
#define y second
int fa[N], n, ans ;
pii a[N];
bool cmp(pii a, pii b) {
return a.x > b.x;
}
int find(int x) {
if(fa[x] != x) {
fa[x] = find(fa[x]);
}
return fa[x];
}
void meger(int a, int b) {
fa[find(a)] = find(b); // !!!!! 合并
}
void solve () {
while(cin >> n) {
ans = 0;
for(int i = 0; i < n; i ++) {
cin >> a[i].x >> a[i].y;
}
for(int i = 0; i < N; i ++) {
fa[i] = i;
}
sort(a, a + n, cmp);
for(int i = 0; i < n; i ++) {
int x = find(a[i].y);
if(x) {
ans += a[i].x;
meger(x, x - 1);
}
}
cout << ans << endl;
}
// for)
}
int main(void){
// freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
// cin >> T;
while(T --) solve();
return 0;
}
4793. 危险程度 (连通块并查集 ）
-
解题一 : (DFS)
题目说要使最后的危险程度最大
其实就是让每一次丢的化学物质都尽可能有能反应的物质丢到了试管中
所以我们每一次丢试剂的时候都要尽可能把所有能反应的一股脑丢进去
所以，凝练之后其实就是连通块问题
把所有能反应的试剂用一张无向边的图来存储，每一次都把连通块搜索完，就能得到最后答案 -
思路二 : (并查集)
1.连通块问题
2.设每一个连通块的数量为ki，那么每一块连通块对危险系数的贡献为2 ^ (ki - 1)
3.所以最后的结果就是2 ^ (n - 连通块的数量)
链接 链接
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2510;
int f[N];
int n, m;
long long res = 1; // 空试管的危险值为 1
// ，每倒入一种化学物质，
//如果该物质能够与之前倒入试管中的一种或多种物质发生反应，则试管的危险值将乘以 2
int find (int x) {
if(x != f[x]) {
f[x] = find(f[x]);
}
return f[x];
}
int main () {
cin >> n >>m;
for (int i = 1; i <= n; i ++ ) f[i] = i;
while(m --) {
int a, b;
cin >> a >>b;
f[find(a)] = find(b);
}
for (int i = 1; i <= n; i ++ ) if(f[i] != i) res *= 2;
cout <<res << endl;
return 0;
}
普通oi 读文件
对拍程序
y总的讲解
- 代码为01背包的对拍程序
对拍.cpp
#include <iostream>
#include <fstream>
using namespace std;
void generate_data() // 生成数据 ： 这个根据题目输入输出写就可以 ， 再结合 rand() 函数 %x 是这个随机数的范围
{
ofstream fout("input.txt"); // 创建一个名为 "input.txt" 的文件，并打开一个输出流以便向该文件写入数据。具体来说，它初始化了一个名为 fout 的 ofstream 类对象，用于向 "input.txt" 文件输出数据。
int n = 10, m = rand() % 100 + 50;
fout << n << ' ' << m << endl; // fout 读数据
for (int i = 0; i < n; i ++ )
{
int v = rand() % 50 + 10, w = rand() % 50 + 10;
fout << v << ' ' << w << endl; // fout 读数据
}
fout.close(); // 关闭文件
}
int main()
{
for (int i = 0; i < 100; i ++ )
{
printf("iteration: %d\n", i);
generate_data();
system("Dp.exe < input.txt > dp_output.txt"); // 将dp.exe 的输入 存到 dp_output中
system("bruteforce.exe < input.txt > bf_output.txt"); // 将暴力.exe 输入到 bfput.txt中
if (system("fc dp_output.txt bf_output.txt")) //比较txt的内容 如果俩程序输入输出不同 则输出错误 ！
{
puts("错啦!");
break;
}
}
return 0;
}
dp.exe
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int f[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ )
{
int v, w;
scanf("%d%d", &v, &w);
for (int j = m; j >= v; j -- )
f[j] = max(f[j], f[j - v] + w);
}
printf("%d\n", f[m]);
return 0;
}
baoli.exe
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ )
scanf("%d%d", &v[i], &w[i]);
int res = 0;
for (int i = 0; i < 1 << n; i ++ )
{
int sumv = 0, sumw = 0;
for (int j = 0; j < n; j ++ )
if (i >> j & 1)
{
sumv += v[j];
sumw += w[j];
}
if (sumv <= m) res = max(res, sumw);
}
printf("%d\n", res);
return 0;
}
