2019-team3-0070

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2019-team3 返回]

[[Image(1.png, 700px)]]


== 概述 ==


== 总结 ==


=== HbFS- ===

很努力很努力的一场比赛，最后掉了一个题目有一点点可惜。

开了很多题目，自己上去写了一个打了一堆补丁最后过了的分治。

比赛3个小时的时候有一点点走神，中途因为自己上机忘记读G题的题意了。

给了lsy一个假算法让她玩了好久（Hhhhh），感觉这个B题才是本场比赛最难的一个题啊。

L题这个板子好像很值得研究一下呢。

=== LIN452 ===
开场就掉到B题里去了

对着复杂度不对的代码怀疑人生

这期间有尝试想过换解法什么的，就把大部分时间都花在这题上了。最后发现题都没读完。

其实G题应该在想B的间隙 去读掉的嗯。

不过至少训练时候的交流和配合好像都挺好的，大家一起努力努力再努力！


=== Pepcy_Ch  ===

今天 pepcy 最大的贡献可能是 debug。。。

以后应当记住的结论是：'''约数个数的规模是远小于 O(sqrt(n)) 的，在 10^9^ 级别是 1344，10^18^ 也只有 10^5^ '''。

以及，二分图带权匹配应当首先去想抄匹配的板子，至于 spfa 和 dij，我可能得自己实验实验。。。（这个 L 真的有点遗憾了，事实上，我当时是有过改成 spfa 的想法的，但由于以前有过 spfa 费用流 TLE 而 dij 费用流 AC 的经历而没有这么改。。。）

UPD：目前的发现是，如果是二分图，容量都为 1，只有从前一层到后一层的边，是 spfa 更快，甚至时间是 dij 的一半。甚至普通的三层图也是 spfa 会快点。但发现两层之间边很多的时候似乎就是 dij 更 nb 的时候，比如八月时的那个费用流就是在源和第一层之间存在 n^2^ 条边，也测试了完全二分图的情况，也是 dij 会更快，甚至只用不到 spfa 一半的时间。在 loj 上的模版题中，也就是一般图上，是 dij 快于 spfa。

=== 补题 ===

[/wiki/2019-team3 返回]

概述

总结

HbFS-

很努力很努力的一场比赛，最后掉了一个题目有一点点可惜。

开了很多题目，自己上去写了一个打了一堆补丁最后过了的分治。

比赛3个小时的时候有一点点走神，中途因为自己上机忘记读G题的题意了。

给了lsy一个假算法让她玩了好久（Hhhhh），感觉这个B题才是本场比赛最难的一个题啊。

L题这个板子好像很值得研究一下呢。

LIN452

开场就掉到B题里去了

对着复杂度不对的代码怀疑人生

这期间有尝试想过换解法什么的，就把大部分时间都花在这题上了。最后发现题都没读完。

其实G题应该在想B的间隙 去读掉的嗯。

不过至少训练时候的交流和配合好像都挺好的，大家一起努力努力再努力！

Pepcy_Ch

今天 pepcy 最大的贡献可能是 debug。。。

以后应当记住的结论是：约数个数的规模是远小于 O(sqrt(n)) 的，在 10⁹ 级别是 1344，10¹⁸ 也只有 10⁵ 。

以及，二分图带权匹配应当首先去想抄匹配的板子，至于 spfa 和 dij，我可能得自己实验实验。。。（这个 L 真的有点遗憾了，事实上，我当时是有过改成 spfa 的想法的，但由于以前有过 spfa 费用流 TLE 而 dij 费用流 AC 的经历而没有这么改。。。）

UPD：目前的发现是，如果是二分图，容量都为 1，只有从前一层到后一层的边，是 spfa 更快，甚至时间是 dij 的一半。甚至普通的三层图也是 spfa 会快点。但发现两层之间边很多的时候似乎就是 dij 更 nb 的时候，比如八月时的那个费用流就是在源和第一层之间存在 n² 条边，也测试了完全二分图的情况，也是 dij 会更快，甚至只用不到 spfa 一半的时间。在 loj 上的模版题中，也就是一般图上，是 dij 快于 spfa。

补题

附加文件

• 1.png by Pepcy_Ch