Topcoder 669 Div1
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
------------------------------------------------------------------------
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]求出来了
好优美的算法~
------------------------------------------------------------------------
评论 (0)
