对拍程序 并查集专题 (C++ | 洛谷 | acwing | 蓝桥)

文章目录

  • 【蓝桥杯专题】 (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;
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/6503.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

树和二叉树相关的练习(选择题)

目录 一、二叉树 二、堆 三、遍历二叉树 一、二叉树 某二叉树共有 399 个结点&#xff0c;其中有 199 个度为 2 的结点&#xff0c;则该二叉树中的叶子结点数为&#xff08; &#xff09;。 A. 不存在这样的二叉树 B. 200 C. 198 D. 199 下列数据结构中&#xff0c;不适合…

C++ Primer Plus 学习笔记(八)——输入、输出和文件

1 流和缓冲区 C程序把输入和输出看作字节流。输入时&#xff0c;程序从输入流中抽取字节&#xff1b;输出时&#xff0c;程序将字节插入到输出流中。 缓冲区是用作中介的内存块&#xff0c;它是将信息从设备传输到程序或从程序传输给设备的临时存储工具&#xff0c;通过使用缓…

HTTP协议:当下最主流的应用层协议之一,你确定不了解一下吗?

一.HTTP协议的含义http是什么&#xff1f;超文本传输协议&#xff08;Hyper Text Transfer Protocol&#xff0c;HTTP&#xff09;是一个简单的请求-响应协议&#xff0c;它通常运行在TCP之上。‘超’可以理解为除了文本之外的图片&#xff0c;音频和视频&#xff0c;和一些其他…

STM32基于HAL工程FREERTOS读取DS18B20数据+串口输出

STM32基于HAL工程FREERTOS读取DS18B20数据串口输出✨申明&#xff1a;本文章仅发表在CSDN网站&#xff0c;任何其他网站&#xff0c;未注明来源&#xff0c;见此内容均为盗链和爬取&#xff0c;请多多尊重和支持原创!&#x1f341;对于文中所提供的相关资源链接将作不定期更换。…

无需公网IP,远程连接SQL Server数据库【内网穿透】

文章目录1.前言2.本地安装和设置SQL Server2.1 SQL Server下载2.2 SQL Server本地连接测试2.3 Cpolar内网穿透的下载和安装2.3 Cpolar内网穿透的注册3.本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置4.公网访问测试5.结语1.前言 数据库的重要性相信大家都有所了解&#xf…

现代前端开发者的自我迷失,你还会前端基础知识吗?

通常来说&#xff0c;我认为情况并不算糟糕&#xff0c;熟练的手可以几乎做到一切。然而&#xff0c;最近我注意到一些事情改变了我对这个行业的看法。似乎在这些无尽的趋势、范式和新奇玩意中&#xff0c;我们忘记了前端开发的支柱&#xff08;意思是忘记了基础知识&#xff0…

【python】GIL全局锁

一、原理&#xff1a; 全局解释器锁&#xff08;Global Interpreter Lock&#xff0c;GIL&#xff09;规定全局范围内任意时候一个进程里只能同时执行一个线程。每一个线程在执行时&#xff0c;都会锁住GIL&#xff0c;以阻止别的线程执行&#xff1b;执行一段时间后&#xff…

OBCP第四章 SQL调优-SQL执行性能监控

(g)v$sql_audit 全局 SQL 审计表 基于虚拟表__all_virtual_sql_audit的视图&#xff0c; 该虚拟表对应的数据存放在一个可配置的内存空间中 由于存放这些记录的内存是有限的&#xff0c;因此到达一定内存使用量&#xff0c;会触发淘汰 可以用来查看每次请求客户端来源&…

【操作系统复习】第3章 处理机调度与死锁 3

死锁&#xff08;Deadlock&#xff09;&#xff1a;指多个进程在运行过程中因争夺资源而造成的一种僵局&#xff0c;当进程处于这种僵持状态时&#xff0c;若无外力作用&#xff0c;这些进程都将永远不能再向前推进。 对资源不加限制地分配可能导致进程间由于竞争资源而相互制约…

JavaSE学习总结(十三)Set集合HashSet集合LinkedHashSet集合TreeSet集合比较器的使用利用Set集合实现去重

JavaSE学习总结&#xff08;十三&#xff09;Set集合/HashSet集合/LinkedHashSet集合/TreeSet集合/比较器的使用/利用Set集合实现去重 一、Set集合 Set集合是Collection集合的一个子接口&#xff0c;实际上Set就是Collection&#xff0c;只是行为略有不同&#xff1a; Set集…

VUE3项目实现动态路由demo

文章目录1、创建vue项目2、安装常用的依赖2.1 安装elementUI2.2 安装axios2.3 安装router2.4 安装vuex2.5 安装store2.6 安装mockjs3、编写登录页面以及逻辑4、编写首页以及逻辑5、配置router.js6、配置store.js7、配置menuUtils.js&#xff08;动态路由重点&#xff09;8、配置…

树的前序遍历与中序遍历构造二叉树和树的中序遍历与后序遍历构造二叉树

目录 一.树的前序遍历与中序遍历构造二叉树 1.题目描述 2.问题分析 3.代码实现 二.树的中序遍历与后序遍历构造二叉树 1.题目描述 2.问题分析 3.代码实现 三.问题思考 一.树的前序遍历与中序遍历构造二叉树 1.题目描述 给定两个整数数组 preorder 和 inorder &#xf…

【机器学习】Logistic回归---学习笔记

Logistic回归学习笔记Logistic回归学习线路预备知识&#xff1a;建议先去B站学习一下信息量&#xff0c;熵&#xff0c;BL散度&#xff0c;交叉熵的概念。Logistic回归的函数模型损失最小化架构分类函数最大概率分类函数阈值分类函数Logistic回归的优化算法梯度下降随机梯度下降…

4.5--计算机网络之基础篇--2.网址到网页解析--(复习+深入)---好好沉淀,加油呀

1.浏览器做的第一步工作是解析 URL 对 URL 进行解析&#xff0c;从而生成发送给 Web 服务器的请求信息 URL? URL 实际上是请求服务器里的文件资源 当没有路径名时&#xff0c;就代表访问根目录下事先设置的默认文件&#xff0c;也就是 /index.html 或者 /default.html 这些文件…

计算机网络复习笔记(三)物理层

文章目录一物理层的基本概念四大特性&#xff1a;两种信号&#xff1a;调制和编码传输介质三大部分二物理层的基本通信技术四种信道复用技术数据的传输方式三OSI模型一物理层的基本概念 四大特性&#xff1a; 机械特性 接口是怎么样的 电气特性 用多少伏的电 功能特性 线路上…

linux基础之计算机基础

一、计算机基础 &#xff08;1) 计算机发展&#xff1a;电子管、晶体管、集成电路、大规模集成电路 &#xff08;2) 冯诺依曼体系&#xff1a;用二进制表示数据和指令&#xff1b; 存储程序控制&#xff0c;程序和数据预先存入存储器&#xff1b; 计算机系统5大部分&#xf…

Python 高级编程(文件操作)

文件&#xff1a;存储在某种长期存储设备上的数据&#xff01;&#xff01;包括&#xff08;硬板 u 盘 移动硬盘 光盘&#xff09; 计算机中临时的数据&#xff1a; 存储在内存中&#xff0c;一旦操作结束&#xff0c;内存中的空间就会被释放 文件&#xff08;特指普通文本&am…

R语言 4.2.2安装包下载及安装教程

[软件名称]:R语言 4.2.2 [软件大小]: 75.6 MB [安装环境]: Win11/Win10/Win7 [软件安装包下载]: https://pan.quark.cn/s/b6f604930d04 R语言软件的GUI界面比较的简陋,只有一个命令行窗口,且每次创建图片都会跳出一个新的窗口,比较的繁琐,我们可以安装RStudio,来更方便的操作R(…

ChatGPT +工业机器人/自动驾驶控制器的一些尝试

ChatGPT 的功能目前已扩展到机器人领域&#xff0c;可以用语言直观控制如机械臂、无人机、家庭辅助机器人等的多个平台。这会改变人机交互的未来形式吗&#xff1f; 你可曾想过用自己的话告诉机器人该做什么&#xff0c;就像对人说话那样&#xff1f; 比如说&#xff0c;只要告…

多个硬盘挂载到同一个目录

同一目录无法重复挂载&#xff0c;后挂载的会覆盖之前挂载的磁盘。但是现在需要将4块磁盘并行挂载&#xff0c;该如何操作呢&#xff1f; 将2块磁盘合并到一个逻辑卷 进行挂载。 基本知识 基本概念PV(Physical Volume)- 物理卷物理卷在逻辑卷管理中处于最底层&#xff0c;它可…
最新文章