2020-2021:teams:i_dont_know_png:week_summary_2
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_2 [2020/05/10 21:51] potassium 创建 |
2020-2021:teams:i_dont_know_png:week_summary_2 [2020/05/17 12:03] (当前版本) qxforever [学习总结] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 2020.05.11-2020.05.17 周报 ====== | + | ====== 2020.05.10-2020.05.16 周报 ====== |
| 行 5: | 行 5: | ||
| + | ^ 比赛时间 ^ 比赛名称 ^ 赛中过题 ^ 总计过题 ^ 总题目数 ^ 排名 ^ | ||
| + | | 2020.05.16 | [[neerc2015 | NEERC 2015]] | 8 | 10 | 12 | 15 / 223 | | ||
| ===== 团队会议 ===== | ===== 团队会议 ===== | ||
| + | 本周无团队会议。 | ||
| ===== 个人训练 - nikkukun ===== | ===== 个人训练 - nikkukun ===== | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | |||
| + | === 2020.05.12 Codeforces Round #641 (Div. 1) === | ||
| + | |||
| + | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F1 ^ F2 ^ | ||
| + | | 通过 | √ | √ | √ | | | | | | ||
| + | | 补题 | | | | | | | | | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | |||
| + | 主要在做图论专题的相关练习，把板子和不熟悉的知识点都过了一遍。 | ||
| + | |||
| + | - [[2020-2021:teams:i_dont_know_png:nikkukun:mobius_inversion|莫比乌斯反演]] | ||
| + | - [[2020-2021:teams:i_dont_know_png:nikkukun:cycle_space|环空间]] | ||
| + | - [[2020-2021:teams:i_dont_know_png:nikkukun:connected_component|连通分量]] | ||
| + | - [[2020-2021:teams:i_dont_know_png:nikkukun:system_of_difference_constraints|差分约束系统]] | ||
| + | |||
| ==== 本周推荐 ==== | ==== 本周推荐 ==== | ||
| + | === ICPC 2019 Taipei L - Largest Quadrilateral === | ||
| - | === === | + | [[https://nanti.jisuanke.com/t/44536 | 题目链接]] |
| + | |||
| + | **题意**：给 $n \leq 4000$ 个点，求面积最大的凸四边形。 | ||
| + | |||
| + | **题解**：显然可以枚举对角线上的两个点，现在要找到距离对角线最远的两侧的点。先固定一个点 $A$，按相对 $A$ 的极角序枚举对角线的每一个点 $B_i$。 | ||
| + | |||
| + | 考虑所有点构成的一个凸包。显然，最远的点只能在凸包上取到。假设凸包上一点 $P$，随着 $i$ 的增大，$P$ 到 $AB_i$ 的距离是先增大后减小的（可以模拟一下）。同时，随着 $AB_i$ 的转动，最远的点应该是和旋转卡壳一样在凸包上单调移动的（这个过程和旋转卡壳很像）。因此维护好这个凸包，在上面单调指针移动即可维护最远点。 | ||
| - | [[|题目链接]] | ||
| - | **题意**： | ||
| - | **题解**： | ||
| 行 32: | 行 53: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | === 2020.05.12 Codeforces Round #641 (Div. 1) === | ||
| - | ==== 学习总结 ==== | + | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F1 ^ F2 ^ |
| + | | 通过 | √ | | | | | | | | ||
| + | | 补题 | | | | | | | | | ||
| + | 我是弱智 | ||
| + | === 2020.05.16 Codeforces Round #643 (Div. 2) === | ||
| + | |||
| + | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| + | | 通过 | √ | √ | √ | √ | √ | | | ||
| + | | 补题 | | | | | | √ | | ||
| + | |||
| + | <HTML> | ||
| + | <del> | ||
| + | </HTML> | ||
| + | 离AK Div.2最近的一次 | ||
| + | <HTML> | ||
| + | </del> | ||
| + | </HTML> | ||
| + | ==== 学习总结 ==== | ||
| + | |||
| + | DDL过多，下周补。 | ||
| ==== 本周推荐 ==== | ==== 本周推荐 ==== | ||
| - | === === | + | === CF1355F Guess Divisors Count === |
| - | [[|题目链接]] | + | [[https://codeforces.com/contest/1355/problem/F|题目链接]] |
| + | 比较有趣的交互题 | ||
| ===== 个人训练 - Potassium ===== | ===== 个人训练 - Potassium ===== | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | |||
| + | === 2020.05.12 Codeforces Round #641 (Div. 2) === | ||
| + | [[https://codeforces.com/contest/1350|链接]] | ||
| + | |||
| + | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | ||
| + | | 通过 | √ | √ | √ | √ | √ | | | ||
| + | | 补题 | | | | | | | | ||
| + | |||
| + | 其中 E 题的思路与 [[https://codeforces.com/problemset/problem/1244/F|CF1244F Chips]] 几乎一致，是这一道题的二维版。 | ||
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 主要进行了字符串、数论和图论的练习。 | ||
| + | |||
| + | 2020.5.10 [[.:potassium:math_theory_revision_1|扩欧 原根 BSGS N 次剩余]] | ||
| + | |||
| + | 2020.5.14 [[.:potassium:connected_component|连通分量]] | ||
| + | |||
| + | 2020.5.15 [[.:potassium:lgv_lemma|LGV 引理]] | ||
| + | |||
| + | 字符串将作为下周主要内容，故略。 | ||
| ==== 本周推荐 ==== | ==== 本周推荐 ==== | ||
| - | === === | + | === Atcoder Beginner Contest 077 D - Small Multiple === |
| + | |||
| + | [[https://atcoder.jp/contests/abc077/tasks/arc084_b|题目链接]] | ||
| + | |||
| + | **题意**：找到最小的、数位和最少的 $k$ 的正整数倍数。 $2\le k\le 10^5$。 | ||
| + | |||
| + | **题解**：不按正常思路进行进位， $10$ 由 $1$ 转移而来，$9$ 无法进行 $+1$ 的转移。于是这就转化成了一个 BFS 的问题：记录模 $k$ 余数为 $r$ 的数位和最小值。一个数 $p$ 能够转移到 $10p$ ，且当它个位为 $9$ 时可以转移到 $p+1$ 。 | ||
| + | |||
| + | 这个题给我们一个很重要的启示，就是逐位枚举的 BFS 。 | ||
| - | [[|题目链接]] | + | 通过这个启发，[[.:neerc2015#b_-_binary_vs_decimal|这里]]的 B 题也使用类似的思路求解，最终得到了正解。 |
| - | **题意**： | ||
| - | **题解**： | ||
2020-2021/teams/i_dont_know_png/week_summary_2.1589118675.txt.gz · 最后更改: 2020/05/10 21:51 由 potassium
