3899: 仙人掌树的同构题解

leaf posted @ 2015年4月29日 20:40 in 未分类 , 1017 阅读

第一次写与仙人掌有关的题目,虽然不是动态XXX

这个题目很有趣,问你有多少个同构的仙人掌

首先,仙人掌的问题肯定是要转换成树的问题的,那么可以先找出所以的环,对于每个环新建一个点,向所以这个环上的点连边,把环的边去掉,为了方便,在其他树边上新建一个中点,好,这样就转换成了树,并且等价。

 

现在考虑要找一个点它是不动的,显然是直径的中心,它不可能和其他的点换,而且新构的树中心是唯一的。把它拎起来,变成有根树。

剩下的考虑一个点,如果它不是环上的,那么如果有K个子树完全相同,那么有K!种方案。怎么判树相同?可以sort一下暴力hash,从小到大标号。

如果是环的中心,那么它不能随便交换,要考虑环上轮换(非中心不用考虑),或者对称,这个是字符串的基础问题了。

 

然后要考虑如果中心是环的中心,要考虑轮换

 

注意:

扫描环的时候要考虑顺序

偶环的对称有两种情况,都可以转换成回文串问题

 

Avatar_small
home cleaning dubai 说:
2022年1月25日 21:21

Whilst our housekeepers don’t supply the following providers, we can highly recommend one of the locally-owned companies from the network associated with trusted home providers. Visit getneighborly.com to learn more.With a track record of clean homes and happy customers, DIALAMAID is your best choice for housekeeping services designed to fit your budget and schedule. We work closely with homeowners, rental property owners, and vacation homeowners to build a custom cleaning plan that fits their unique cleaning needs..

Avatar_small
AP SSC Chemistry Mod 说:
2022年9月14日 03:36

Chemistry makes the students know about the content in-depth manner. Based on the new or revised syllabus subject experts have designed and suggested AP 10th Class Chemistry Model Paper 2023 with Answers to every Telugu Medium, English Medium and Urdu Medium student of the State which helps the scholars to get good scores in all exams like SA-1, SA-2, FA-1, FA-2, FA-3, AP SSC Chemistry Model Paper FA-4 along with Assignments. The BSEAP 10th Class Chemistry model papers 2023 have been prepared by Leading educational institute subject experts of chemistry and teaching staff are designed for theory, objective type multiple choice questions and bit questions for both Government & Private School students.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter