2020-2021:teams:die_java:weeksummary8
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:weeksummary8 [2020/07/31 15:14] mychael |
2020-2021:teams:die_java:weeksummary8 [2020/07/31 16:53] (当前版本) wxg [王兴罡] |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| \\ comment:考虑优化状态的时候要想到什么是真正有用的 | \\ comment:考虑优化状态的时候要想到什么是真正有用的 | ||
| - | wxg: | + | wxg: |
| - | \\ 题目大意： | + | Educational Codeforces Round 92 (Rated for Div. 2) ECalendar Ambiguity |
| - | \\ tag: | + | \\ 题目大意：一年有 $m$ 个月，每个月 $d$ 天，一周是 $k$ 天，问你有多少点对（a，b），$a$ 月 $b$ 日和 $b$ 月 $a$ 日在按星期算是同一天 |
| - | \\ 做法: | + | \\ tag: 数学 |
| - | \\ comment: | + | \\ 做法: (a,b),(b,a) 相差的天数是 $(b-a)(k-1)$ 天，我们只要保证 $(b-a)(k-1)%w = 0$ 即可，我们只需保证$b-a$ 是 $\frac{w}{gcd(w,d-1)}$ 的倍数，同时保证 $1 \le a \le b \le min(d,m)$ |
| - | hxm: | + | 设$\frac{w}{gcd(w,d-1)}$ 为 $k$ ,答案就是 $\sum^{ik \le min(d,m)-1}_{i=1}{min(d,m)-ik}$ |
| - | \\ 题目大意： | + | \\ comment: 把点对问题转化为 $b-a$ 的计算同时考虑各种边界问题 |
| - | \\ tag: | + | |
| - | \\ 做法: | + | hxm:M-SOLUTIONS Programming Contest 2020 F题 |
| - | \\ comment: | + | \\ 题目大意：二维平面有若干架飞机($n \leq 10^5$)，以相同速度分别沿四个方向中的一个方向飞行，问最早什么时候会有飞机相撞？ |
| + | \\ tag:转化，二分 | ||
| + | \\ 做法:相向而行的飞机相撞很容易判断，主要讨论交叉相撞的。以向上和向右的飞机为例，如果两个飞机在某个位置相撞那么其实可以把这个相撞的位置上移到一个特定的直线上，同时将向右飞行的飞机向左平移等同于其距离该直线的距离，这样转化了，两者还是会相撞，但相撞点移到了这条直线。通过这种方法，我们可以把向右移动的飞机都移动到一条直线上，把将问题降维了，对于每个向上的飞机只需在上面二分查找即可。其它方向交叉类似。 | ||
| + | \\ comment:问题降维 | ||
| ---- | ---- | ||
| 行 44: | 行 47: | ||
| ====== 王兴罡 ====== | ====== 王兴罡 ====== | ||
| - | + | 整理板子，cf的Educational Codeforces Round 92，及补了第五场的 H | |
| ---- | ---- | ||
| ====== 黄旭民 ====== | ====== 黄旭民 ====== | ||
| - | 补题：牛客第五场C | + | 补题：牛客第五场C、M-SOLUTIONS Programming Contest 2020 F题 |
| \\ 比赛：M-SOLUTIONS Programming Contest 2020 | \\ 比赛：M-SOLUTIONS Programming Contest 2020 | ||
| \\ 整理板子： | \\ 整理板子： | ||
2020-2021/teams/die_java/weeksummary8.1596179648.txt.gz · 最后更改: 2020/07/31 15:14 由 mychael
