2020-2021:teams:namespace:week_summary_12
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:week_summary_12 [2020/07/30 11:53] great_designer 创建 |
2020-2021:teams:namespace:week_summary_12 [2020/07/30 17:52] (当前版本) great_designer [本周推荐] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ===== 团队训练 ===== | ===== 团队训练 ===== | ||
| - | [[牛客多校第三场]] | + | [[牛客多校第五场]] |
| - | [[牛客多校第四场]] | + | [[牛客多校第六场]] |
| - | [[7.23CF加训]] | ||
| ===== 李淳一 ===== | ===== 李淳一 ===== | ||
| 行 14: | 行 13: | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| - | 本周在学习压力不比学期差的同时，打了三场比赛。心情实在一般。 | + | 完了完了完了科目三考试要拖到小学期里了我现在心情是崩溃的 |
| ==== 本周推荐 ==== | ==== 本周推荐 ==== | ||
| ===题目名称及来源=== | ===题目名称及来源=== | ||
| - | 牛客第四场比赛的F题，是一道有趣的脑筋急转弯。 | + | 牛客第五场比赛的C题。 |
| ===标签=== | ===标签=== | ||
| - | 脑筋急转弯。 | + | 生成函数。 |
| ===题意=== | ===题意=== | ||
| - | 已知AB和CD平行，但是不知道是顺平行还是反平行。现在给出AC、AD、BC、BD四条线段的长度，试着判断AB和CD是顺平行还是反平行。 | + | W先生正在写序列。如果他写两个长度为K的正整数序列A和B满足： |
| - | （可能像大作业一样的G题会用到这个结论。G题站内链接：[[小型Matlab的实现方式]]） | + | $$\sum_{i=1}^K a_i=N$$ |
| + | |||
| + | $$\sum_{i=1}^K b_i=M$$ | ||
| + | |||
| + | 他会得到: | ||
| + | |||
| + | $$P=\prod_{i=1}^K \min(a_i,b_i)$$ | ||
| + | |||
| + | 积分。 | ||
| + | |||
| + | 你想知道他能写的所有可能的序列的总分之和。 | ||
| ===题解=== | ===题解=== | ||
| - | 官方的题解很巧妙，但是对于编程不友善。官方题解指出，四条线段最长的一定构成梯形的对角线。这意味着，至少要判断大小关系三次才能判断位置关系，所以我认为官方题解不好。 | + | 详细内容见第五场题解页面。通过计算，知道所求为多项式： |
| + | |||
| + | $$\frac{1}{{(1-x)}^K}\frac{1}{{(1-y)}^K}\frac{1}{{(1-xy)}^K}$$ | ||
| - | 我希望只判断一次，就能判定位置关系，这样可以有效减短代码长度和逻辑关系。这个答案是不唯一的，因为平行本身是一个很长的条件。 | + | 之中$x^{N-K}y^{M-K}$前的系数。通过计算可知，该系数为： |
| - | 最初我给出的解法用到了**定差幂线定理**。计算-AC^2+AD^2+BC^2-BD^2，如果为正则是顺平行，为负则是反平行。0意味着AB和CD平行，这是不可能的。 | + | $$\sum_{t=0}^{\min(N,M)-K} C_{K-1+t}^{K-1}C_{N-1-t}^{K-1}C_{M-1-t}^{K-1}$$ |
| - | 但是赛后看到其他人的题解发现，去掉平方也是对的，即-AC+AD+BC-BD，结论不变。原因是三角形两边之和大于第三边，画图就知道了。 | + | 为所求答案。 |
| ===评论=== | ===评论=== | ||
| - | 本题虽然代码非常简短，甚至适合C语言入门，但是对脑回路的考察可谓是相当深入的。可以说是年度好题了。 | + | 比赛的时候没有看这道题。看题解生成函数的开头，便照葫芦画瓢的做了一遍。 |
| + | |||
| + | 还有，处理阶乘的逆的手段——**倒着处理**很巧妙，值得好好参考。 | ||
| ===== 胡湘鹏 ===== | ===== 胡湘鹏 ===== | ||
| 行 54: | 行 67: | ||
| ===题目名称及来源=== | ===题目名称及来源=== | ||
| - | 牛客第三场比赛的E题，是算法的优秀例题。 | + | 牛客多校第六场的E题。 |
| ===标签=== | ===标签=== | ||
| - | 图论、动态规划。 | + | 数论、构造。 |
| ===题意=== | ===题意=== | ||
| - | 两个置换（长度为偶数n）由不交的对换填满，并且这两个置换也不相交。对于一个给定向量，一个置换在上面的权重是对换距离差之和。 | + | 构造1到n的排列，模n意义下存在连续i个数和为k，对于任意的i从1跑到n。 |
| - | + | ||
| - | 求距离差之和的最小值。 | + | |
| ===题解=== | ===题解=== | ||
| - | 首先看成图论问题。对换看成边，则被填满的置换就可以看成饱和对集。 | + | 首先，只有k为((n%2)?0:n/2)的时候有解。这是因为连续n个数必然是1到n全体，求和模n是固定的。 |
| - | 两个饱和对集不相交，叠加在一起必然构成若干个圈。因此直接考虑回路上的和。 | + | 当n为奇数，构造为n 1 n-1 2 n-2 ……。 |
| - | 圈长为偶数，至少是4。求和最大值最终会变为不相邻取数的最小值问题，是典型的动态规划问题，直接求解即可。 | + | 当n为偶数，构造为n n/2 1 n-1 2 n-2 ……。 |
| ===评论=== | ===评论=== | ||
| - | 本题设计巧妙，结论深刻而优秀，是难得一见的好题。 | + | 优秀的构造题目，想到第一步考虑n个数全体是解题的关键。 |
| ===== 马逸行 ===== | ===== 马逸行 ===== | ||
| 行 87: | 行 98: | ||
| ===题目名称及来源=== | ===题目名称及来源=== | ||
| - | 牛客第三场比赛的A题。 | + | 牛客多校第五场的E题。 |
| ===标签=== | ===标签=== | ||
| - | 贪心。 | + | 置换、圈、最小公倍数、高精度。 |
| ===题意=== | ===题意=== | ||
| - | 每轮池塘里可能有一条鱼也可能没有，可能有一只蛤也可能没有。每轮可以选择捕鱼或捕蛤，也可以将已经捕到的一只蛤变成鱼，也可以什么都不做。对于每种状态序列，求最终捕鱼数的最大值。 | + | 对于给定置换，求它在置换群中的阶。（高精度取模） |
| ===题解=== | ===题解=== | ||
| - | 贪心的想法，首先有鱼就捕鱼。 | + | 分解成k个不相交的轮换，求轮换长的最小公倍数。 |
| - | + | ||
| - | 没有鱼就先捕蛤，什么都没有但是还有捕到的蛤，就让蛤变鱼。 | + | |
| - | + | ||
| - | 假设到最后还剩下若干只蛤，这意味着倒数几轮中可以将捕蛤的操作改成蛤变鱼，使得捕到的总鱼数增加，得到最终不剩下蛤的流程是最优的，即最后再加上剩下若干只蛤的数目的一半，就是原问题的最优解。 | + | |
| ===评论=== | ===评论=== | ||
| - | 有趣的钓鱼问题，是贪心算法的优秀实例。 | + | 为了避过高精度，练习了Java的BigInteger类。 |
| ===== 页面链接 ===== | ===== 页面链接 ===== | ||
| - | 本页面的时间范围是2020.07.18-2020.07.24的周报 | + | 本页面的时间范围是2020.07.25-2020.07.31的周报 |
| - | 前一篇：[[week_summary_10]] | + | 前一篇：[[week_summary_11]] |
| - | 后一篇：[[week_summary_12]] | + | 后一篇：[[week_summary_13]] |
2020-2021/teams/namespace/week_summary_12.1596081220.txt.gz · 最后更改: 2020/07/30 11:53 由 great_designer
