5.3测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
---------------------------------------------------------------------------
常州一中的题..嗯...
SuperOj貌似没加..这里说下题意好了
T1:给你一个长度为n的整数组成的环,让你把这个环切成k个部分,最大化每个部分的和的gcd,n<=2000,ai<=5*10^7,对于每个1<=k<=n都要回答一次
T2:给你一棵有点权的树,让你选两条不相交的链使他们长度和最大,树大小<=200000
T3:给你一个无向图,有边权,有重边,每次一个询问给定两个点,询问这两个点之间的最大边最小的环(边不能交叉,也就是说至少两条路径)的最大边大小,数据范围是10^5级别
---------------------------------------------------------------------------
T1:
不难发现答案一定是单调的,而且一定是所有数的和的约数
所以枚举所有数的和的约数d,然后只需看使每一段都是d的倍数,最多分成多少段
枚举起始位置i,然后不难发现段数就是[i,i+n-1]中和a[i-1]关于d同余的数个数,然后单调队列搞一搞就好了
---------------------------------------------------------------------------
T2:
首先定义一个链的深度为链中最浅点的深度
然后定义低链为两个链中深度较深的,如果一样深就随便哪一个,另一个叫做高链
然后YY一下就会发现,低链一定是他的最浅点所在子树的直径
先把这个求出来,然后讨论一下高链和低链的关系,然后发现每一种关系都可以树型DP做(一共有5种情况,写死我了...)
---------------------------------------------------------------------------
T3:
首先整体二分,二分答案,然后小于等于mid的询问都丢到左边,大于的都丢到右边
然后两边分别递归做就可以了(先左边,再处理这一层,再处理右边)
然后把小于等于mid的边连上,现在只需要问两点之间有没有环,用并查集就可以了
---------------------------------------------------------------------------
评论 (0)
