2020-2021:teams:farmer_john:2020hdu暑期多校第二场
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020hdu暑期多校第二场 [2020/07/31 16:16] jjleo [题解] |
2020-2021:teams:farmer_john:2020hdu暑期多校第二场 [2020/10/07 21:24] (当前版本) jjleo |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======比赛名称====== | + | ======2020HDU暑期多校第二场====== |
| [[https://codeforces.com/gym/288624|比赛链接]] | [[https://codeforces.com/gym/288624|比赛链接]] | ||
| =====A.===== | =====A.===== | ||
| 行 10: | 行 10: | ||
| 我们考虑将 $b_i$ 从大到小排序，对于扫到的点我们只考虑比当前枚举的 $b_i$ 大的点。先将 $b_i$ 加入答案，如果此时不在一个联通块中将其合并，并且可以从答案中减去 $b_i$，因为在考虑过这个点之后比他大的点就可以少操作 $b_i$ 次，用并查集维护联通即可。 | 我们考虑将 $b_i$ 从大到小排序，对于扫到的点我们只考虑比当前枚举的 $b_i$ 大的点。先将 $b_i$ 加入答案，如果此时不在一个联通块中将其合并，并且可以从答案中减去 $b_i$，因为在考虑过这个点之后比他大的点就可以少操作 $b_i$ 次，用并查集维护联通即可。 | ||
| =====B.===== | =====B.===== | ||
| - | **solved by** | + | **upsolved by** |
| ====题意==== | ====题意==== | ||
| 行 25: | 行 25: | ||
| 给定一个$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$，因此我们可以用主席树维护每个权值，比较大小时维护区间哈希值，在线段树上二分最长公共前缀，最终比较第一位不同的而得出大小关系。另外因为我们要维护每个点分别到起点和终点的最大值，最终求每一行的最大值前后缀需要进行加法，因为两者相加的哈希值等于两者的哈希值相加，所以直接将两棵树放一起进行比较即可。 | ||
| 行 37: | 行 37: | ||
| 找二次函数顶点，周围扩一定量的点，肯定是最优的，但是不能一个扩$n$个不然$O(n^5)$会炸的。然后乱搞一波套EK就过了。 | 找二次函数顶点，周围扩一定量的点，肯定是最优的，但是不能一个扩$n$个不然$O(n^5)$会炸的。然后乱搞一波套EK就过了。 | ||
| =====F.===== | =====F.===== | ||
| - | **solved by ** | + | **solved by Bazoka13** |
| ====题意==== | ====题意==== | ||
| + | 给定两个按照斐波那契表示法的a,b,从a*b的结果中删去斐波那契数列的一项，询问删除的第几项。 | ||
| ====题解==== | ====题解==== | ||
| + | 显然有$a*b=c+f[k]$，那么在模意义下找到等于$a*b-c$的那项即可，因为担心同余所以取双模，记得不要乱开ll | ||
| =====G.===== | =====G.===== | ||
| **upsolved by JJLeo** | **upsolved by JJLeo** | ||
| 行 53: | 行 55: | ||
| 考虑函数不增不删只有数次询问的情况，可以发现这些函数都是$f(x)=x^4$进行平移得来，两两只会相交一次并在此处改变大小关系，因此可以类似决策单调性dp中的二分栈，维护出每个区间的最优函数，对于每个询问只需二分找到对应区间即可获得答案。但本题有函数的增删，因此可以再套一个线段树分治，对每一层都来一次上述过程，处理区间中所有的询问，而每个询问只需取最小值即可。这样每个询问被处理$O(\log n)$次，每个函数被处理$O(\log n)$次，总复杂度$O(n \log ^2 n)$。（一开始把所有函数和询问全在叶子节点处理，直接白分治了） | 考虑函数不增不删只有数次询问的情况，可以发现这些函数都是$f(x)=x^4$进行平移得来，两两只会相交一次并在此处改变大小关系，因此可以类似决策单调性dp中的二分栈，维护出每个区间的最优函数，对于每个询问只需二分找到对应区间即可获得答案。但本题有函数的增删，因此可以再套一个线段树分治，对每一层都来一次上述过程，处理区间中所有的询问，而每个询问只需取最小值即可。这样每个询问被处理$O(\log n)$次，每个函数被处理$O(\log n)$次，总复杂度$O(n \log ^2 n)$。（一开始把所有函数和询问全在叶子节点处理，直接白分治了） | ||
| =====I.===== | =====I.===== | ||
| - | **upsolved by ** | + | **solved by ** |
| ====题意==== | ====题意==== | ||
| 行 71: | 行 73: | ||
| =====L.===== | =====L.===== | ||
| - | **upsolved by JJLeo** | + | **solved by JJLeo** |
| ====题意==== | ====题意==== | ||
| - | 给定两个字符串$s$和$t$，每次问$s$一个子串和$t$的距离。字符串的距离定义为每次操作可以选择两个字符串之一，删除任意一个字符，或在任意位置添加一个字符，最少的次数将两个字符串变为一样。$(|s| \le 10^5, |t| \le 20)$ | + | 给定两个字符串$s$和$t$，$q$次询问$s$一个子串和$t$的距离。字符串的距离定义为每次操作可以选择两个字符串之一，删除任意一个字符，或在任意位置添加一个字符，最少的次数将两个字符串变为一样。$(|s|,q \le 10^5, |t| \le 20)$ |
| ====题解==== | ====题解==== | ||
| - | 距离本质就是两者长度减去两倍的最长公共子序列长度。因此本题就是求$s$的子串和 | + | 距离本质就是两者长度减去两倍的最长公共子序列长度。因此本题就是求$s$的子串和$t$的最长公共子序列，因为$t$长度很小，可以设$f_{i,j}$为匹配到$t$的第$i$位，此前有$j$位匹配时$s$最靠前的匹配点。只需预处理出$s$中每个位置距离下一个每个字符最近的距离（子序列自动机）即可。 |
| =====记录===== | =====记录===== | ||
| 0min：分题，又没找到签到题\\ | 0min：分题，又没找到签到题\\ | ||
| 行 88: | 行 90: | ||
| * MJX：并查集合并出问题，太离谱了。 | * MJX：并查集合并出问题，太离谱了。 | ||
| * ZYF：感觉低级错误太多，码力不够，WA了无数次，浪费了大好时光。最后G写对了可惜被卡常了。 | * ZYF：感觉低级错误太多，码力不够，WA了无数次，浪费了大好时光。最后G写对了可惜被卡常了。 | ||
| + | * CSK：不开ll见祖宗，乱开ll见祖宗 | ||
2020-2021/teams/farmer_john/2020hdu暑期多校第二场.1596183377.txt.gz · 最后更改: 2020/07/31 16:16 由 jjleo
