Difference between revisions of "CCPC-Wannafly Winter Camp Day2 (Div 1)"
Xiejiadong (talk | contribs) (Created page with "= CCPC-Wannafly Winter Camp Day2 (Div 1) = == Problem A == Unsolved. == Problem B == Unsolved. == Problem C == Unsolved. == Problem D == Unsolved. == Problem E == Un...") |
Xiejiadong (talk | contribs) |
||
(4 intermediate revisions by the same user not shown) | |||
Line 23: | Line 23: | ||
== Problem F == | == 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 == | == Problem G == | ||
Line 31: | Line 35: | ||
== Problem H == | == Problem H == | ||
− | + | Solved. | |
+ | |||
+ | 温暖的签到题。 | ||
+ | |||
+ | 题意:给出$n$个互不相交的球,求出每个球与大球交集的体积之和。 | ||
+ | |||
+ | 题解:对于每个球,只需要保存半径和距离大球的距离。可以通过积分求出交集部分体积公式,特判并求和即可。 | ||
== Problem I == | == Problem I == | ||
Line 43: | Line 53: | ||
== Problem K == | == 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 == | == Problem L == | ||
Unsolved. | Unsolved. |
Latest revision as of 11:49, 26 February 2019
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.