Topcoder 669 Div1

------------------------------------------------------------------------
QAQ
 
------------------------------------------------------------------------
250:
题意是有一个史莱姆,一开始大小为s,然后每一次你可以选一个史莱姆把他分成两个,使得这两个得大小之等于原来那个,获得这两个大小之积的价值,问最少操作多少次使得代价超过m,s <= 200 , m <= 10^9
YY一下就知道对于一种状态,不管怎么得到他,代价都是一样的
然后再YY一下发现,对于相同的步数,坑定是越均匀越好
于是枚举一下步数就行了
------------------------------------------------------------------------
600:
不屑(hui)做
------------------------------------------------------------------------
1000:
题意是问用m的幂无序地拼成n有多少种拼法,m<=1000,n<=10^18
这题太一颗赛艇了
首先这个问题可以转化成另一个问题:
一只YYY在数轴上跳,一开始在0,目标位置在n,他每次只能向右跳m的幂次的长度,并且由于体力不支的原因,这一次跳的长度一定要小于等于上一次,问最后跳到位置n的方案数
然后如果要问最少跳几次的话,显然有一个贪心:m^i用的次数是(n mod m^(i+1))/m^i(向下取整)
假设YYY就这么跳,经过的那些位置称为关键位置
有一个结论:不管怎么跳,关键位置一定会被跳到,这个证明挺简单的YY一下就知道了(要使用条件m^i | m^j(j >= i))
现在设一个矩阵f[k],f[k][i][j](i>=k)表示YYY跳到k这个位置,第一次跳的大小>=m^i,最后一次跳的大小恰等于m^j
考虑m = f[k]*f[l] : m[i][j] = Σ(f[k][i][o]*f[l][o][j])
发现就是转移了一次
那么得到结论:如果k对于n而言是一个必须经过的位置的话,就有f[n] = f[k]*f[n-k]
因为我们已经得到了关键位置,所以就可以倍增啦
怎么求f[m^i]?
很显然,要跳到m^i这个位置,要么一步跳过去,要么一定要经过0*m^(i-1),1*m^(i-1),2*m^(i-1)...m*m^(i-1)这些位置
因此f[m^i]等于f[m^(i-1)]^m + (一个除了第i列第i~log(n,m)行是1之外全部是0的矩阵)
然后就可以倍增把f[n]求出来了
 
好优美的算法~
------------------------------------------------------------------------