2.5学习总结9

并查集

知识点

并查集是一种数据结构，用于处理一些不相交集合的合并及查询问题。它支持两种操作：

1. Find(x)：查找元素 x 所属的集合。
2. Union(x, y)：将元素 x 所属的集合和元素 y 所属的集合合并。

初始化：将每个元素单独作为一个集合。

int father[10010];
void init(int n)
{for(int i=1;i<=n;i++)father[i]=i;
}

查找：确定某个元素所属的集合。

int find(int i)
{if(i==father[i])return i;else father[i]=find(father[i]);return father[i];
}

合并：将两个集合合并成一个集合。

void unionn(int i,int j)
{int x=find(i);int y=find(j);father[x]=y;
}

并查集的时间复杂度为O(log*n)，其中n是元素的个数。

P3367 【模板】并查集

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。

接下来 M 行，每行包含三个整数 Zi​,Xi​,Yi​ 。

当 Zi​=1 时，将 Xi​ 与 Yi​ 所在的集合合并。

当 Zi​=2 时，输出 Xi​ 与 Yi​ 是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

对于每一个 Zi​=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

输入输出样例

输入 #1复制

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出 #1复制

N
Y
N
Y

说明/提示

对于 30%30% 的数据，N≤10，M≤20。

对于 70%70% 的数据，N≤100，M≤10^3。

对于 100%100% 的数据，1≤N≤10^4，1≤M≤2×10^5，1≤Xi​,Yi​≤N，Zi​∈{1,2}。

#include<stdio.h>
int father[10010];
void init(int n)
{for(int i=1;i<=n;i++)father[i]=i;
}//初始化
int find(int i)
{if(i==father[i])return i;else father[i]=find(father[i]);return father[i];
}//查找
void unionn(int i,int j)
{int x=find(i);int y=find(j);father[x]=y;
}//合并
int main()
{int i,n,m,z,x,y;scanf("%d %d",&n,&m);init(n);for(i=1;i<=m;i++){scanf("%d %d %d",&z,&x,&y);if(z==1) unionn(x,y);else {if(find(x)==find(y))printf("Y\n");//祖先相同，位于同一集合else printf("N\n");}}    
}

P1111 修复公路

题目背景

A 地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

题目描述

给出 A 地区的村庄数 N，和公路数 M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）。

输入格式

第 1 行两个正整数 N,M。

下面 M 行，每行 3 个正整数 x,y,t，告诉你这条公路连着 x,y 两个村庄，在时间t时能修复完成这条公路。

输出格式

如果全部公路修复完毕仍然存在两个村庄无法通车，则输出 −1，否则输出最早什么时候任意两个村庄能够通车。

输入输出样例

输入 #1复制

4 4
1 2 6
1 3 4
1 4 5
4 2 3

输出 #1复制

5

说明/提示

1≤x,y≤N≤10^3，1≤M,t≤10^5。

#include<bits/stdc++.h>
using namespace std;
struct  road
{int x,y,t;
}a[100010],b;
bool operator < (road a,road b){return a.t<b.t;}
int father[1010];
void init(int n)
{for(int i=1;i<=n;i++)father[i]=i;
}//初始化
int find(int i)
{if(i==father[i])return i;return father[i]=find(father[i]);
}//查找
int main()
{int i,j,n,m,x,y,cnt=0,max=0;scanf("%d %d",&n,&m);init(n);for(i=1;i<=m;i++)scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].t);sort(a+1,a+1+m);//对a[i].t排序for(i=1;i<=m;i++) {int x=find(a[i].x);int y=find(a[i].y);if(x==y)continue;father[x]=y;//合并cnt++;max=a[i].t<max?max:a[i].t;}if(cnt!=n-1)printf("-1");else printf("%d",max);
}

P1455 搭配购买

题目描述

明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有 n 朵云，云朵已经被老板编号为 1,2,3,...,n，并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。

输入格式

第一行输入三个整数，n,m,w，表示有 n 朵云，m 个搭配和你现有的钱的数目。

第二行至 n+1 行，每行有两个整数，ci​,di​，表示第 i 朵云的价钱和价值。

第 n+2 至 n+1+m 行 ，每行有两个整数 ui​,vi​。表示买第 ui​ 朵云就必须买第 vi​ 朵云,同理，如果买第 vi​ 朵就必须买第 ui​ 朵。

输出格式

一行，表示可以获得的最大价值。

输入输出样例

输入 #1复制

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

输出 #1复制

1

说明/提示

• 对于 30%30% 的数据，满足 1≤n≤100；

• 对于 50%50% 的数据，满足 1≤n,w≤10^3，1≤m≤100；

• 对于 100%100% 的数据，满足 1≤n,w≤10^4，0≤m≤5×10^3。

一道并查集+01背包题，01背包的限制条件为买A必须买B，故可以用并查集将几个物品合成一个大物品，然后再用01背包问题做即可。

