CCPC-Wannafly Winter Camp Day2 (Div 1)

CCPC-Wannafly Winter Camp Day2 (Div 1)

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Solved.

题意：给出一个限制递归层数不超过k-1的快速排序，求任意一个排列排序下来的逆序对期望个数

思路：对于一次划分以后，可能出现的逆序对只有可能出现在子区间以内而不会跨越枢轴。因为是任意排列，假定一切都是对称的（并不会严谨归纳。。。），取得枢轴成为第x大是等概率的（感觉都是对称的都能找到原来的排列）。然后就可以递推了。$dp_{ij}$表示长度为i，层数不超过j-1的情况，$dp[i][1]=i*(i-1)/4$，这是一次排序都没做，所有排列的逆序数的平均。$dp[i][j]=sum_{k=1}^{i-1}{(dp[k][j-1]+dp[i-1-k][j-1])/n}$，每一个枢轴等概率的成为第x大，剩下的逆序对只能由两个子区间里贡献。数据要求预处理出$n^2$的，因此还需要前缀和优化，还有点卡常，推荐使用int。

Problem G

Unsolved.

Problem H

Solved.

温暖的签到题。

题意：给出$n$个互不相交的球，求出每个球与大球交集的体积之和。

题解：对于每个球，只需要保存半径和距离大球的距离。可以通过积分求出交集部分体积公式，特判并求和即可。

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved.

这题目也太卡常了。

题意：$12$根火柴，分成四组，最多能有给足可以构成三角形。

题解：直接暴力，TLE。我们只能先把所有的集合情况预处理出来。

处理的方法是，用$12$的阶乘，默认$3$个$3$个分组，为了保证不重不漏，要求$3$个内部有序，而且每组的第一个有序，即$a[k]<a[k+1]<a[k+2](k\equiv 0(mod\; 3))$而且$a[1]<a[4]<a[7]<a[10]$。

然后每一组数据，都是根据预处理出来的集合情况来枚举所有火柴的分组情况。

这样的时间复杂度正好贴着时限。

Problem L

Unsolved.