2020-2021:teams:farmer_john:week_13
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:week_13 [2020/07/31 15:34] jjleo [JJLeo] |
2020-2021:teams:farmer_john:week_13 [2020/07/31 17:27] (当前版本) 2sozx [题目] |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| ====2sozx==== | ====2sozx==== | ||
| - | ===题目名称 CF 1388 E=== | + | ===CF 1388 E=== |
| * 分类：计算几何 | * 分类：计算几何 | ||
| 行 34: | 行 34: | ||
| * 题意：给定一个$n \times n$的方格图，每次只能向右向下走，要从左上角走到右下角。每个方格有一个权值$a_{i,j}$，路径上每经过一个点就会获得${(n^2)}^{a_{i,j}}$的权值。现在有$q$次询问，询问若一个矩形区域不可通过，所有合法路径中的最大权值对$10^9+7$取模。$(n \le 400, q \le 2 \times 10^5)$ | * 题意：给定一个$n \times n$的方格图，每次只能向右向下走，要从左上角走到右下角。每个方格有一个权值$a_{i,j}$，路径上每经过一个点就会获得${(n^2)}^{a_{i,j}}$的权值。现在有$q$次询问，询问若一个矩形区域不可通过，所有合法路径中的最大权值对$10^9+7$取模。$(n \le 400, q \le 2 \times 10^5)$ | ||
| - | * 题解：如图所示，设灰色区域为被禁止通过的区域，那么所有合法路径一定至少经过了一个红色格子或绿色格子，同时至少经过了一个红色格子或绿色格子的路径也是合法的。因此可以求出每个点分别到起点和终点的最大权值，求一下每一行的前缀后缀最大值即可。{{:2020-2021:teams:farmer_john:jjleo:hdu2020b.png?600|}} | + | * 题解：如图所示，设灰色区域为被禁止通过的区域，那么所有合法路径一定至少经过了一个红色格子或绿色格子，同时至少经过了一个红色格子或绿色格子的路径也是合法的。因此可以求出每个点分别到起点和终点的最大权值，求一下每一行的前缀后缀最大值即可。{{:2020-2021:teams:farmer_john:jjleo:hdu2020d.png?600|}} |
| * 然而cls并没有让这题就这样结束，可以发现权值太大没有办法直接维护。观察权值的底数可以发现我们可以将权值和写成$n^2$进制，这样权值相加可以保证不会发生进位，从而将比较大小改为比较两个字符串的字典序。每次转移中相当于在某一位加了个$1$，因此我们可以用主席树维护每个权值，比较大小时维护区间哈希值，在线段树上二分最长公共前缀，最终比较第一位不同的而得出大小关系。另外因为我们要维护每个点分别到起点和终点的最大值，最终求每一行的最大值前后缀需要进行加法，因为两者相加的哈希值等于两者的哈希值相加，所以直接将两棵树放一起进行比较即可。 | * 然而cls并没有让这题就这样结束，可以发现权值太大没有办法直接维护。观察权值的底数可以发现我们可以将权值和写成$n^2$进制，这样权值相加可以保证不会发生进位，从而将比较大小改为比较两个字符串的字典序。每次转移中相当于在某一位加了个$1$，因此我们可以用主席树维护每个权值，比较大小时维护区间哈希值，在线段树上二分最长公共前缀，最终比较第一位不同的而得出大小关系。另外因为我们要维护每个点分别到起点和终点的最大值，最终求每一行的最大值前后缀需要进行加法，因为两者相加的哈希值等于两者的哈希值相加，所以直接将两棵树放一起进行比较即可。 | ||
| * comment：每一步转化都十分巧妙，同时也十分磨练码力。 | * comment：每一步转化都十分巧妙，同时也十分磨练码力。 | ||
| + | =====题目===== | ||
| + | * [[2020.7.27|每日亿题2020.7.27]] | ||
| + | * [[2020.7.30|每日亿题2002.7.30]] | ||
| =====个人训练===== | =====个人训练===== | ||
| ===== 2sozx ===== | ===== 2sozx ===== | ||
| 行 46: | 行 49: | ||
| * 2020.07.30 [[.2sozx:Codeforces Round 660 (Div. 2)|Codeforces Round #660(Div. 2)]] | * 2020.07.30 [[.2sozx:Codeforces Round 660 (Div. 2)|Codeforces Round #660(Div. 2)]] | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | * 无 | ||
| ===== Bazoka13 ===== | ===== Bazoka13 ===== | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | * 2020.07.30 [[.bazoka13:Codeforces Round 660 (Div. 2)|Codeforces Round #660(Div. 2)]] | ||
| ====题目==== | ====题目==== | ||
| ===== JJLeo ===== | ===== JJLeo ===== | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | * 2020.07.24 [[.JJLeo:codeforces_round_659_div._1|Codeforces Round #659 (Div. 1)]] | ||
| + | * 2020.07.25 [[.jjleo:m-solutions_programming_contest_2020|M-SOLUTIONS Programming Contest 2020]] | ||
| + | * 2020.07.28 [[.jjleo:educational_codeforces_round_92_rated_for_div._2|Educational Codeforces Round 92 (Rated for Div. 2)]] | ||
| + | * 2020.07.31 [[.JJLeo:codeforces_round_660_div._2_virtual_participation|Codeforces Round #660 (Div. 2) Virtual participation]] | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
2020-2021/teams/farmer_john/week_13.1596180877.txt.gz · 最后更改: 2020/07/31 15:34 由 jjleo
