7.11测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-----------------------------------------------------------------
挂零场...
(看了题解之后感觉)明明T1T2都不难
感觉考试的时候脑子里都是一团浆糊
-----------------------------------------------------------------
T1:题意是给你一个排列,问你冒泡排序直到有序要排做多少轮
设f(i)是i这个位置的数向前回到ai这个位置的回合数(如果ai>i就不管)
显然答案就是max{f(i)}
然后发现每一轮如果i>ai,那么ai前面一定有比ai大的数(鸽巢原理),并且YY一下就知道一定会有一个数向右移越过ai,因此ai会向左移动一格
因此只要i>ai,ai就会向左移
因此答案就是max{i-ai}
-----------------------------------------------------------------
T2:题意是用一个n维半平面x1+x1+...+xn<=s去和一个n维超立方体{(x1,x2...xn) | xi∈[0,ri] }求交,求交的部分的体积
首先n维边长为a的超正三角形(?)的体积公式S(n,a)YY一下就知道是:a^n/n!(对n-1维超直角三角形的体积积分一下就好了)
然后考虑用S(n,s)减去每一维超出的,再加上算重的,这样
然后就不难得到一个容斥:
设K={r1,r2,...rn}
设Sum(A)=A的所有元素之和
答案r=Σ(c∈K)[Sum(c) <= s]S(n,s - Sum(c))(-1)^|c|
然后暴力枚举子集就有60分辣
然后考虑优化
因为ri<=M
因此Sum(c)<=n*M
因此可以把Sum一样的一起搞
设f(i,j)表示前i个,Sum为j的子集的系数之和
那么就有f(i,j)=f(i-1,j)-f(i-1,j-ri) (考虑把某个ri丢进某个集合形成和为j的,然后要乘以一个-1)
然后一起算就行了
大概就是Σ(i=0,n*M)(s - f(n,i))^n/n!这样
-----------------------------------------------------------------
T3:
挺..挺麻烦的
有(mei)时(shi)间(gan)再搞
-----------------------------------------------------------------
评论 (0)
