2.18学习总结

链式前向星的处理和建立

tarjan对割点和缩点的使用

拓扑排序

链式前向星：

预处理：

struct edge{
	int from;
	int to;
	int next;
}e[N];
int n,m,head[N],dfn[N],low[N],tot,color[N],num[N],out[N],s,instack[N],id;

处理：

void add(int u,int v){	
	e[++tot].from=u;
	e[tot].to=v;
	e[tot].next=head[u];
	head[u]=tot;
}

tarjan算法求割点，以及tarjan的缩点法

割点（割顶）https://www.luogu.com.cn/problem/P3388

题目描述

给出一个 �n 个点，�m 条边的无向图，求图的割点。

输入格式

第一行输入两个正整数 �,�n,m。

下面 �m 行每行输入两个正整数 �,�x,y 表示 �x 到 �y 有一条边。

输出格式

第一行输出割点个数。

第二行按照节点编号从小到大输出节点，用空格隔开。

输入输出样例

输入 #1复制

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

输出 #1复制

1
5

说明/提示

对于全部数据，1≤�≤2×1041≤n≤2×104，1≤�≤1×1051≤m≤1×105。

点的编号均大于 00 小于等于 �n。

tarjan图不一定联通。

对一个点是否是割点的判断：

如果一个点是割点那么就一定存在两种情况

情况一：这个点不是根节点，且low[x的子节点]>=dfn[x]（x的子节点回溯后的时间仍然大于等于这个节点的时间戳，那么x就是割点）

情况二：如果一个点事根节点，且他有至少两个儿子，那这个点也一定是割点

求割边就是:假设x->y是桥，那么low[y]>low[x]

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+4;
int head[N],tot,n,m,low[N],dfn[N],s,cut[N];

struct	edge{	//链式前向星 
	int from;	//数值域 
	int to;
	int next;	//指针域 
}e[N];

void add(int u,int v){	//构造链式前向星 
	e[++tot].from=u;	//数组下标为tot的位置存放一条边的关系 
	e[tot].to=v;
	e[tot].next=head[u];	//由于是链表的头部插入，所以新来的节点，指针指向下一个节点 
	head[u]=tot;			//头指针变成新来的指针，头指针的下标为当前节点的下标，意味着以u为比编号的链表的头是tot 
}

void tarjan(int u,int fa){	//tarjan算法求割点 
	dfn[u]=low[u]=++s;	//dfn记录时间戳，low记录最小回溯时间 
	int child=0;	//记录子树数量 
	for (int i=head[u];i;i=e[i].next){	//遍历当前节点的所有邻居节点 
		int v=e[i].to;
		if (!dfn[v]){	//如果没有被访问过，那么就继续深度搜索 
			tarjan(v,fa);	
			low[u]=min(low[u],low[v]);	//子节点更新后，也需要更新父节点 
			//割点有两种，一种：是父亲节点且有大于等于两个的子树,第二中是，子节点回溯最短时间大于当前时间戳
			if (low[v]>=dfn[u] && u!=fa){	 
				cut[u]=1;
			}
			if (u==fa) child++;
		}
		low[u]=min(low[u],dfn[v]);	//如果u的邻居节点v已经访问过了，那么就表示v比u更早被访问，所以需要更新u节点 
	}
	if (u==fa && child>=2){
		cut[u]=1;
	}
}

