CVBB ACM Team

分类：平面图对偶图，点定位，扫描线，最小生成树，倍增

题意：给定一个平面图 $n\le10^5$，每条边有权值，$q$ 次询问，每次给出平面上两个点，问所有不通过无穷大平面的曲线链接这两个点所经过的边的最小值是多少。$q\le10^5$，平面图的点为整点，询问的点坐标为 $0.5$ 的奇数倍且不在边上。

题解：先用最左转线将平面图进行划分，转成对偶图，并且连边，求出对偶图的最小生成树。对于每个点我们要定位在属于对偶图的哪个点，因此将线段进行排序，用扫描线从左向右扫描，将扫到的线段插入 $treap$ 中，如果遇到了询问的点则在 $treap$ 中找到比这个点高的最低的线段，则这个点则属于这条线段下方的区域内，对于每个询问可以通过在最小生成树上倍增求解即可。

comment：知识点巨多，虽然还没通过hack数据，但是感觉还是一道好题。

分类：动态规划、概率

题意：在一条长度为$l$的线段上随机出现$n$条线段，求被$k$条线段覆盖的长度之和

题解：$dp[i][j]$用来表示前$i$个端点里有$j$个起点没有被匹配的方案数，然后转移的时候就有两种情况，要么是起点，要么是终点

comment：学弟出的题真的🐂啊，，，

分类：动态规划，概率期望。

题意：数轴上一共有$2n+1$个点，每个点的坐标为$x_i$，下标为奇数的点为洞，下标为偶数的点为球，每次等概率地随机选择一个球，等概率地往左或往右推动它，直到它落入遇到的第一个洞里，每个洞只能放一个球。求球滚过距离之和的期望，对$998244353$取模，多组数据。$(n \le 3000, \sum n \le 10^6)$

题解：每次推球这个过程可以转化为从一个序列中每次选择两个相邻的数，使得总路程增加$|x_i-x_j|$，然后将这两个数从序列中删除，不断重复上述操作直到只剩下一个数。考虑拆开上述的绝对值，一个数如果和它右边的数一起被删，贡献为$-x_i$；如果和它左边的数一起被删，贡献为$x_i$；如果没被删，贡献为$0$。因此我们设$f_{i,j}$为一个数左边有$i$个数，右边有$j$个数时和它右边的数一起被删的概率，我们可以通过$O(n^2)$dp预处理出该数组，考虑当前状态一共有$(i+j)$种删除方案，对于每一种删除后都可以转化为一个子问题，因此有如下的递推：

for(int i = 0;i <= n;i++){
	for(int j = 1;i + j <= n;j++){
		if((i + j) & 1) continue;//显然本题中i+j必然为偶数
		if(j) f[i][j] = 1;
		if(j > 1) f[i][j] = (f[i][j] + 1ll * f[i][j - 2] * (j - 1)) % p;
		if(i > 1) f[i][j] = (f[i][j] + 1ll * f[i - 2][j] * (i - 1)) % p;
		f[i][j] = 1ll * f[i][j] * inv[i + j] % p;
	}
}

最后对于每一组数据，答案为$\sum_{i=1}^{2n+1}(f_{n-i,i-1}x_i-f_{i-1,n-i}x_i)$，总复杂度$O(n^2+\sum n)$。

comment：转化过于巧妙，同时$n$奇特的范围也在暗示预处理。

2020.08.14 Educational Codeforces Round 93 (Rated for Div 2)

暑假题目汇总