网站开发招标采购需求,wordpress 推特,wordpress相关面试问题,重庆网站建设哪家强并查集
知识点
并查集是一种数据结构#xff0c;用于处理一些不相交集合的合并及查询问题。它支持两种操作#xff1a;
Find(x)#xff1a;查找元素 x 所属的集合。Union(x, y)#xff1a;将元素 x 所属的集合和元素 y 所属的集合合并。
初始化#xff1a;将每个元素单…并查集
知识点
并查集是一种数据结构用于处理一些不相交集合的合并及查询问题。它支持两种操作
Find(x)查找元素 x 所属的集合。Union(x, y)将元素 x 所属的集合和元素 y 所属的集合合并。
初始化将每个元素单独作为一个集合。
int father[10010];
void init(int n)
{for(int i1;in;i)father[i]i;
}
查找确定某个元素所属的集合。
int find(int i)
{if(ifather[i])return i;else father[i]find(father[i]);return father[i];
}
合并将两个集合合并成一个集合。
void unionn(int i,int j)
{int xfind(i);int yfind(j);father[x]y;
}
并查集的时间复杂度为O(log*n)其中n是元素的个数。
P3367 【模板】并查集
题目描述
如题现在有一个并查集你需要完成合并和查询操作。
输入格式
第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。
接下来 M 行每行包含三个整数 Zi,Xi,Yi 。
当 Zi1 时将 Xi 与 Yi 所在的集合合并。
当 Zi2 时输出 Xi 与 Yi 是否在同一集合内是的输出 Y 否则输出 N 。
输出格式
对于每一个 Zi2 的操作都有一行输出每行包含一个大写字母为 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≤10M≤20。
对于 70%70% 的数据N≤100M≤10^3。
对于 100%100% 的数据1≤N≤10^41≤M≤2×10^51≤Xi,Yi≤NZi∈{1,2}。
#includestdio.h
int father[10010];
void init(int n)
{for(int i1;in;i)father[i]i;
}//初始化
int find(int i)
{if(ifather[i])return i;else father[i]find(father[i]);return father[i];
}//查找
void unionn(int i,int j)
{int xfind(i);int yfind(j);father[x]y;
}//合并
int main()
{int i,n,m,z,x,y;scanf(%d %d,n,m);init(n);for(i1;im;i){scanf(%d %d %d,z,x,y);if(z1) 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^31≤M,t≤10^5。
#includebits/stdc.h
using namespace std;
struct road
{int x,y,t;
}a[100010],b;
bool operator (road a,road b){return a.tb.t;}
int father[1010];
void init(int n)
{for(int i1;in;i)father[i]i;
}//初始化
int find(int i)
{if(ifather[i])return i;return father[i]find(father[i]);
}//查找
int main()
{int i,j,n,m,x,y,cnt0,max0;scanf(%d %d,n,m);init(n);for(i1;im;i)scanf(%d %d %d,a[i].x,a[i].y,a[i].t);sort(a1,a1m);//对a[i].t排序for(i1;im;i) {int xfind(a[i].x);int yfind(a[i].y);if(xy)continue;father[x]y;//合并cnt;maxa[i].tmax?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 个搭配和你现有的钱的数目。
第二行至 n1 行每行有两个整数ci,di表示第 i 朵云的价钱和价值。
第 n2 至 n1m 行 每行有两个整数 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^31≤m≤100 对于 100%100% 的数据满足 1≤n,w≤10^40≤m≤5×10^3。
一道并查集01背包题01背包的限制条件为买A必须买B故可以用并查集将几个物品合成一个大物品然后再用01背包问题做即可。
#includebits/stdc.h
using namespace std;
int father[10010],c[10010],d[10010],dp[10010];
int find(int i)
{if(ifather[i])return i;return father[i]find(father[i]);
}//查找
void unionn(int i,int j)
{int xfind(i);int yfind(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;cinnmw;for(i1;in;i){cinc[i]d[i];father[i]i;}for(i1;im;i){int x,y;cinxy;unionn(x,y);}for(i1;in;i){if(father[i]i){for(jw;jc[i];j--)dp[j]max(dp[j],dp[j-c[i]]d[i]);}}//0-1背包问题解法printf(%d,dp[w]);
}二分查找
知识点
二分查找是一种在有序数组中查找某一元素的算法。它的基本思想是将数组分为两部分然后判断目标元素在左边还是右边再在相应的部分中进行查找重复这个过程直到找到目标元素或者确定目标元素不存在。
具体步骤如下
1. 声明两个指针一个指向数组的开头一个指向数组的末尾。
2. 计算数组中间元素的下标可以使用 mid ( lowhigh ) / 2。
3. 比较中间元素与目标元素的大小
如果中间元素等于目标元素说明找到了目标元素返回其下标。如果中间元素大于目标元素说明目标元素在数组的左边移动右指针到中间元素的前一个位置。如果中间元素小于目标元素说明目标元素在数组的右边移动左指针到中间元素的后一个位置。
4. 重复步骤2和步骤3直到找到目标元素或者确定目标元素不存在。
二分查找的时间复杂度是 O(log n)其中 n 是数组的长度。这是由于每次查找都将查找范围缩小一半。
int binarySearch(int arr[],int low,int high,int target)
{while(lowhigh) {int mid(lowhigh)/2;// 如果目标值等于中间值则返回中间索引if (arr[mid]target) return mid;// 如果目标值小于中间值则在左半部分查找if (arr[mid]target) highmid-1;// 如果目标值大于中间值则在右半部分查找if (arr[mid]target) lowmid1;}// 如果没有找到目标值则返回-1return -1;
}
P2759 奇怪的函数
题目描述
使得 x^x 达到或超过 n 位数字的最小正整数 x 是多少
输入格式
一个正整数 n。
输出格式
使得 x^x 达到 n 位数字的最小正整数 x。
输入输出样例
输入 #1复制
11
输出 #1复制
10
说明/提示
对于全部数据1≤n≤2×10^9。
#includestdio.h
#includemath.h
int main()
{long long n,num,mid,low1,high2000000000;scanf(%lld,n);while(lowhigh){mid(lowhigh)/2;nummid*log10(mid)1;if(numn) lowmid1;else highmid;}printf(%lld,low);
}
P8800 [蓝桥杯 2022 国 B] 卡牌
题目描述
这天小明在整理他的卡牌。
他一共有 n 种卡牌第 i 种卡牌上印有正整数数 i(i∈[1,n]), 且第 i 种卡牌现有 ai 张。
而如果有 n 张卡牌其中每种卡牌各一张那么这 n 张卡牌可以被称为一套牌。小明为了凑出尽可能多套牌拿出了 m 张空白牌, 他可以在上面写上数 i将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观决定第 i 种牌最多手写 bi 张。
请问小明最多能凑出多少套牌?
输入格式
输入共 3 行第一行为两个正整数 nm 。
第二行为 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 。
#includebits/stdc.h
using namespace std;
long long a[200010],b[200010];
long long n,m;
long long low0,high1e7;
int check(int num)
{long long sum0;for(int i1;in;i){if(num-a[i]b[i])return 0;sumsummax(num-a[i],(long long)0);}if(summ) return 1;else return 0;
}
int cut()
{while(low1high){int mid(lowhigh)/2;if(check(mid)1)lowmid;else highmid;}if(check(high)1) return high;return low;
}
int main()
{cinnm;for(int i1;in;i)scanf(%lld,a[i]);for(int i1;in;i)scanf(%lld,b[i]);coutcut();
}