int main(){
	int cnt=0;
	cin>>n>>m;
	for (int i=1;i<=m;++i){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for (int i=1;i<=n;++i){
		if (!dfn[i]) tarjan(i,i);
	}
	for (int i=1;i<=n;++i){
		if (cut[i]) cnt++;
	}
	cout<<cnt<<endl;
	for (int i=1;i<=n;++i){
		if (cut[i]) cout<<i<<" ";
	}
}

受欢迎的牛 Ghttps://www.luogu.com.cn/problem/P2341

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 �A 喜欢 �B，�B 喜欢 �C，那么 �A 也喜欢 �C。牛栏里共有 �N 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

输入格式

第一行：两个用空格分开的整数：�N 和 �M。

接下来 �M 行：每行两个用空格分开的整数：�A 和 �B，表示 �A 喜欢 �B。

输出格式

一行单独一个整数，表示明星奶牛的数量。

输入输出样例

输入 #1复制

3 3
1 2
2 1
2 3

输出 #1复制

1

说明/提示

只有 33 号奶牛可以做明星。

【数据范围】

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

对于 30%30% 的数据，�≤103N≤103，�≤2×104M≤2×104。

对于 70%70% 的数据，�≤5×103N≤5×103，�≤5×104M≤5×104。

对于 100%100% 的数据，1≤�≤1041≤N≤104，1≤�≤5×1041≤M≤5×104。

#include <bits/stdc++.h>
using namespace std;

const int N=5e4+5;

struct edge{
	int from;
	int to;
	int next;
}e[N];

int n,m,head[N],dfn[N],low[N],tot,color[N],num[N],out[N],s,instack[N],id;
stack<int>st;

void add(int u,int v){	
	e[++tot].from=u;
	e[tot].to=v;
	e[tot].next=head[u];
	head[u]=tot;
}

void tarjan(int u){	//tarjan缩点法 ,和割点法的区别在于多了栈，染色数组 
	dfn[u]=low[u]=++s;
	st.push(u);
	instack[u]=1;
	for (int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if (!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if (instack[v]){
			low[u]=min(low[u],low[v]);
		}
	}
	if (dfn[u]==low[u]){
		id++;
		while (st.top()!=u){
			color[st.top()]=id;		//一个SCC里面的编号，染同样的颜色 
			num[id]++;
			instack[st.top()]=0;
			st.pop();
		}
		color[st.top()]=id;
		num[id]++;
		instack[st.top()]=0;
		st.pop();
	}
}

int main(){
	cin>>n>>m;
	for (int i=1;i<=m;++i){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	for (int i=1;i<=n;++i){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	for (int i=1;i<=n;++i){
		for (int j=head[i];j;j=e[j].next){
			if (color[i] != color[e[j].to]){
				out[color[i]]++;
			}
		}
	}
	int ans=0;
	for (int i=1;i<=id;++i){
		if (out[i]==0){
			if (ans){
				cout<<0;
				return 0;
			}
			ans=i;
		}
	}
	cout<<num[ans];
}

拓扑排序https://www.luogu.com.cn/problem/B3644

题目描述

有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。

输入格式

第 11 行一个整数 �N（1≤�≤1001≤N≤100），表示家族的人数。接下来 �N 行，第 �i 行描述第 �i 个人的后代编号 ��,�ai,j​，表示 ��,�ai,j​ 是 �i 的后代。每行最后是 00 表示描述完毕。

输出格式

输出一个序列，使得每个人的后辈都比那个人后列出。如果有多种不同的序列，输出任意一种即可。

输入输出样例

输入 #1复制

5
0
4 5 1 0
1 0
5 3 0
3 0

输出 #1复制

2 4 5 3 1

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f

const int N=105;

struct edge{
	int from;
	int to;
	int next;
}e[N];

int head[N],tot,n,in[N];

void add(int u,int v){
	e[++tot].from=u;
	e[tot].to=v;
	e[tot].next=head[u];
	head[u]=tot;
}

void topo(){
	queue<int>q;
	for (int i=1;i<=n;++i){		//入度为0的节点输出并入队 
		if (!in[i]) cout<<i<<" ",q.push(i);
	}
	while (!q.empty()){
		int x=q.front(); q.pop();
		for (int i=head[x];i;i=e[i].next){
			in[e[i].to]--;	//出队后，相邻节点的入度就减1 
			if (!in[e[i].to]){	//如果入度为0，就输出并入队 
				cout<<e[i].to<<" ";
				q.push(e[i].to);
			}
		}
	}
}

signed main(){
	cin>>n;
	for (int i=1;i<=n;++i){
		int m;
		while (true){
			cin>>m;
			if (!m) break;
			add(i,m);
			in[m]++;	//长辈指向后辈,但后辈不能指向长辈,后辈的入度+1 
		}
	}
	topo();
}

刷题：

堆https://www.luogu.com.cn/problem/P3378

题目描述

给定一个数列，初始为空，请支持下面三种操作：

  1. 给定一个整数 �x，请将 �x 加入到数列中。

  2. 输出数列中最小的数。

  3. 删除数列中最小的数（如果有多个数最小，只删除 11 个）。

输入格式

第一行是一个整数，表示操作的次数 �n。
接下来 �n 行，每行表示一次操作。每行首先有一个整数 ��op 表示操作类型。

  • 若 ��=1op=1，则后面有一个整数 �x，表示要将 �x 加入数列。

  • 若 ��=2op=2，则表示要求输出数列中的最小数。

  • 若 ��=3op=3，则表示删除数列中的最小数。如果有多个数最小，只删除 11 个。

输出格式

对于每个操作 22，输出一行一个整数表示答案。

输入输出样例

输入 #1复制

5
1 2
1 5
2
3
2

输出 #1复制

2
5

说明/提示

【数据规模与约定】

  • 对于 30%30% 的数据，保证 �≤15n≤15。

  • 对于 70%70% 的数据，保证 �≤104n≤104。

  • 对于 100%100% 的数据，保证 1≤�≤1061≤n≤106，1≤�<2311≤x<231，��∈{1,2,3}op∈{1,2,3}。

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f

const int N=1e6+5;

int op,n;
priority_queue<int,vector<int>,greater<int> >q;

signed main(){
	cin>>n;
	while (n--){
		cin>>op;
		if (op==1){
			int x; cin>>x;
			q.push(x);
		}else if (op==2){
			cout<<q.top()<<endl;
		}else if (op==3){
			q.pop();
		}
	}
}

黑匣子https://www.luogu.com.cn/problem/P1801

题目描述

Black Box 是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量 �i。最开始的时候 Black Box 是空的．而 �=0i=0。这个 Black Box 要处理一串命令。

命令只有两种：

  • ADD(x)：把 �x 元素放进 Black Box;

  • GET：�i 加 11，然后输出 Black Box 中第 �i 小的数。

记住：第 �i 小的数，就是 Black Box 里的数的按从小到大的顺序排序后的第 �i 个元素。

我们来演示一下一个有11个命令的命令串。（如下表所示）

序号

操作

�i

数据库

输出

1

ADD(3)

00

33

/

2

GET

11

33

33

3

ADD(1)

11

1,31,3

/

4

GET

22

1,31,3

33

5

ADD(-4)

22

−4,1,3−4,1,3

/

6

ADD(2)

22

−4,1,2,3−4,1,2,3

/

7

ADD(8)

22

−4,1,2,3,8−4,1,2,3,8

/

8

ADD(-1000)

22

−1000,−4,1,2,3,8−1000,−4,1,2,3,8

/

9

GET

33

−1000,−4,1,2,3,8−1000,−4,1,2,3,8

11

10

GET

44

−1000,−4,1,2,3,8−1000,−4,1,2,3,8

22

11

ADD(2)

44

−1000,−4,1,2,2,3,8−1000,−4,1,2,2,3,8

/

现在要求找出对于给定的命令串的最好的处理方法。ADD 命令共有 �m 个，GET 命令共有 �n 个。现在用两个整数数组来表示命令串：

  1. �1,�2,⋯ ,��a1​,a2​,⋯,am​：一串将要被放进 Black Box 的元素。例如上面的例子中 �=[3,1,−4,2,8,−1000,2]a=[3,1,−4,2,8,−1000,2]。

  2. �1,�2,⋯ ,��u1​,u2​,⋯,un​：表示第 ��ui​ 个元素被放进了 Black Box 里后就出现一个 GET 命令。例如上面的例子中 �=[1,2,6,6]u=[1,2,6,6] 。输入数据不用判错。

输入格式

第一行两个整数 �m 和 �n，表示元素的个数和 GET 命令的个数。

第二行共 �m 个整数，从左至右第 �i 个整数为 ��ai​，用空格隔开。

第三行共 �n 个整数，从左至右第 �i 个整数为 ��ui​，用空格隔开。

输出格式

输出 Black Box 根据命令串所得出的输出串，一个数字一行。

输入输出样例

输入 #1复制

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

输出 #1复制

3
3
1
2

说明/提示

数据规模与约定

  • 对于 30%30% 的数据，1≤�,�≤1041≤n,m≤104。

  • 对于 50%50% 的数据，1≤�,�≤1051≤n,m≤105。

  • 对于 100%100% 的数据，1≤�,�≤2×105,∣��∣≤2×1091≤n,m≤2×105,∣ai​∣≤2×109，保证 �u 序列单调不降。

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f

const int N=2e5+5;

int a[N],u[N],m,n,s,k;

priority_queue<int>q1;
priority_queue<int,vector<int>,greater<int> >q2;

signed main(){
	cin>>n>>m;
	k=1;
	for (int i=1;i<=n;++i){
		cin>>a[i];
	}
	for (int i=1;i<=m;++i){
		cin>>u[i];
	}
	for (int i=1;i<=n;++i){
		q1.push(a[i]);
		if (q1.size()>s){
			q2.push(q1.top());
			q1.pop();
		}
		while (u[k]==i){
			s++;
			cout<<q2.top()<<endl;
			q1.push(q2.top());
			q2.pop();
			k++;
		}
	}
}

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

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

相关文章

svg之全局组件，配合雪碧图解决vue2的svg优化问题

svg之全局组件，配合雪碧图解决vue2的svg优化问题

这里是vue2中的svg的完整解决方案的另一篇。 <template><svg :class"svgClass"><use :xlink:href"#${name}"></use></svg> </template><script>export default {name: icon,props: {name: {type: String,requi…
阅读更多...
lv15 input子系统框架、外设驱动开发 5

lv15 input子系统框架、外设驱动开发 5

一、input子系统基本框架 在我们日常的Linux系统中&#xff0c;存在大量的输入设备&#xff0c;例如按键、鼠标、键盘、触摸屏、摇杆等&#xff0c;他们本身就是字符设备&#xff0c;linux内核将这些字符设备的共同性抽象出来&#xff0c;简化驱动开发建立了一个input子系统。 …
阅读更多...
关于Spring Boot应用系统避免因为日切（日期切换）导致请求结果变更的一种解决方案

关于Spring Boot应用系统避免因为日切（日期切换）导致请求结果变更的一种解决方案

一、前言 在系统开发过程中&#xff0c;有些业务功能面临日切&#xff08;日期切换&#xff09;问题&#xff0c;比如结息跑批问题&#xff0c;在当前工作日临近24点的时候触发结息&#xff0c;实际交易时间我们预期的是当前时间&#xff0c;但是由于业务执行耗时&#xff0c;…
阅读更多...
【EI会议征稿通知】第五届城市工程与管理科学国际会议（ICUEMS 2024）

【EI会议征稿通知】第五届城市工程与管理科学国际会议（ICUEMS 2024）

【Scopus稳定检索】第五届城市工程与管理科学国际会议&#xff08;ICUEMS 2024&#xff09; 2024 5th International Conference on Urban Engineering and Management Science 第五届城市工程与管理科学国际会议&#xff08;ICUEMS 2024&#xff09;将于2024年5月31日-6月2日…
阅读更多...
告警能力中台设计与实践（三）——告警通知

告警能力中台设计与实践（三）——告警通知

一、告警消息与告警通知 1、告警消息 正如笔者在最开始所写的那样&#xff0c;第三方服务通过调用能力中台的OpenAPI实现告警发起&#xff0c;并且每一次的告警请求都会创建、归档为一条告警消息&#xff08;AlarmMsg&#xff09;。 这样的消息是无状态的&#xff0c;并且对…
阅读更多...
Python：变量与数据类型

Python：变量与数据类型

目录 一、变量 1.1 强数据类型与弱数据类型 1.2 全局函数 1.3 变量的命名规范 二、数据类型 2.1 基本数据类型 2.2 复合数据类型&#xff08;引用数据类型&#xff09; 三、数据类型转换 一、变量 变量&#xff1a;顾名思义&#xff0c;变化的量。在python中代指运行时…
阅读更多...
【Java面试】MongoDB

【Java面试】MongoDB

目录 1、mongodb是什么&#xff1f;2、mongodb特点什么是NoSQL数据库&#xff1f;NoSQL和RDBMS有什么区别&#xff1f;在哪些情况下使用和不使用NoSQL数据库&#xff1f;NoSQL数据库有哪些类型?启用备份故障恢复需要多久什么是master或primary什么是secondary或slave系列文章版…
阅读更多...
【Redis篇】详解布隆过滤器（原理 | 操作 | 代码）

【Redis篇】详解布隆过滤器（原理 | 操作 | 代码）

文章目录 &#x1f354;简述布隆过滤器&#x1f33a;原理&#x1f6f8;存入过程&#x1f6f8;查询过程 &#x1f3f3;️‍&#x1f308;优缺点⭐优点⭐缺点 &#x1f339;代码实现&#xff08;本地&#xff09;&#x1f339;代码实现&#xff08;分布式&#xff09; &#x1f3…
阅读更多...
Redis 集群(Cluster)

Redis 集群(Cluster)

集群概念 Redis 的哨兵模式&#xff0c;提高了系统的可用性&#xff0c;但是正在用来存储数据的还是 master 和 slave 节点&#xff0c;所有的数据都需要存储在单个 master 和 salve 节点中。 如果数据量很大&#xff0c;接近超出了 master / slave 所在机器的物理内存&#…
阅读更多...
HTTP请求报文与响应报文格式

HTTP请求报文与响应报文格式

HTTP请求报文与响应报文格式 HTTP请求报文与响应报文格式 请求报文包含四部分&#xff1a; a、请求行&#xff1a;包含请求方法、URI、HTTP版本信息b、请求首部字段c、请求内容实体d、空行 响应报文包含四部分&#xff1a; a、状态行&#xff1a;包含HTTP版本、状态码、状态码…
阅读更多...
【从Python基础到深度学习】7. 使用scp命令实现主机间通讯

【从Python基础到深度学习】7. 使用scp命令实现主机间通讯

一、生成 SSH 密钥对 ssh-keygen 是一个用于生成 SSH 密钥对的命令行工具&#xff0c;用于身份验证和加密通信 ssh-keygen 二、将本地主机上的 SSH 公钥添加到远程主机 ssh-copy-id 命令用于将本地主机上的 SSH 公钥添加到远程主机上的 authorized_keys 文件中&#xff0c;…
阅读更多...
《苍穹外卖》知识梳理P9-定时任务、来单提醒与用户催单

《苍穹外卖》知识梳理P9-定时任务、来单提醒与用户催单

一.定时任务 实现定时任务可以使用spring家族中的sprinig-task&#xff1b; 1.1 spring-task spring-task是Spring框架的任务调度工具&#xff0c;可以按照约定的时间自动执行某个代码逻辑&#xff1b; 应用场景 信用卡每月归还贷款提醒&#xff0c;定时任务检查&#xff…
阅读更多...
Jetpack Compose 第 2 课：布局

Jetpack Compose 第 2 课：布局

点击查看&#xff1a;Jetpack Compose 教程 点击查看&#xff1a;Composetutorial 代码 简介 Jetpack Compose 是用于构建原生 Android 界面的新工具包。它使用更少的代码、强大的工具和直观的 Kotlin API&#xff0c;可以帮助您简化并加快 Android 界面开发。 在本教程中&a…
阅读更多...
【springboot+vue项目（十四）】基于Oauth2的SSO单点登录（一）整体流程介绍

【springboot+vue项目（十四）】基于Oauth2的SSO单点登录（一）整体流程介绍

场景&#xff1a;现在有一个前后端分离的系统&#xff0c;前端框架使用vue-element-template&#xff0c;后端框架使用springbootspringSecurityJWTRedis&#xff08;登录部分&#xff09;现在需要接入到已经存在的第三方基于oauth2.0的非标准接口统一认证系统。 温馨提示&…
阅读更多...
html表格标签(下)：lable标签，select标签和textara标签

html表格标签(下)：lable标签，select标签和textara标签

html表格标签(下)&#xff1a;lable标签&#xff0c;select标签和textarea标签 lable标签 搭配 input 使用,点击 label 标签就能选中对应的单选/复选框, 能够提升用户体验。 for 属性: 指定当前 label 和哪个相同 id 的 input 标签对应 (此时点击才是有用的) 运行效果&#x…
阅读更多...
php数组运算符 比较 isset、is_null、empty的用法和区别

php数组运算符 比较 isset、is_null、empty的用法和区别

php数组运算符 1. 数组运算符2. 判断两个数组是否相等3. isset、is_null、empty的用法和区别 1. 数组运算符 注意&#xff1a;只会保留第一个数组中的键值对&#xff0c;而忽略后面数组中相同键名的元素&#xff0c;如果想要合并两个数组并覆盖相同键名的元素&#xff0c;可以…
阅读更多...
obsidian的Workbooks插件

obsidian的Workbooks插件

学习目标&#xff1a; 学会使用obsidian 学习内容&#xff1a; obsidian咖啡豆教程 | Obsidian的Excel管理解密|Workbooks插件 直接在obsidian中插入表格编辑 但是在实际的使用过程中不好。虽然设置了自动保存&#xff0c;但是实际有时没有保存 读取外部excel文件进行修改 默…
阅读更多...
【Jvm】性能调优（拓展）Jprofiler如何监控和解决死锁、内存泄露问题

【Jvm】性能调优（拓展）Jprofiler如何监控和解决死锁、内存泄露问题

文章目录 Jprofiler简介1.安装及IDEA集成Jprofiler2.如何监控并解决死锁3.如何监控及解决内存泄露(重点)4.总结5.后话 Jprofiler简介 Jprofilers是针对Java开发的性能分析工具(免费试用10天), 可以对Java程序的内存,CPU,线程,GC,锁等进行监控和分析, 1.安装及IDEA集成Jprofil…
阅读更多...
VFH特征的使用(一)

VFH特征的使用(一)

一、SHOT特征描述符可视化 C #include <pcl/point_types.h> #include <pcl/point_cloud.h> #include <pcl/io/pcd_io.h> #include <pcl/features/normal_3d_omp.h> #include <pcl/registration/correspondence_estimation.h> #include <boo…
阅读更多...
软件测试项目测试报告总结

软件测试项目测试报告总结

测试计划概念&#xff1a;就在软件测试工作实施之前明确测试对象&#xff0c;并且通过资源、时间、风险、测试范围和预算等方面的综合分析和规划&#xff0c;保证有效的实施软件测试。 需求挖掘的6个方面&#xff1a; 1、输入方面 2、处理方面 3、结果输出方面 4、性能需求…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站