11.21 小清新图论专场训练

news/2024/11/22 18:11:10/

小清新

A

怎么感觉不是很简单呢

分析一下发现操作的自由度是很高的,不妨认为 一个连通块内不需要考虑边的方向,只需考虑当前是否还有空位

空位的判定条件就是是否已经加出一个环了

int n , L ;
int a[N] , b[N] ;
int bin[N] ;
bool vis[N] ;
int Find( int x )
{if( x == bin[x] ) return x ;return bin[x] = Find(bin[x]) ;
}
//最终状态? 
// 一个联通块最多只有一个环 int main()
{scanf("%d%d" , &n , &L ) ;for(int i = 1 ; i <= L ; i ++ ) bin[i] = i ;for(int i = 1 ; i <= n ; i ++ ) {scanf("%d%d" , &a[i] , &b[i] ) ;int fx = Find(a[i]) , fy = Find(b[i]) ;if( fx^fy ) {bin[fx] = fy ;if( vis[fx]&&vis[fy] ) printf("SMECE\n") ;else printf("LADICA\n") ;vis[fy] |= vis[fx] ;}else {if( !vis[fx] ) vis[fx] = 1 , printf("LADICA\n") ;else printf("SMECE\n") ;}}return 0 ;
}

D

构造题,先猜出答案的下界/上界

容易想到先不考虑乘积相等的情况,相邻位置看成二元组 ( a , b ) (a,b) (a,b)(不考虑顺序)

直接猜 X X X 种元素构出的最大长度就是 不同的二元组个数,不是最大长度的话显然删掉序列末尾一定不会变得不合法

这个数量是平方级别的,也就是元素种类数大概就是根号

再想发现把数都取成质数就能完全等价于二元组了

接下来想怎么构造出来这个上界

相邻位置的传递可以看成连边, ( a , b ) (a,b) (a,b) 的二元组就看成 a → b a\to b ab 的一条边,二元组需要全部出现,就是边要全部经过,由此想到欧拉路径

重新表述一下:答案上界的构造等价于 X X X 个点的完全图的一条欧拉路径

分讨, X X X 为奇数显然直接满足; X X X 为偶数的话每个点度数都是奇数,上界就取不到了

考虑增量构造,从 X − 1 X-1 X1 推过来,发现最优的肯定是两两匹配后再删一条边

直接按这个上界构造即可

注意不能把所有的 X X X 都预处理,这样是 n n n\sqrt n nn 的,每次询问的时候现做即可,复杂度 O ( n ) O(n) O(n)

G

难评的一道题

显然有暴力思路是每次枚举一条边反转后重新跑

画画图发现只有反转最短路上的边才需要重新跑,其他可以分讨出来

F

以下是不会的题

C

感觉是比较套路的题 虽然我不会

最小生成树,以前见的都是魔改一下经典算法的过程然后什么数据结构维护一下

还有一种套路:边数很多的时候(比如完全图),通常可以分析出来许多边是没用的,只保留那些较优的边,再跑最小生成树算法

假设三条线段 x , y , z x,y,z x,y,z 两两相交,若 a x < a y < a z a_x<a_y<a_z ax<ay<az,那么只需保留 a x → a y , a y → a z a_x\to a_y,a_y\to a_z axay,ayaz,显然第三条边是没用的

稍稍推广一下:考虑数轴上的一个位置,如果被多条线段同时覆盖,只需要按 a a a 排序后相邻两条线段连边即可

好对啊!set 简单维护之

B

好牛的题

貌似括号序列的限制是挺多的,找找性质

  • x x x y y y 连通
  • x x x 必须是 ( ( ( y y y 必须是 ) ) )
  • x x x y y y 需要存在一条长度为偶数的路径
  • 会反复横跳的一定是在两个相同字符的点之间
    … …

感觉这些都还差点意思

从边的角度分析:边要么是连接不同字符,这样的边反复横跳是没意义的;否则就是相同字符,反复横跳一次就会在串里面插入两个 ( ( ( 或者 ) ) )

再考虑路径:简单的情况是不经过第二类边,那么路径上一定是 ( ) ( ) ( ) ( ) ( ) . . . ()()()()()... ()()()()()...,这是好维护的

