首页 > 其他分享 >2024HDU 6th

2024HDU 6th

时间:2024-08-07 23:08:58浏览次数:14  
标签:度数 原图 6th 复杂度 混沌 菊花 2024HDU

T1
显然我们选择的点度数为2。
考虑若答案为Yes,则原图最多有5个度数为2的点。多于5个直接判为No
因此可以枚举所有度数为2的点,暴力判断以该点为根,两个儿子的子树是否为菊花图。这是简单的,因为树为菊花图当且仅当点数不超过2或者一度点的个数等于点数-1。
时间复杂度 \(O(n)\)。
T2
考虑图中是否存在一条边 \((u,v)\),使得存在与 \(u\) 相邻的点 \(x(x\neq v)\) 和与 \(v\) 相邻的点 \(y(y\neq u)\),\(x\) 可以等于 \(y\)。
若存在,则只有 \(u,v,x,y\) 可能是混沌点,因为它们构成长度为3的链或环,不可能是菊花的一部分。
接下来,只要暴力考虑这几个点是否为混沌点。用并查集维护连通块大小和一度点个数即可,出现环即不合法。
如果这几个点都不合法,则图中没有混沌点。
若不存在,则原图就是一个“菊花森林”,所有点都是混沌点。
时间复杂度 \(O(n\alpha(n))\)。

标签:度数,原图,6th,复杂度,混沌,菊花,2024HDU
From: https://www.cnblogs.com/studentDL/p/18348020

相关文章

  • The 16th Zhejiang Provincial (小白 重现之我是Joker)
    G-Lucky7inthePocket(签到题)思路:大于等于n,且被7整除,不能被4整除,算出这个数。Code:#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn;cin>>n;for(;n;){if(n%7==0&&n%4!=0){cout......
  • Dwango Programming Contest 6th D 题解
    正好测试一下专栏的题解系统。我省选寄了都怪洛谷/fn/fn/fn/fn/fn/fn/fn题解显然可以对于所有关系建有向边,显然是基环外向树森林。由于是字典序最小,因此找到最小的上一个点没有直接连向边的点一定最优。但是有时取最优会导致最后无法选完,我们考虑无法选完的情况。第一种是......
  • 初中英语优秀范文100篇-086The Person Who Has Influenced Me Most-对我影响最大的人
    PDF格式公众号回复关键字:SHCZFW086记忆树1Mymotheristhepersonwhohasinfluencedmemost.翻译我的母亲是对我影响最大的人简化记忆母亲句子结构主语Mymother作为主语,明确指出了影响说话者最大的人是“我的母亲系动词is系动词,用于连接主语和表语,表示主......
  • 2023 Dec. 16th
    上一周晚去补了语文英语,每天两节课,感觉没什么实质性的作用,而且每天都写不完作业,落了一堆。每天都因为写不完作业很烦......周六还迎来了周测,没想象中的那么难,也没那么简单,语文还没出分,只感觉作文写的跟屎一样;数学周三考的,115,还行;英语102.5/120,在班里挺靠前的,但还是感觉拉了;生物挺......
  • 86th 2023/11/18 NOIP Day1
    已经过去了,总结得写赛前没什么,直接入题T1一眼了,T2看了看,手模了一下,觉得非常麻烦,难以处理T3看一眼认为不太能做,后来还剩0.5h时开了它,发现可以拿分T4看出了暴力,发现有一当应该是DP的部分分然后去推T2,然后很自信地认为,按它特殊数据给的数量,可以拿80分然后20min切了T1后,开始码T2......
  • 76th 2023/10/10 Atcoder 10/8-ARC-T3
    这道题题目很有意思,看上去是很简单明显的计数,但一思考会发现要死很多重复状态因为标记的线很容易让人从一个方框开始思考起,所以很容易带入关于重复考虑的误区观察到线是斜着的,思考影响到的范围若涂上一个格子或左一个格子的右下,则该格子不能填涂左上观察到影响范围是一个个斜......
  • 56th 2023/7/4 模拟赛总结40
    额,这场比赛应该打得算认真,虽然最后因为一些奇怪的因素导致没有拿到所想的排名,但是总体可以首先先思考了很久,T2T3都挺接近正解的,但是因为一些知识点的欠缺二没有打下来如:T3的缩点,还有T2的一部分结论然后当时是把T2暴力拉满,还想哈希卡常过的,结果是低估了数据的强度,被卡的死死的,拿......
  • 26th
    保守数源代码#include<bits/stdc++.h>usingnamespacestd;intmain(){ for(inti=0;i<100000;i++){ intt=i; intcount=0;while(t!=0){t/=10;count++;//计算i是几位数}intk=pow(10,count);//截取后面的几位数10count次方if(i*i%k==i) cout<<i<<endl;}r......
  • undefined symbol: _ZTINSt6thread6_StateE解决方案
    场景   公司环境编译放在现场运行,提示错误如下:解析   编译的程序使用的是gccversion7.3.120180303(RedHat7.3.1-5)(GCC)    环境安装的是系统依......
  • 46th 2022/10/7 模拟赛总结33
    这次算是一个高光时刻吧rank2,不错的排名需要肯定但是,还是有所惰性,虽然今天可以理解,因为左眼有点肿?本次其实个人认为,rank2超级好拿,T1老老实实打了二分优化拿80,然后趁着......