CVBB ACM Team

牛客多校第三场

牛客多校第四场

7.23CF加训

团体比赛。

本周在学习压力不比学期差的同时，打了三场比赛。心情实在一般。

牛客第四场比赛的F题，是一道有趣的脑筋急转弯。

脑筋急转弯。

已知AB和CD平行，但是不知道是顺平行还是反平行。现在给出AC、AD、BC、BD四条线段的长度，试着判断AB和CD是顺平行还是反平行。

（可能大作业一般的G题会用到这个结论。G题站内链接：小型Matlab的实现方式）

官方的题解很巧妙，但是对于编程不友善。官方题解指出，四条线段最长的一定构成梯形的对角线。这意味着，至少要判断大小关系三次才能判断位置关系，所以我认为官方题解不好。

我希望只判断一次，就能判定位置关系，这样可以有效减短代码长度。这个答案是不唯一的，因为平行本身是一个很长的条件。

最初我给出的解法用到了定差幂线定理。

本题设计巧妙，结论深刻而优秀，是难得一见的好题。

牛客第三场比赛的E题，是算法的优秀例题。

图论、动态规划。

两个置换（长度为偶数n）由不交的对换填满，并且这两个置换也不相交。对于一个给定向量，一个置换在上面的权重是对换距离差之和。

求距离差之和的最小值。

首先看成图论问题。对换看成边，则被填满的置换就可以看成饱和对集。

两个饱和对集不相交，叠加在一起必然构成若干个圈。因此直接考虑回路上的和。

圈长为偶数，至少是4。求和最大值最终会变为不相邻取数的最小值问题，是典型的动态规划问题，直接求解即可。

本题设计巧妙，结论深刻而优秀，是难得一见的好题。

本页面的时间范围是2020.07.18-2020.07.24的周报

前一篇：week_summary_10

后一篇：week_summary_12