TitanZhang

题解

算法浅谈(1)

/ 注册

全部文章 / 题解（共4篇）

2020牛客暑期多校训练营（第七场）G Topo Counting 来自专栏

题目大意原题长的一批的翻译：有一种有向图，被称为排列的DRG图，其包含组节点，第组包含个节点：。 DRG上有2种边：组内边和组间边。第组内的组内边可以表示为：（应该都能看懂）组间边可以表示为：现在我们想知道排列的DRG图的拓扑序列的数量。有向图的拓扑序列可以表示为：。所有节点来自且对于任意...

拓扑排序动态规划组合数学

2020-08-02

1 845

2020牛客暑期多校训练营（第七场）A Social Distancing 来自专栏

题目大意在半径为的圆内放个人，使得相互之间距离尽可能远，即使得尽可能大，表示第i个人与第j个人的欧几里得距离。解题思路这道题我们考虑用dp来做。很容易得出，我们的n个点的距离和为：将其化为加法，可以推出这样的式子：每次直接求出前面一项，而后面用勾股定理求即可。 AC代码 #include&...

平面几何动态规划

2020-08-02

1 817

2020牛客暑期多校训练营（第七场）I Valuable Forests 来自专栏

题目大意我们将无根树T的价值定义为，其中V(T)是T的所有顶点的集合，而d(u)是T的度数。（即内部每个节点度数的平方和）我们将森林的价值定义为森林中所有树木的价值之和。求所有包含N个节点的森林的价值总和，答案对素数M取模。解题思路这题需要用到prufer序列的结论：初识prufe...

prufer序列动态规划组合数学

2020-08-02

5 1140

2020牛客暑期多校训练营（第五场）A-Portal 来自专栏

题目大意从点1出发，你要按顺序完成k个任务，每个任务有要求的起点终点。途中你可以在所在的位置建立一个传送门，而同时只能用两个传送门存在，如果超过两个，则必须（远程）关闭任意一个传送门。解题思路一首先可以想到，所谓的k个任务有起点终点，就是按顺序走过2k个点，a->b,c->d这样...

最短路动态规划

2020-07-26

5 823