【蓝桥杯-单链表-网络寻路】

蓝桥杯-单链表-网络寻路

  • 单链表基本操作
    • 操作一:向链表头插入一个数
    • 操作二:在第 k个插入的数后插入一个数
    • 操作三:删除第 k个插入的数后面的一个数;
  • P8605 [蓝桥杯 2013 国 AC] 网络寻路

单链表基本操作

初始化有关操作

// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点,这个点的节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

操作一:向链表头插入一个数

// 将x插到头结点
void add_to_head(int x)
{
    e[idx] = x;取value
    ne[idx] = head,;将idx指向head“指向的节点”
    head = idx;将head指向idx
    idx++;下一个idx(工具人)
}

这里的head可以比较令人费解,head表示的是头节点的下标,其本身不是节点。指向head指向的节点其实就是指向原来的头节点,这样新节点就取而代之成为新的头节点。

操作二:在第 k个插入的数后插入一个数

// 将x插到下标是k的点后面
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx ;
    idx++;
}

操作三:删除第 k个插入的数后面的一个数;

// 将下标是k的点后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

P8605 [蓝桥杯 2013 国 AC] 网络寻路

在这里插入图片描述
思路:

  1. 以第一组数据为例,先将给定的三组节点连起来,且可以双向通讯。
  2. 结果就是 1->2; 2->1; 2->3; 3->2; 1->3; 3->1; 然后我们就可以去拼接了。
  3. 用dfs去枚举子节点,且记录父节点不能重复(题目要求的中间节点必须不同)
    说明:
    1->2->1 不会出现,直接continue到下一个。
    1->2->3->1 就是合法的。
    解释:
    题目的中间节点不重复,转移两个位置只是针对4个节点。节点很多也去其中4个。
    题目的中间节点不合法的情况必然会出现1->2->1这种与父节点相同的,因此只要引入父节点就不会可以保证合法。
  4. 如果cnt==4 那就方案加1。
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=1e5+10;

int h[N],e[N],ne[N];
int ans;
int idx;

void add(int a,int b)//去连接节点
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx;
	idx++;
}

void dfs(int x,int fa,int cnt)//枚举子节点
{
	if(cnt==4)
	{
		ans++;
		return;
	}
	
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa)continue;
		dfs(j,x,cnt+1);
	}
	return ;
}

signed main()
{
	memset(h,-1,sizeof h);
	
	int n,m;
	cin>>n>>m;
	
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	//i为当前节点,对于第一次就是起点;fa为父节点;cnt为当前节点个数
	for(int i=1;i<=n;i++) //枚举起点
	{
		dfs(i,-1,1);
	}
	
	cout<<ans;
	
	return 0;
}

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

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

相关文章

Debian12 使用 nginx 与 php8.2 使用 Nextcloud

最近将小服务器升级了下系统&#xff0c;使用了 debian12 的版本&#xff0c;正好试试 nginx 和 php-fpm 这种方式运行 Nextcloud 这个私有云的配置。 一、基本系统及应用安装 系统&#xff1a;debian12 x86_64 位版本最小安装&#xff0c;安装后可根据自己需求安装一些工具&…

如何优化TCP?TCP的可靠传输机制是什么?

在网络世界中&#xff0c;传输层协议扮演着至关重要的角色&#xff0c;特别是TCP协议&#xff0c;以其可靠的数据传输特性而广受青睐。然而&#xff0c;随着网络的发展和数据量的激增&#xff0c;传统的TCP协议在效率方面遭遇了挑战。小编将深入分析TCP的可靠性传输机制&#x…

【C++初阶】 vector 在OJ中的使用

前言&#xff1a; &#x1f3af;个人博客&#xff1a;Dream_Chaser &#x1f388;博客专栏&#xff1a;C &#x1f4da;本篇内容&#xff1a;只出现一次的数字 和 杨辉三角 OJ 目录 一、只出现一次的数字 题目描述&#xff1a; 二、杨辉三角OJ 题目描述&#xff1a; 一、只…

vue快速入门(七)内联语句

注释很详细&#xff0c;直接上代码 上一篇 新增内容 button点击事件绑定内联语句写法与要求 源码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-wid…

phpstorm设置头部注释和自定义注释内容

先说设置位置&#xff1a; PhpStorm中文件、类、函数等注释的设置在&#xff1a;setting-》Editor-》FIle and Code Template-》Includes-》PHP Function Doc Comment下设置即可&#xff0c;其中方法的默认是这样的&#xff1a; /** ${PARAM_DOC} #if (${TYPE_HINT} ! "…

【第九篇】使用BurpSuite进行编码与解码

Burp存在一个功能&#xff0c;可以识别包含不透明数据&#xff08;例如会话令牌&#xff09;的消息。 如图&#xff1a;如果 Burp 识别所选内容的编码格式&#xff0c;它会自动解码数据。解码后的文本显示在 Inspector面板中。 在编码工具模块中&#xff0c;可对数据进行重复解…

C. MEX Game 1

