2020-2021:teams:mian:weekly_report:2020_summer_week_3_report
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:weekly_report:2020_summer_week_3_report [2020/07/31 15:06] grapelemonade [Pantw] |
2020-2021:teams:mian:weekly_report:2020_summer_week_3_report [2020/07/31 19:24] (当前版本) grapelemonade [团队训练] |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| [[2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_6|2020牛客暑期多校训练营（第六场）]] ''%%task:5/6/11%%'', ''%%rank:95 / 1120%%'' | [[2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_6|2020牛客暑期多校训练营（第六场）]] ''%%task:5/6/11%%'', ''%%rank:95 / 1120%%'' | ||
| - | [[2020-2021:teams:mian:cf_mashup:20200730|2020/07/30 CF Mashup Training]] ''%%task:16/16/26%%'' | + | [[2020-2021:teams:mian:cf_mashup:20200730|2020/07/30 CF Mashup Training]] ''%%task:16/16/26%%'' |
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| 行 17: | 行 17: | ||
| * 分类：平衡树 / 线段树 | * 分类：平衡树 / 线段树 | ||
| * 题意：给一个 $n\times n$ 尺寸的上三角方格。有 $q$ 个操作。每次操作选择一个副对角线上的格子，指定一个方向，从副对角线上的格子开始对这个方向上的格子全部染色，直至碰见边界，或者遇见在之前的查询中染过色的格子为止。对每个操作需要输出在该次操作中被染色的格子数。$1\le n\le 10^9, 1\le q\le 2\times 10^5$ | * 题意：给一个 $n\times n$ 尺寸的上三角方格。有 $q$ 个操作。每次操作选择一个副对角线上的格子，指定一个方向，从副对角线上的格子开始对这个方向上的格子全部染色，直至碰见边界，或者遇见在之前的查询中染过色的格子为止。对每个操作需要输出在该次操作中被染色的格子数。$1\le n\le 10^9, 1\le q\le 2\times 10^5$ | ||
| - | * 解法： | + | * 解法：平衡树维护斜线区间对应的图形形状 / 离散化后用线段树维护每行和每列的限制 |
| - | * 评论： | + | * 评论：平衡树的做法比较自然好想 |
| ===== Withinlover ===== | ===== Withinlover ===== | ||
| + | |||
| + | [[https://codeforces.com/problemset/problem/543/D|CF543 Div1 D]] | ||
| + | |||
| + | * 分类：换根dp | ||
| + | * 题意：树上黑白染色，要求所有点到根的路径上至多只有一个黑边。对于每个点，求出以它为根节点时的方案数 | ||
| + | * 解法：如果只有一个根，可以考虑 $O(n)$ 的dp：$dp[x] = \prod(dp[son[x]]+1)$，将树根移动时仅会影响两个点的dp数组，可以 $O(1)$的计算出新根的答案。所以dp完了再遍历一次就得到答案了。 | ||
| + | * 评论：有一个坑点是 $dp[son[x]] + 1$ 在模意义下可能为 $0$，然后你换根的时候如果用逆元去做除法就GG了。正确的处理方法应该是预处理出前缀和后缀的乘积加速计算。 | ||
| ===== Gary ===== | ===== Gary ===== | ||
| 行 41: | 行 48: | ||
| [[https://community.topcoder.com/stat?c=round_overview&rd=18085|SRM 788]] | [[https://community.topcoder.com/stat?c=round_overview&rd=18085|SRM 788]] | ||
| + | |||
| + | [[https://codeforces.com/contest/1389|Educational Codeforces Round 92 (Rated for Div. 2)]] | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| 行 46: | 行 55: | ||
| CF551D, CF552C, CF552D, CF552E, CF555C, CF555D | CF551D, CF552C, CF552D, CF552E, CF555C, CF555D | ||
| + | |||
| + | CF1389A, CF1389B, CF1389C, CF1389D, CF1389E | ||
| ===== Withinlover ===== | ===== Withinlover ===== | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| [[https://atcoder.jp/contests/m-solutions2020|M-SOLUTIONS Programming Contest 2020]] | [[https://atcoder.jp/contests/m-solutions2020|M-SOLUTIONS Programming Contest 2020]] | ||
| 行 59: | 行 71: | ||
| Codeforces 660 div2 A,B,C,D | Codeforces 660 div2 A,B,C,D | ||
| + | |||
| + | CF543D CF550D CF550E CF551C CF555B | ||
| ===== Gary ===== | ===== Gary ===== | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| - | 广义后缀自动机(还没完看) | + | 广义后缀自动机(还没看完) |
| ==== 比赛 ==== | ==== 比赛 ==== | ||
2020-2021/teams/mian/weekly_report/2020_summer_week_3_report.1596179176.txt.gz · 最后更改: 2020/07/31 15:06 由 grapelemonade
