正文
BestCoder Round #40
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
T1：Tom and pape (hdu 5224)
题目大意：
给出一个矩形面积N,求周长的最小值.(长&&宽&&面积都是正整数) N<=10 9
题解：
没啥好说的,直接暴力O(sqrt(N))枚举约数即可。
T2: Tom and permutation(hdu 5225)
题目大意：
给出一个N的排列,求字典序比它小的所有N排列的逆序对数之和. N<=100
题解：
类似数位DP,从前往后枚举每一位,预处理出dp[x]表示1-x的所有排列的逆序对数之和。然后计算逆序对分为3部分。
分别是确定的前i位之间的逆序对,确定的前i位和未确定的位之间的逆序对,未确定的位之间的逆序对(dp[n-i]).
时间复杂度O(N 2 ).
T3: Tom and matrix(hdu 5226)
题目大意：
计算组合数C(x1...y1,x2....y2) mod P的和. 数据范围<=10 5 .
题解：
记得组合数学上有个公式。 C(n+1,r+1)=C(n,r)+C(n-1,r)+C(n-2,r)+....C(0,r) r>=1.
感觉应该要用这个来搞.然后我傻逼的把每一项拆成很多项,怎么都搞不出来。
其实这题是这个公式的逆运用。应该把后面的一串当成前缀和搞一搞。
枚举j=x2 to y2 ans+=C(0..y1,j)-C(0..x1-1)=C(y1+1,j+1)-C(x1,j+1).
模数P比较小,预处理阶乘逆元 用lucas搞一搞就好啦。
T4：Tom and game(hdu 5227)
题目大意：
一个四元组(a,b,c,d)是合法的当且仅当b<=a && c<=a && d<=gcd(b,c).
给出N个节点的一棵树,每个节点上是一个合法的四元组. 2个人玩游戏,选择一条路径上的所有四元组,每个回合选一个四元组把它变成字典序比它小的一个四元组.最后不能操作的就输了。 问先手胜的概率。 N,a,b,c,d<=10000
题解：
这题2个关键点。
1.如何求出一个四元组的SG,可以发现SG值就是比它小的四元组的个数. 具体求的时候用莫比乌斯反演搞一搞,官方题解写的很详细,就不写了。 比较综合的数论练习题。
2.求出SG异或和为0的路径数。我一开始的做法是求出根到x的异或和,如何傻逼的以为x到y的异或和等于根到x的异或和异或根到y的异或和,然后hash去搞了,WA到死.如果权值在边上不在点上,那么这样做应该是对的。但是权值在点上的话就会把LCA(x,y)的值搞没了。 所以还是按照官方题解用了点分治+map。
总结：本次比赛的失误主要在于第三题,第三题那个公式我是知道的,但是用反了。第四题是非常好的一道题,虽然这东西比赛的时候不但想不到而且写不出来..
