学步园

hdu上代码还没放出来，先写下大致的思路了。

就按比赛时我的做题顺序写了。。。

1008：Hard Disk Drive

题意：就是硬盘容量的计算，硬盘上标的是按1000进制的，而真实值则是按1024进制的，给出一个硬盘标出的容量，问真实容量是多少。

解题思路：就按hint计算 100[MB]，1-(100 * 1000 * 1000 ) / ( 100 * 1024 * 1024) ，很简单吧。上下两个100是可以约掉的，然后就是1-(1000/1024) ^ n，n是从标的单位转到B的级数。

1006：Fibonacci Tree

题意：给出一个双向图，然后图上的边有两种，白边跟黑边，选取图上的若干条边，使图成为一颗生成树，问这个生成树上的白边数是否有可能是fib数。

解题思路：我们先求出构成生成树最少要多少条白边，最多可以有多少条白边，然后看，在这个范围内是否有fib数。为什么可以这么做呢？我们从最小值开始考虑，然后用未被加在树上的边去替换树上的边，使之仍然成为生成树，那么，我们这样一条一条的替换过去，最终总能替换到最大值，那么因为我们是一条一条的替换过去的，所以每次要么增加一条白边，要么不增加，也就是说，我们从最小值到最大值都能取到了。是不是很简单？

1010：Just Random

题意：x属于[a,b]，y属于[c,d]，问有多少种(x,y)的组合，使得(x+y) % p = m ;

解题思路：(x+y) % p = m 转换成 (x+y-m)%p = 0 继续转换(x+y+p-m) % p = 0;那么问题就转换成，在x属于[a,b] ， y(新的y)属于[c+p-m,d+p-m]，（请注意，后面的[c,d]都用[c+p-m,d+p-m]代替）有多少种(x,y)的组合使得(x+y) % m = 0；首先我们可以考虑这样一个东西，(a+b) % p = 0 则 (a+1 + b-1 ) % p = 0 ，(a+k*p + b) % p = 0这样两个式子都没错吧吧？这两个式子要结合起来用，第一个式子说明从[a,b]中取一段长为p的连续递增区间，在[c,d]中也会存在一段连续的递减区间与之一一对应相加起来取余p等于0（先假设[a,b]，[c,d]范围足够大），第二个式子说明，从第一个式子里推出的区间中，[a,b]里拿出来的可以任意的跟[c,d]里拿出来的组合。但是这样的区间有可能不是完整的，[a,b]，[c,d]开头跟结尾有可能会有一些多余出来，先考虑完整的区间，我们在[a,b]中这样取区间，以a为开头，然后按递增的每p长度取一次区间，那么对应在[c,d]中，会是从什么地方开始呢？是不是从d-(a+b)%p,设这个值为e,的地方开始取，按递减，每p个长度取一个区间。设[a,b]中能取出的完整的区间数是cnt1,[c,d]中取出的完整的区间个数是cnt2，那么对应的完整的部分能取到的答案就是cnt1*cnt2*p。接下来就是不完整的区间的考虑了，对于[a,b]区间，因为我们是从a开始取的，因此开头不会多出来，多出来的只会在尾部，假设多了r个，而[c,d]中，有可能开头会有多出来，假设是t个，结尾也有可能会有多出来，假设是z个。因为[c,d]是从e开始，倒着往前去的，我们能取到的长度l2=max(0,e-c+1)。那么r= (
b - a + 1 ) %p;t = l2 % p ;z = ( a + d ) % p ;然而这个z我们是不一定能取到的，结尾的地方，最多只会多出d-c+1个，当p很大的时候，z的值可能会超过d-c+1，因此z = min ( z , d - c + 1 ) ;好了，下面就是要怎样统计这个问题了，[a,b]中取出的完整区间可以跟[c,d]中所有的不完整的配，也就是ans += cnt1 * (t+z);同样的[c,d]中取出的不完整的区间也可以跟[a,b]中不完整的配,也就是ans += cnt2 * r
;然后就是两部分中，都不完整的配，这个我只能先贴一下这部分代码了，只有三句话：

ans += min ( r , t ) ;
ll v = p - ( a + d ) % p ;
ans += max ( (ll)0 , min ( r - v , z ) ) ;

这里要解释清楚有点复杂，有想了解的可以留言详谈。

这题代码还在：