2020-2021:teams:farmer_john:2020牛客暑期多校第九场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020牛客暑期多校第九场 [2020/08/14 17:34] jjleo [题意] |
2020-2021:teams:farmer_john:2020牛客暑期多校第九场 [2020/10/07 21:25] (当前版本) jjleo |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======比赛名称====== | + | ======2020牛客暑期多校第九场====== |
| [[https://ac.nowcoder.com/acm/contest/5674|比赛链接]] | [[https://ac.nowcoder.com/acm/contest/5674|比赛链接]] | ||
| =====A.===== | =====A.===== | ||
| - | **solved by ** | + | **solved by Bazoka13** |
| ====题意==== | ====题意==== | ||
| + | 给一个$2$进制表达式，求出十进制结果 | ||
| ====题解==== | ====题解==== | ||
| + | 使用$python$的$eval+replace$，一行$AC$ | ||
| =====B.===== | =====B.===== | ||
| **upsolved by JJLeo** | **upsolved by JJLeo** | ||
| 行 19: | 行 19: | ||
| 给定$n$个区间$[l_i, r_i]$，边界均为非负整数，每个区间有$\frac{1}{2}$的概率被选，求选择区间交集整点个数平方的期望，对$998244353$取模。$(1 \le n \le 5 \times 10^5, 0 \le l_i,r_i \le 10^9)$ | 给定$n$个区间$[l_i, r_i]$，边界均为非负整数，每个区间有$\frac{1}{2}$的概率被选，求选择区间交集整点个数平方的期望，对$998244353$取模。$(1 \le n \le 5 \times 10^5, 0 \le l_i,r_i \le 10^9)$ | ||
| ====题解==== | ====题解==== | ||
| + | 首先注意并不是求区间长度，而是整点个数，因此离散化时右端点要加一。\\ | ||
| + | 其次考虑如果求整点个数之和的期望怎么做，只需要离散化后扫一遍确定每个区间被覆盖了几次即可，设离散化后的一个区间出现了$x$次，该区间的整点个数为$y$，则对分子的贡献为$y(2^{x}-1)$，最后除以分母的$2^n$即可。\\ | ||
| + | 而本题需要求平方的期望，因此对于离散化后的一段区间，不能仅仅单独考虑它自己，还要考虑当它是交集一部分时与其它同处于交集一部分区间互相之间形成的贡献。例如对于一段区间整点个数的平方和可以进行如下分解$${(x+y+z)}^2=x(x+y+z)+y(x+y+z)+z(x+y+z)$$因此对于每一个离散化后的区间$i$来说，若考虑所有覆盖它的原始区间，可以得到离散化后的所有区间各被覆盖了多少次，设一个区间被覆盖次数为$x$，整点个数为$y$，则区间$i$对于分子的贡献即为$$y_i\sum_jy_j(2^{x_j}-1)$$整个过程使用线段树来一遍扫描线，线段树维护每一段整点个数乘以权值（因此区间加的时候要乘以整点个数），通过$\times 2 + 1$与$-1\times \frac{1}{2}$即可完成对上述值的维护。最后除以分母的$2^n$即可。 | ||
| =====D.===== | =====D.===== | ||
| **upsolved by JJLeo** | **upsolved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 给定一棵$n$个点的树，$i$号点上有$i$号人，第$i$条边只能允许$[l_i,r_i]$的人通过，每个人可以强行走$k_i$次不允许走的边，问$i$号人能到达点的个数。$(2 \le n \le 10^5, 0 \le k_i \le 1)$ | ||
| ====题解==== | ====题解==== | ||
| + | 首先dfs一次确定所有点的父亲以及深度。接下来上线段树分治，启发式合并维护一个比较特殊的并查集，每个并查集里面是一个连通块，除了常规的fa和siz，还要维护连通块最浅点以及所有“儿子”的siz之和。最后答案如果$k_i=0$则直接返回siz否则返回siz加上最浅点父亲所在连通块大小以及所有儿子的siz之和。可以发现这几个东西都是可以撤销的，细节比较多，一定要注意每个量的具体含义以及操作的顺序。 | ||
| =====E.===== | =====E.===== | ||
| **solved by 2sozx** | **solved by 2sozx** | ||
| 行 32: | 行 37: | ||
| **solved by JJLeo** | **solved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 给定一个序列，每个数有一种颜色，现在选出任意个数使得这个序列中拥有全部颜色且选出元素的最大值与最小值的差值最小。 | ||
| ====题解==== | ====题解==== | ||
| + | 滑动窗口滑就完事了。 | ||
| =====G.===== | =====G.===== | ||
| **upsolved by** | **upsolved by** | ||
| 行 50: | 行 57: | ||
| 考虑总计添加不超过 $k$ 个字符，容易看出可以通过生成函数解决这个问题。每个间隙的生成函数即为 $\sum_{i=0}^{\infty}g(j)^ix^i=\frac{1}{1-g(j)x}$ ，总的生成函数即为 $\prod_{i=1}^{n+1}\frac{1}{1-g(i)x}$ ，对分母分治$NTT$ 再求逆即可，前 $k$ 项系数和再乘原串本身的贡献即为答案。 | 考虑总计添加不超过 $k$ 个字符，容易看出可以通过生成函数解决这个问题。每个间隙的生成函数即为 $\sum_{i=0}^{\infty}g(j)^ix^i=\frac{1}{1-g(j)x}$ ，总的生成函数即为 $\prod_{i=1}^{n+1}\frac{1}{1-g(i)x}$ ，对分母分治$NTT$ 再求逆即可，前 $k$ 项系数和再乘原串本身的贡献即为答案。 | ||
| =====I.===== | =====I.===== | ||
| - | **upsolved by ** | + | **solved by 2sozx Bazoka13** |
| ====题意==== | ====题意==== | ||
| 行 58: | 行 65: | ||
| **solved by JJLeo** | **solved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 给定一个$n \times m$的$01$矩阵，求有多少个子矩阵满足四边都是$1$，中间部分$01$数量相差不超过$1$，且长宽均大于$1$。$(n,m \le 500)$ | ||
| ====题解==== | ====题解==== | ||
| + | 考虑枚举两列，保证两列都是$1$的情况下（否则清空），维护一下全$1$行及其前缀和，从上往下扫一遍即可。 | ||
| =====K.===== | =====K.===== | ||
| **solved by JJLeo** | **solved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| + | 给定一棵树，两个人各在一个节点，前者以$2m/s$追后者，后者以$1m/s$速度逃离，每条边长度为$1m$，问最晚多久才被抓。 | ||
| ====题解==== | ====题解==== | ||
| + | 以追人那个人为根dfs，枚举最后逃到哪个点，算一下距离讨论是否合法即可。 | ||
| =====L.===== | =====L.===== | ||
| **upsolved by ** | **upsolved by ** | ||
| 行 87: | 行 94: | ||
| =====总结===== | =====总结===== | ||
| * MJX：要勇于看还没看过的题 | * MJX：要勇于看还没看过的题 | ||
| + | * CSK：貌似非$C++$题还是会暂时蒙古一会？多学习$java python$节省时间的特性，同时注意复杂度 | ||
| + | * ZYF：不要纠结于一道题上太久，贪心没思路时要敢于发挥想象力。 | ||
2020-2021/teams/farmer_john/2020牛客暑期多校第九场.1597397672.txt.gz · 最后更改: 2020/08/14 17:34 由 jjleo
