用欧拉路径判断图同构推出reverse合法性:1116T4
http://cplusoj.com/d/senior/p/SS231116D
假设我们要把 a a a 变成 b b b,我们在 a i a_i ai 和 a i + 1 a_{i+1} ai+1 之间连边, b b b 同理,则 a a a 能变成 b b b 的充要条件是两图 A , B A,B A,B 同构。
必要性显然,因为无论如何reverse都不会改变图的形态。我们现在要证明的是图的任意欧拉路径都可以通过reverse构造出来。
考虑第一个 a i ≠ b i a_i\neq b_i ai=bi 的位置 i i i,设 x = b i , y = b i − 1 = a i − 1 x=b_i,y=b_{i-1}=a_{i-1} x=bi,y=bi−1=ai−1。在图同构是必然存在一个 a k = x a_k=x ak=x,且 a k − 1 a_{k-1} ak−1 或 a k + 1 a_{k+1} ak+1 其中一个等于 y y y。(注意 A , B A,B A,B 同构)
如果 a k + 1 = y a_{k+1}=y ak+1=y,我们直接reverse即可。如果 a k − 1 = y a_{k-1}=y ak−1=y,我们只需要考虑 ( x , y ) (x,y) (x,y) 这条边在 A A A 中是不是桥就行。因为在 B B B 中一定不是桥(注意到 y y y 必然出现两次)
因为如果在 A A A 中是桥, B B B 中不是,说明 A , B A,B A,B 不同构,和我们的前提冲突。
如果在 A A A 中不是桥,说明对于这条边来说 A , B A,B A,B 同构,说明一定存在 i ≤ l ≤ k − 1 , r > k + 1 i\le l \le k-1,r>k+1 i≤l≤k−1,r>k+1 满足 a l = a r a_l=a_r al=ar。我们直接按 [ l , r ] [l,r] [l,r] reverse即可。因此一定可以构造
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>using namespace std;struct xorShift128Plus {unsigned long long k1, k2;unsigned long long gen() {register unsigned long long k3 = k1, k4 = k2;k1 = k4;k3 ^= k3 << 23;k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);return k2 + k4;}int gen(int w) {return gen()%w;}
}rnd;const int S=5000005;
#define pb push_back
#define fi first
#define se secondint n, a[S], t[S], k, i, tot;
bool b[S];
int ans[S];
vector<pair<int, int> >G[S]; void dfs(int x) {for(; t[x]<G[x].size(); ){auto p=G[x][t[x]]; ++t[x]; if(b[p.se]) continue; int y=p.fi; b[p.se]=1; dfs(y); }ans[++tot]=x;
}void cun(int x, int y) {G[x].pb({y, ++k}); G[y].pb({x, k});
}int main()
{freopen("life.in","r",stdin);freopen("life.out","w",stdout);#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endifint t;scanf("%d%d",&n,&t);if(t==0) for(int i=1;i<=n;i++) scanf("%d",&a[i]);else{int ra;scanf("%d%llu%llu",&ra,&rnd.k1,&rnd.k2);for(int i=1;i<=n;i++) a[i]=rnd.gen(ra)+1;}// cun(n+1, a[1]); cun(n+2, a[n]); for(i=1; i<n; ++i) cun(a[i], a[i+1]); for(i=1; i<=n+2; ++i) {sort(G[i].begin(), G[i].end());
// reverse(G[i].begin(), G[i].end()); }dfs(a[1]); reverse(ans+1, ans+n+1); /*code here*/if(t==0){for(int i=1;i<=n;i++) printf("%d ",ans[i]);printf("\n");}else{int bse=1919839,p=1000000007;int mul=1,res=0;for(int i=1;i<=n;i++,mul=1ll*mul*bse%p) res=(res+1ll*ans[i]*mul%p)%p;printf("%d\n",res);}return 0;
}
相关文章:
用欧拉路径判断图同构推出reverse合法性:1116T4
http://cplusoj.com/d/senior/p/SS231116D 假设我们要把 a a a 变成 b b b,我们在 a i a_i ai 和 a i 1 a_{i1} ai1 之间连边, b b b 同理,则 a a a 能变成 b b b 的充要条件是两图 A , B A,B A,B 同构。 必要性显然࿰…...
高阶数据结构---树状数组
文章目录 楼兰图腾一个简单的整数问题 一个简单的整数问题2谜一样的牛 一、楼兰图腾OJ链接 二、一个简单的整数问题OJ链接 三、一个简单的整数问题2OJ链接 四、谜一样的牛OJ链接...
如何保护PayPal账户安全:防止多个PayPal账号关联?
PayPal是一家全球领先的在线支付平台,已经成为全球最受欢迎的在线支付工具之一,广泛应用于电子商务、跨境交易和个人之间的付款,很多跨境卖家的支付平台都会选择PayPal。PayPal支持全球多个国家和20多种货币在线支付,并且能即时收…...
关于 Spring :松耦合、可配置、IOC、AOP
关于 Spring :松耦合、可配置、IOC、AOP 文章目录 关于 Spring :松耦合、可配置、IOC、AOP一、关于 Spring1、概述2、Spring 的“松耦合”体现在哪3、Spring 的“可配置”体现在哪4、Spring 的 IOC 容器的主要作用5、Spring 的 AOP 容器的主要作用 一、关…...
pytorch tensor数据类型转换为python数据
一、item() input: x torch.tensor([1.0]) x.item()output: 1.0二、tolist() input: a torch.randn(2, 2) a.tolist() a[0,0].tolist()output: [[0.012766935862600803, 0.5415473580360413],[-0.08909505605697632, 0.7729271650314331]]0.012766935862600803...
HarmonyOS开发:动态共享包的依赖问题
一、共享包的依赖方式 在需要依赖的模块包目录下oh-package.json5文件中添加依赖: "dependencies": {"ohos/srpaasUI": "file:../../srpaasUI","ohos/srbusiness": "file:../../feature/srbusiness"} 引入之后…...
中睿天下加入中关村华安关键信息基础设施安全保护联盟
近日,中睿天下正式加入中关村华安关键信息基础设施安全保护联盟,成为其会员单位。 中关村华安关键信息基础设施安全保护联盟是由北京市科学技术委员会、中关村科技园区管理委员会指导支持,经北京市民政局批准,于2023年8月正式注册…...
【c++STL算数仿函数,关系仿函数,逻辑仿函数】
文章目录 C STL中的算数、关系和逻辑仿函数1. 算数仿函数2. 关系仿函数3. 逻辑仿函数 C STL中的算数、关系和逻辑仿函数 STL(Standard Template Library)是C标准库的一部分,提供了许多强大的工具和功能,其中包括仿函数࿰…...
产品经理的能力模型是什么?
一个产品的成功需要团队成员利用自己的技能共同合作完成。作为团队的核心和产品的主导者,产品经理需要具备一定的能力模型,以更好地完成工作。下面从五个方面进行解答。 首先,产品经理需要具备需求分析的能力。需求是用户在特定场景下产生的欲…...
缓存和DB一致性
读操作,一般是先查询缓存,查询不到再查询数据库,最后回写进缓存。 写操作,究竟是先删除(更新)缓存,再更新数据库,还是先更新数据库,再删除(更新)缓存呢? 1、给缓存设置过期时间 适用…...
netty websockt之断连重试
断连重试有以下两点考虑: 1、连接异常,比如网络抖动导致连接失败; 2、连接过程中断开连接重试; 主要用到两个工具类: ChannelFutureListener监听ChannelFuture..isSuccess(); ChannelInboundHandlerAd…...
【Gateway】基于ruoyi-cloud-plus项目,gateway局部过滤器和过滤返回以及集成nacos
1.使用Gateway路由转发 1.1标题引入依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-gateway</artifactId></dependency>1.2添加YML配置 spring:cloud:gateway:# 打印请求日志(自定义)…...
mysql -mmm
MMM(Master-Master replication manager for MvSQL,MySQL主主复制管理器) 是一套支持双主故障切换和双主日常管理的脚本程序。MMM 使用 Perl 语言开发,主要用来监控和管理 MySQL Master-Master (双主)复制&…...
C++初阶 类和对象(下)
目录 一、拷贝构造函数 1.1 什么是拷贝构造函数? 1.2 为什么得是引用? 1.3 使用拷贝构造函数 1.4 拷贝构造函数有什么用? 二、运算符重载 2.1 什么是运算符重载? 2.2 尝试前须知 2.3 常见运算符重载 2.3.1运算符重载 …...
使用Postman进行压力测试
1.打开Postman新建测试接口 2.点击右边保存,选择一个文件集合,如果没有就创建,然后保存 就是这个东西,这里不便展示出来,压力测试需要在文件夹里面进行 3.选择要测试的接口,iterations 表示请求发起次数&a…...
AI视频检索丨历史视频标签化,助力重要事件高效溯源
随着科技的不断发展,安全监控已成为我们生活中不可或缺的一部分。当发生盗窃、人员走失、安全事故等重要事件时,常常需要通过查看视频回放了解事情经过,为解决问题提供证据或指明查找方向。但是,人工查看视频回放往往费时费力&…...
【前段基础入门之】=>CSS3新特性 响应式布局
文章目录 概念媒体查询媒体类型媒体特性媒体运算符 概念 所谓对响应式布局方案的理解,众说纷纭,核心点就是同一套代码在不同尺度屏幕下的布局呈现方式的不同 社区中有很多人分享,并列出了多种实现响应式布局的方案,比如【 rem&…...
【Java 进阶篇】JQuery 遍历:发现元素的魔法之旅
欢迎来到 JQuery 的奇妙世界,一个充满活力和灵感的地方。在这个世界里,我们将一起探讨 JQuery 的遍历功能,这是一个让你轻松发现和操作网页元素的神奇工具。无需太多前端经验,只要有一颗探险的心,你就能在 JQuery 遍历…...
合肥数字孪生赋能工业制造,加速推进制造业数字化转型
聚焦国家战略需求和先进制造业发展方向,加快数字化发展战略部署,数字孪生、工业互联网、工业物联网已被广泛认为是工业革命的新引擎。合肥数字孪生正在推动工业制造从制造转向智造。通过数字化建模和仿真的方式,优化设计、生产、质量管理、供…...
Linux发展史与环境安装
Linux发展史与环境安装 一、Linux发展史推动技术进步的基本模式理解操作系统的发展理解Linux操作系统的发展 一、Linux的环境安装 一、Linux发展史 Linux和window XX其实都是一样的,定位:操作系统,企业内部,要给用户提供“互联网…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用
在工业制造领域,无损检测(NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统,以非接触式光学麦克风技术为核心,打破传统检测瓶颈,为半导体、航空航天、汽车制造等行业提供了高灵敏…...