否则是从 x x x 出发走一段 ( ) ( ) . . . ()()... ()()...接下来必定是走过 ( ( (( (( 的边若干次 后继续走

后半部分倒过来看,从 y y y 出发走一段 ( ) ( ) . . . ()()... ()()...,接下来走过 ) ) )) )) 边若干次后继续走

考虑只保留一类边进行并查集,得到若干连通块

记从 x x x 出发走到的第一个在同一连通块中,且连有一条 ( ( (( (( 的点为 p p p,对称的记 y y y 对应的点为 q q q,我们继续分析 p p p 走到 q q q 的过程

因为 p p p q q q 均有 ( ( (( (( ) ) )) )) 的边,可以通过反复横跳来修正中间括号匹配的限制,那么唯一的限制就是 存在偶数长度的路径!!

判断这个有比较 trick 的做法:

在这里插入图片描述

第一种方式比较好做,直接维护就行了


http://www.ppmy.cn/news/1549096.html

相关文章

三、计算机视觉_06YOLO基础知识

1、YOLO概述 1.1 定义 YOLO&#xff08;You Only Look Once&#xff09;是一种流行的对象检测和图像分割模型&#xff0c;由华盛顿大学的 Joseph Redmon 和 Ali Farhadi 于 2015 年推出&#xff0c;因其高速和准确性而迅速受到欢迎 在目标检测领域&#xff0c;传统方法&…

如何利用Java爬虫获得1688店铺详情

在数字化时代&#xff0c;数据已成为企业决策的重要依据。对于电商平台而言&#xff0c;获取竞争对手的店铺详情对于市场分析、产品定位等具有重要意义。本文将详细介绍如何利用Java编写爬虫&#xff0c;获取1688店铺详情&#xff0c;并提供实际的代码示例。 1. 背景介绍 1688…

五天SpringCloud计划——DAY1之mybatis-plus的使用

一、引言 咱也不知道为啥SpringCloud课程会先教mybatis-plus的使用&#xff0c;但是教都教了&#xff0c;就学了吧&#xff0c;学完之后觉得mybatis-plus中的一些方法还是很好用了&#xff0c;本文作为我学习mybatis-plus的总结提升&#xff0c;希望大家看完之后也可以熟悉myba…

IntelliJ+SpringBoot项目实战(十)--常量类、自定义错误页、全局异常处理

一、常量类 在项目开发中&#xff0c;经常需要约定一些常量&#xff0c;比如接口返回响应请求指定状态码、异常类型、默认页数等&#xff0c;为了增加代码的可阅读性以及开发团队中规范一些常量的使用&#xff0c;可开发一些常量类。下面有3个常量类示例&#xff0c;代码位于op…

【划分型DP-约束划分个数】力扣813. 最大平均值和的分组

给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个非空子数组&#xff0c;且数组内部是连续的 。 分数 由每个子数组内的平均值的总和构成。 注意我们必须使用 nums 数组中的每一个数进行分组&#xff0c;并且分数不一定需要是整数。 返回我们所能得到的最…

【Springboot3 ➕Vue3】 实现学生选课管理系统

学生选课系统 介绍软件框架参考官方文档有话要说 介绍 简单的搭建一个学生选课平台--------作为开发练手的第一个项目 一共有三个系统角色&#xff1a;&#x1f447; 管理员&#xff1a;管理员可以看到以上所有模块&#xff0c;管理所有模块信息。教师&#xff1a;教师可以…

Flutter:AnimatedIcon图标动画,自定义Icon通过延时Interval,实现交错式动画

配置vsync&#xff0c;需要实现一下with SingleTickerProviderStateMixinclass _MyHomePageState extends State<MyHomePage> with SingleTickerProviderStateMixin{// late延迟初始化 AnimationControllerlate AnimationController _controller;overridevoid initStat…

基于 BP 神经网络整定的 PID 控制

基于 BP 神经网络整定的 PID 控制 是一种结合了经典 PID 控制和 BP&#xff08;反向传播&#xff09;神经网络的自适应控制方法。在这种方法中&#xff0c;神经网络用于在线调整 PID 控制器的参数&#xff08;比例增益 KpK_pKp​&#xff0c;积分增益 KiK_iKi​ 和微分增益 KdK…