CVBB ACM Team

题意:略长的签到。

题解:摸了。

题意:对于给定的$n$，将$\{1,2,\ldots,i\}$分为两部分，使两部分之和的差值等于$n$，问$i$最小是多少。$(0 \le n \le 10^9)$

题解:设分成两部分的和为$x$和$y$，且$\sum_{j=1}^{i}{j}=m$，有$x+y=m,x-y=n$，解得$x=\frac{n+m}{2}$，因此从小到大枚举$i$，第一个$\frac{n+m}{2}$是整数且$\frac{n+m}{2} \ge m$的$i$即是答案。因为$\{1,2,\ldots,i\}$可以分出一个子集使得它的和等于任意$\le \sum_{j=1}^{i}{j}$的值。

题意:大水题，感觉应该和B换位置。

题解:摸了。

题意:数轴上给出$n$个的线段，所有端点两两不等，没有线段退化成点，所有端点恰好铺满$1,2,\ldots,2n$。每个线段对应一个节点，如果两条线段相交且不包含，那么它们对应的节点中间有一条边，问是否生成的图是一棵树。$(1 \le n \le 5 \cdot 10^5)$

题解:（45min时写完了因为细节WA了6次到70min才A，太菜了）按照左端点排序，然后每处理完一个节点放入按右端点排序的set，与所有右端点处于$[l_i,r_i]$的对应的节点连线，使用并查集记录判断最终是否是一棵树即可。

题意:给出一颗$n$个节点的树，构造出$n$个线段，将每个节点对应到一个线段。要求这$n$个线段是一组合法的D题输入，且按照D题的规则生成的图是该题中输入的树。$(1 \le n \le 5 \cdot 10^5)$

题解:核心思想就是，父子节点相交，兄弟节点完全包含。随便选一个根进行$dfs$，维护当前最右的端点，每个节点通过拓展最右端点为子节点们留好左端点的空间，并将这个点作为右端点，然后每个子节点的左端点从父亲右端点开始向左递减即可。

题意:洗$n$次牌并在洗牌后看顶端的牌，每次有$\frac{1}{m}$的概率翻到Joker，设$x$是翻到Joker次数，求$x^k$的期望，对$998244353$取模。$(1 \le n, m < 998244353, 1 \le k \le 5000)$

题解:数学太差，才知道$x$期望的$k$次方和$x^k$的期望是不一样的。假设第$a_1,a_2,..,a_x$次翻到了Joker，那么对期望的贡献就是$x^k$，等价于长度为$k$的有序序列的个数，例如对于$a_1,a_2,a_3$次翻到了Joker，$k=2$时，有序列为$(a_1,a_1),(a_1,a_2),(a_1,a_3),(a_2,a_2),(a_2,a_3),(a_3,a_3)$。因此只需要求出具有不用元素种类的长度为$k$的本质不同有序序列个数，再乘以各自的概率即可获得期望。设$f_{i,j}$为长度为$i$元素种类数为$j$时本质不同的有序序列个数，转移为$f_{i,j}=f_{i-1,j} \times j + f_{i-1,j-1} \times (n - j + 1)$，即选一个旧的元素和选一个新的元素。最后元素种类数为$j$时的概率为$\frac{1}{m^j}$，相乘再加起来即可得到期望。