P10477 Subway tree systems 题解,c++ 树相关题目
题目
poj 链接
洛谷链接
n n n 组数据,每组数据给定两个 01 01 01 串(长度不超过 3000 3000 3000),意思如下:
- 对于每一个 0 0 0,代表该节点有一个子节点,并前往该子节点。
- 对于每一个 1 1 1,代表返回该节点的父亲节点。
求两个字符串说表示的树是否同构。

思路
考虑对于每一个节点进行递归处理(因为可以知道一个大问题可以拆成多个小问题进行计算)。为方便后续操作,可虚构一个根节点的父亲节点(即在字符串开头加上 0 0 0,结尾加上 1 1 1)。
对于每一个节点,我们可以获得一个字符串代表该节点的子树,首先去掉头尾的字符(即去掉通往父亲节点的边),记 S S S 为字符串, c n t cnt cnt 表示 S S S 从 0 0 0 到 i i i 中 0 0 0 的数量与 1 1 1 的数量的差, j j j 表示儿子的数量。容易得到以下结论:
- 对于 S i = 0 S_i = 0 Si=0,则 c n t ← c n t + 1 cnt \gets cnt + 1 cnt←cnt+1。
- 对于 S i = 0 S_i = 0 Si=0,则 c n t ← c n t − 1 cnt \gets cnt - 1 cnt←cnt−1。
- 对于 c n t = 0 cnt = 0 cnt=0,即一个儿子已经遍历结束,则 j ← j + 1 j \gets j + 1 j←j+1,并统计前一个儿子所代表的子串进行递归。
如果全部儿子所代表的子串递归完毕,可按照字符串排序的方式排列儿子所代表的字符串,并在头尾添上 01 01 01。可以发现,对于两个同构的树,以上操作后获得的字符串相等。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
string a,b;
string paixu(string x) {//cout<<x<<endl;// 分离操作string y = x;int num = x.size(),cnt = 0;x = "";if(num <= 2) return y;for(int i = 1;i < num - 1;i++) x += y[i];num -= 2;string new_string[1505];int j = 1;for(int i = 0;i < num;i++) {if(x[i] == '0') cnt++,new_string[j] += '0';else cnt--,new_string[j] += '1';if(cnt == 0) {j++;}}j--;//递归for(int i = 1;i <= j;i++) new_string[i] = paixu(new_string[i]);//排序for(int i = j;i >= 1;i--) {for(int k = 1;k < i;k++) {if(new_string[k] > new_string[k + 1]) swap(new_string[k],new_string[k + 1]);}}for(int i = 2;i <= j;i++) new_string[1] += new_string[i];//cout<<("0" + new_string[1] + "1")<<endl;return ("0" + new_string[1] + "1");
}
signed main() {scanf("%lld",&T);while(T--) {cin >> a >> b;a = "0" + a + "1";b = "0" + b + "1";if(paixu(a) == paixu(b)) printf("same\n");else printf("different\n");}return 0;
}相关文章:
P10477 Subway tree systems 题解,c++ 树相关题目
题目 poj 链接 洛谷链接 n n n 组数据,每组数据给定两个 01 01 01 串(长度不超过 3000 3000 3000),意思如下: 对于每一个 0 0 0,代表该节点有一个子节点,并前往该子节点。对于每一个 1 1 …...
18.jdk源码阅读之CopyOnWriteArrayList
1. 写在前面 CopyOnWriteArrayList 是 Java 中的一种线程安全的 List 实现,基于“写时复制”(Copy-On-Write)机制。下面几个问题大家可以先思考下,在阅读源码的过程中都会解答: CopyOnWriteArrayList 适用于哪些场景…...
美股:AMD展现乐观前景,挑战AI加速器市场霸主
在科技行业的激烈竞争中,AMD公司近期发布了对当前季度收入的乐观预测,显示出其新推出 一、AMD第三季度营收预期超越分析师平均预期 AMD在周二的声明中预计,第三季度营收将达到约67亿美元,这一数字超出了分析师此前平均预期的66.…...
如何提高计算机视觉技术在复杂环境和低光照条件下的物体识别准确率?
要在复杂环境和低光照条件下提高计算机视觉技术的物体识别准确率,可以采取以下几个方法: 数据增强:在训练集中添加各种复杂环境和低光照条件下的图片,通过增加数据的多样性,使算法能够更好地适应各种场景。 预处理&am…...
ubuntu cmake使用自己版本的qt
给一篇文章参考 https://blog.csdn.net/bank_dreamer/article/details/138678909 自己使用的范例 set(Qt5_DIR "/home/peak/Qt5.14.0/5.14.0/gcc_64/lib/cmake/Qt5")# 设置Qt5的安装目录 #set(CMAKE_PREFIX_PATH "/home/peak/Qt5.14.0")find_package(Qt5…...
Python基础知识笔记---保留字
保留字,也称关键字,是指被编程语言内部定义并保留使用的标识符。 一、保留字概览 二、保留字用途 1. False:表示布尔值假。 2. None:表示空值或无值。 3. True:表示布尔值真。 4. not:布尔逻辑操作符…...
Python面试整理-Web开发
在Python中,Web开发可以利用多种强大的框架和库来构建从简单的静态网页到复杂的动态Web应用。以下是几种流行的Python Web开发框架和相关技术的概述: 1. Flask Flask 是一个轻量级的Web应用框架,它非常灵活,适用于小型到中型项目,或作为构建微服务的基础。Flask的核心非常…...
民大食堂用餐小程序的设计
管理员账户功能包括:系统首页,个人中心,用户管理,商家管理,档口号管理,商家餐品管理,餐品种类管理,购物车管理,订单信息管理 微信端账号功能包括:系统首页&a…...
Linux系统编程(4):消息队列
Linux下的进程通信手段基本上是从Unix平台上的进程通信手段继承而来的。 而对Unix发展做出重大贡献的两大主力AT&T的贝尔实验室 以及 BSD(加州大学伯克利分校的伯克利软件发布中心), 他们在进程间通信方面的侧重点有所不同; 前…...
【初阶数据结构篇】单链表的实现(赋源码)
文章目录 单链表的实现代码位置概念与结构概念:结构: 链表的性质链表的分类单链表的实现单链表的创建和打印及销毁单链表的创建单链表的打印单链表的销毁 单链表的插入单链表头插单链表尾插单链表在指定位置之前插入数据单链表在指定位置之后插入数据 单…...
LeetCode 2844.生成特殊数字的最少操作(哈希表 + 贪心)
给你一个下标从 0 开始的字符串 num ,表示一个非负整数。 在一次操作中,您可以选择 num 的任意一位数字并将其删除。请注意,如果你删除 num 中的所有数字,则 num 变为 0。 返回最少需要多少次操作可以使 num 变成特殊数字。 如…...
昇思MindSpore 应用学习-基于 MindSpore 实现 BERT 对话情绪识别
基于 MindSpore 实现 BERT 对话情绪识别 模型简介 BERT全称是来自变换器的双向编码器表征量(Bidirectional Encoder Representations from Transformers),它是Google于2018年末开发并发布的一种新型语言模型。与BERT模型相似的预训练语言模…...
【初阶数据结构篇】顺序表和链表算法题
文章目录 顺序表算法题移除元素删除有序数组中的重复项合并两个有序数组 链表算法题移除链表元素反转链表链表的中间结点合并两个有序链表链表分割链表的回文结构 顺序表算法题 不熟悉顺序表的可以先了解一下 顺序表实现方法 移除元素 给你一个数组 nums 和一个值 val&#x…...
使用weex进行APP混合开发
Weex 是一个用于构建高性能原生应用的框架,它使用 Vue.js 的语法和组件模型,允许开发者使用 HTML、CSS 和 JavaScript 来编写应用,同时能够编译成原生应用。Weex 主要由阿里巴巴集团开发,并且已经被多个公司采用。 下面是使用 We…...
C++stl大根堆/小根堆的创建与记忆
priority_queue<int, vector<int>, greater<int>> heap; 这行代码在 C 中声明了一个优先队列 heap,其元素类型为 int,使用 vector<int> 作为其底层容器,并且指定了 greater<int> 作为比较函数对象。 这里的关…...
visual studio性能探测器使用案列
visual studio性能探测器使用案列 在visual studio中,我们可以使用自带的工具对项目进行性能探测,具体如下 1.选择性能探查器 Vs2022/Vs2019中打开方式: Vs2017打开方式: 注意最好将解决方案配置为:Release Debu…...
redis的代码开发
redis是什么? 前提:官网地址https://redis.io 1.Redis是一个开源的,key,value格式的,内存型数据结构存储系统;它可用作数据库、缓存和消息中间件。 value支持多种类型的数据结构如strings, hashes, lists, sets, sorted sets with range queries, bitmaps, hyperloglo…...
嗷呜,就问你接不接?
...
避免过拟合,参数大模型强,正则让模型不要走偏
1、加入惩罚项L1【绝对值】 和L2【默认 平方】,降低噪音的影响,减少权重W的值 2、丢弃法 层与层之间加入噪音,只能在全连接层使用 无偏差加入噪音 p为丢弃的概率 x 当概率p是0 否则为除以(1-p) 丢弃概率p 一般为0.1 0.5 def drop_out(x…...
vue+element-ui的列表查询条件/筛选条件太多以下拉选择方式动态添加条件(支持全选、反选、清空)
1、此功能已集成到TQueryCondition组件中 2、最终效果 3、具体源码(新增moreChoose.vue) <template><el-popoverpopper-class"t_query_condition_more":bind"popoverAttrsBind"ref"popover"v-if"allcheckList.length>0"…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
