2020-2021:teams:namespace:week_summary_11

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:namespace:week_summary_11 [2020/07/23 15:32]
great_designer
+++ 2020-2021:teams:namespace:week_summary_11 [2020/07/24 12:46] (当前版本)
serein [比赛]
@@ 行 19: / 行 19: @@
 ===题目名称及来源===
-牛客第三场比赛的E题，是算法的优秀例题。
+牛客第四场比赛的F题，是一道有趣的脑筋急转弯。
 ===标签===
-图论、动态规划。
+脑筋急转弯。
 ===题意===
-两个置换（长度为偶数n）由不交的对换填满，并且这两个置换也不相交。对于一个给定向量，一个置换在上面的权重是对换距离差之和。
+已知AB和CD平行，但是不知道是顺平行还是反平行。现在给出AC、AD、BC、BD四条线段的长度，试着判断AB和CD是顺平行还是反平行。
-求距离差之和的最小值。
+（可能像大作业一样的G题会用到这个结论。G题站内链接：[[小型Matlab的实现方式]]）
 ===题解===
-首先看成图论问题。对换看成边，则被填满的置换就可以看成饱和对集。
+官方的题解很巧妙，但是对于编程不友善。官方题解指出，四条线段最长的一定构成梯形的对角线。这意味着，至少要判断大小关系三次才能判断位置关系，所以我认为官方题解不好。
-两个饱和对集不相交，叠加在一起必然构成若干个圈。因此直接考虑回路上的和。
+我希望只判断一次，就能判定位置关系，这样可以有效减短代码长度和逻辑关系。这个答案是不唯一的，因为平行本身是一个很长的条件。
-圈长为偶数，至少是4。求和最大值最终会变为不相邻取数的最小值问题，是典型的动态规划问题，直接求解即可。
+最初我给出的解法用到了**定差幂线定理**。计算-AC^2+AD^2+BC^2-BD^2，如果为正则是顺平行，为负则是反平行。0意味着AB和CD平行，这是不可能的。
+但是赛后看到其他人的题解发现，去掉平方也是对的，即-AC+AD+BC-BD，结论不变。原因是三角形两边之和大于第三边，画图就知道了。
 ===评论===
-本题设计巧妙，结论深刻而优秀，是难得一见的好题。
+本题虽然代码非常简短，甚至适合C语言入门，但是对脑回路的考察可谓是相当深入的。可以说是年度好题了。
 ===== 胡湘鹏 =====
 ==== 比赛 ====
+比赛如上。
 ==== 学习总结 ====
@@ 行 85: / 行 87: @@
 ===题目名称及来源===
-===tag===
+牛客第三场比赛的A题。
+===标签===
+贪心。
 ===题意===
+每轮池塘里可能有一条鱼也可能没有，可能有一只蛤也可能没有。每轮可以选择捕鱼或捕蛤，也可以将已经捕到的一只蛤变成鱼，也可以什么都不做。对于每种状态序列，求最终捕鱼数的最大值。
 ===题解===
-===comment===
+贪心的想法，首先有鱼就捕鱼。
+没有鱼就先捕蛤，什么都没有但是还有捕到的蛤，就让蛤变鱼。
+假设到最后还剩下若干只蛤，这意味着倒数几轮中可以将捕蛤的操作改成蛤变鱼，使得捕到的总鱼数增加，得到最终不剩下蛤的流程是最优的，即最后再加上剩下若干只蛤的数目的一半，就是原问题的最优解。
+===评论===
+有趣的钓鱼问题，是贪心算法的优秀实例。
 ===== 页面链接 =====

2020-2021/teams/namespace/week_summary_11.1595489528.txt.gz · 最后更改: 2020/07/23 15:32 由 great_designer