本题如果我们去模拟这个算法的话会很麻烦&#xff0c;也会TLE&#xff0c;首先我们想 1&#xff0c;对于alice来说&#xff0c;先取小的&#xff0c;对于bob来说先删除alic想取的下一个小的 2&#xff0c;那如果这个数多于两个&#xff0c;那也就是说&#xff0c;alice肯定能…

电工技术学习笔记——正弦交流电路

一、正弦交流电路 1. 正弦量的向量表示法 向量表示方法&#xff1a;正弦交流电路中&#xff0c;相量表示法是一种常用的方法&#xff0c;用于描述电压、电流及其相位关系。相量表示法将正弦交流信号表示为复数&#xff0c;通过复数的运算来描述电路中各种参数的相互关系 …

C/C++预处理过程

目录 前言&#xff1a; 1. 预定义符号 2. #define定义常量 3. #define定义宏 4. 带有副作用的宏参数 5. 宏替换的规则 6. 宏和函数的对比 7. #和## 8. 命名约定 9. #undef 10. 命令行定义 11. 条件编译 12. 头文件的包含 13. 其他预处理指令 总结&#x…

IP地址:是给主机配置的,还是给网卡配置的?

在探索网络的奥秘时&#xff0c;我们经常会遇到一个看似简单但又复杂的问题&#xff1a;IP地址到底是配置在主机上&#xff0c;还是配置在网卡上&#xff1f;为什么我们通常说的是“主机IP地址”呢&#xff1f;让我们一起深入探讨。 1. 网卡与IP地址 &#x1f5a5;️&#x1f…

有同学和我说,深度学习不用特征工程,只有浅层机器学习方法采用特征工程,我说你误会了,我给你好好解释吧!!

1. 通俗解释 浅层机器学习算法&#xff08;如逻辑回归、决策树、支持向量机等&#xff09;和深度学习算法&#xff08;如神经网络&#xff09;在特征工程上的依赖性确实存在一些差异。 浅层机器学习算法的特征工程依赖性&#xff1a; 浅层算法通常需要手工选择和设计特征&…

lua学习笔记5(分支结构和循环的学习)

print("*****************分支结构和循环的学习******************") print("*****************if else语句******************") --if 条件 then end a660 b670 --单分支 if a<b thenprint(a) end --双分支 if a>b thenprint("满足条件")…

RGB三通道和灰度值的理解

本文都是来自于chatGPT的回答!!! 目录 Q1:像素具有什么属性?Q2:图像的色彩是怎么实现的?Q3:灰度值和颜色值是一个概念吗?Q4:是不是像素具有灰度值&#xff0c;也有三个颜色分量RGB&#xff1f;Q5:灰度图像是没有色彩的吗&#xff1f;Q6: 彩色图像是既具有灰度值也具有RGB三…

11_printf函数移植串口通信

printf函数移植串口通信 printf函数移植串口通信串口显示汉字乱码问题解决代码 printf函数移植串口通信 MicroLIB是Keil为嵌入式平台优化的一个精简库 --no-multibyte-chars 串口显示汉字乱码问题解决 法一 法二 代码 主函数 #include "stm32f10x.h" …

[StartingPoint][Tier1]Sequel

Task 1 During our scan, which port do we find serving MySQL? (在扫描过程中&#xff0c;我们发现哪个端口为 MySQL 提供服务&#xff1f;) 3306 Task 2 What community-developed MySQL version is the target running? (目标正在运行哪个社区开发的 MySQL 版本&…

详解 Redis 在 Centos 系统上的安装

详解 Redis 在 Centos 系统上的安装 1. 使用 yum 安装 Redis 5 如果是Centos8&#xff0c;yum 仓库中默认的 redis 版本就是5&#xff0c;直接 yum install 即可 如果是Centos7, yum 仓库中默认的 redis 版本是3系列&#xff0c;版本就比较老 使用yum list | grep redis命令…

【问题解决】电脑突然 总蓝屏,这份火爆全网的452页Linux运维 Framework内核解析

“你的设备遇到问题&#xff0c;需要重启。我们智手机某些错误信息&#xff0c;然后为你重新启动。” 电脑突然就蓝屏了&#xff0c;终止代码显示&#xff1a;UNEXPECTED_STORE_EXCEPTION。 原因分析&解决方案 可能性原因解决方案1出现蓝屏的情况&#xff0c;大部分原因都…

【C++ STL容器适配器】queue 队列

文章目录 【 1. 基本原理 】【 1. queue 的创建 】2.1 使用默认的 deque 基础容器创建一个空的 queue2.2 指定基础容器创建 queue2.3 通过基础容器来初始化 queue 容器适配器2.4 通过一个 queue 初始化另一个 queue 【 3. queue 支持的成员函数 】 【 1. 基本原理 】 STL queu…

ChatGPT(3.5版本)开放无需注册:算力背后的数据之战悄然打响

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…

AI Agents产品图谱+网站合集

这个网站收集了市面受欢迎的项目&#xff0c;包括开源项目和闭源项目以及公司 地址&#xff1a;通过浏览列表中的AI代理项目和公司&#xff0c;社区里的创业者可以了解当前市场上的主要玩家和他们的产品特点&#xff0c;进行市场趋势分析和竞争分析。