#include<bits/stdc++.h>
using namespace std;
int father[10010],c[10010],d[10010],dp[10010];
int find(int i)
{if(i==father[i])return i;return father[i]=find(father[i]);
}//查找
void unionn(int i,int j)
{int x=find(i);int y=find(j);if(x!=y){father[x]=y;c[y]=c[y]+c[x];d[y]=d[y]+d[x];}
}//合并物品，将价值，价钱分别相加
int main()
{int n,m,w,i,j;cin>>n>>m>>w;for(i=1;i<=n;i++){cin>>c[i]>>d[i];father[i]=i;}for(i=1;i<=m;i++){int x,y;cin>>x>>y;unionn(x,y);}for(i=1;i<=n;i++){if(father[i]==i){for(j=w;j>=c[i];j--)dp[j]=max(dp[j],dp[j-c[i]]+d[i]);}}//0-1背包问题解法printf("%d",dp[w]);
}

二分查找

知识点

二分查找是一种在有序数组中查找某一元素的算法。它的基本思想是将数组分为两部分，然后判断目标元素在左边还是右边，再在相应的部分中进行查找，重复这个过程，直到找到目标元素或者确定目标元素不存在。

具体步骤如下：

1. 声明两个指针，一个指向数组的开头，一个指向数组的末尾。

2. 计算数组中间元素的下标，可以使用 mid = ( low+high ) / 2。

3. 比较中间元素与目标元素的大小：

• 如果中间元素等于目标元素，说明找到了目标元素，返回其下标。
• 如果中间元素大于目标元素，说明目标元素在数组的左边，移动右指针到中间元素的前一个位置。
• 如果中间元素小于目标元素，说明目标元素在数组的右边，移动左指针到中间元素的后一个位置。

4. 重复步骤2和步骤3，直到找到目标元素或者确定目标元素不存在。

二分查找的时间复杂度是 O(log n)，其中 n 是数组的长度。这是由于每次查找都将查找范围缩小一半。

int binarySearch(int arr[],int low,int high,int target) 
{while(low<=high) {int mid=(low+high)/2;// 如果目标值等于中间值，则返回中间索引if (arr[mid]==target) return mid;// 如果目标值小于中间值，则在左半部分查找if (arr[mid]>target) high=mid-1;// 如果目标值大于中间值，则在右半部分查找if (arr[mid]<target) low=mid+1;}// 如果没有找到目标值，则返回-1return -1;
}

P2759 奇怪的函数

题目描述

使得 x^x 达到或超过 n 位数字的最小正整数 x 是多少？

输入格式

一个正整数 n。

输出格式

使得 x^x 达到 n 位数字的最小正整数 x。

输入输出样例

输入 #1复制

11

输出 #1复制

10

说明/提示

对于全部数据，1≤n≤2×10^9。

#include<stdio.h>
#include<math.h>
int main()
{long long n,num,mid,low=1,high=2000000000;scanf("%lld",&n);while(low<high){mid=(low+high)/2;num=mid*log10(mid)+1;if(num<n)  low=mid+1;else high=mid;}printf("%lld",low);
}

P8800 [蓝桥杯 2022 国 B] 卡牌

题目描述

这天，小明在整理他的卡牌。

他一共有 n 种卡牌，第 i 种卡牌上印有正整数数 i(i∈[1,n]), 且第 i 种卡牌现有 ai​ 张。

而如果有 n 张卡牌，其中每种卡牌各一张，那么这 n 张卡牌可以被称为一套牌。小明为了凑出尽可能多套牌，拿出了 m 张空白牌, 他可以在上面写上数 i，将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观，决定第 i 种牌最多手写 bi​ 张。

请问小明最多能凑出多少套牌?

输入格式

输入共 3 行，第一行为两个正整数 n，m 。

第二行为 n 个正整数 a1​,a2​,…,an​ 。

第三行为 n 个正整数 b1​,b2​,…,bn​ 。

输出格式

一行，一个整数表示答案。

输入输出样例

输入 #1复制

4 5
1 2 3 4
5 5 5 5

输出 #1复制

3

说明/提示

【样例说明】

这 5 张空白牌中，拿 2 张写 1，拿 1 张写 2，这样每种牌的牌数就变为了 3,3,3,4，可以凑出 3 套牌，剩下 2 张空白牌不能再帮助小明凑出一套。

【评测用例规模与约定】

对于 30%30% 的数据，保证 n≤2000;

对于 100%100% 的数据，保证 n≤2×10^5;n≤2×105;ai​,bi​≤n;m≤n2 。

#include<bits/stdc++.h>
using namespace std;
long long a[200010],b[200010];
long long n,m;
long long low=0,high=1e7;
int check(int num)
{long long sum=0;for(int i=1;i<=n;i++){if(num-a[i]>b[i])return 0;sum=sum+max(num-a[i],(long long)0);}if(sum<=m) return 1;else return 0;
}
int cut()   
{while(low+1<high){int mid=(low+high)/2;if(check(mid)==1)low=mid;else high=mid;}if(check(high)==1)   return high;return low;
}            
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<=n;i++)scanf("%lld",&b[i]);cout<<cut();   
}