首页 > 最长树链
头像 shyyhs
发表于 2021-01-11 14:42:04
前言: 之前那个博客有大问题...确实是数据太水了. 思路: 首先我们处理出4e4以内的质数,然后因为任何合数都可以写成的形式,显然大于4e4的数,假如经过这么一次筛选,一定是不会出现超过4e4的合数.对于每个数,我们处理出来它们的质因子,这里呢,用的是最原始的判断方法,假如有n个数是大质数,那么就 展开全文
头像 MYCui_
发表于 2021-01-13 17:33:23
前置知识: 素数判断( 素数探测可用可不用吧) + + 分组思维 具体做法 观察题目,发现题目要求我们求 不等于 的一条最长链。 那么如果这条链上所有的节点的 都不为 ,那么它们肯定有着至少一个相同的质因子。 所以我们考虑将拥有相同质因子的节点放在一起处理,然后对于具有相同质因子的节点中求 展开全文
头像 sunrise__sunrise
发表于 2021-01-13 21:11:45
题目描述 给你个节点的一棵树,还有每个点的点权值,现在要你选出一条最长的边,保证这条边中全部的点之后的值不等于,也就是存在一个公共的因子全部点都有。 Solution 思路参考喵渺淼妙的死忠粉大佬这是原题解传送门观察到这个问题,那么我们第一步想想能不能去枚举,根据唯一分解定理,每一个数都可以拆成一堆 展开全文
头像 WuliWuliiii
发表于 2021-01-16 22:33:18
很容易想到正确的解法,首先,我们可以知道(2 * 3 * 5 * 7 * 11 * 13 * ……)最多19个质数相乘就会达到1e9级别的。于是,我们可以考虑质数,我们可以知道一个数最多就是分成20个质数,所以我们直接进行对质数的检验会好一些。但是有些大质数应该怎么办呢?于是就有了米勒罗宾检验素数。 展开全文
头像 熠丶
发表于 2021-01-12 13:41:44
因为我太菜了,于是乎就找了份代码,理解了一下思路(把坑填完才能好好复习zz 思路: 1.先用筛求质数表,表长大约是sqrt(1e9) 2.建树 3.对权值进行质因数分解,并把对应的权值下标与素数对应起来存下来 4.然后树形dp求符合条件的最长链 代码 #include<bits/stdc+ 展开全文
头像 ⊙__⊙
发表于 2021-01-14 10:21:21
题意: 给出一颗树,请你找出最长的一条链,这条链上所有数值的GCD要大于1.并输出最长链的长度。 这题参考了 小熠小熠很不容易 大佬的思路。 思路就是,先建一棵树,然后从根开始搜索,这里要注意根不一定是1,要自己找根。 然后再搜索的时候,每次计算下GCD,如果GCD大于1,那么是满足条件的 展开全文

等你来战

查看全部