Vijos 1485 传球游戏 解题报告

用f[i,j]表示第i秒传到第j个人的方案数，递推式是f[i,j]=f[i-1,j-1]+f[i-1,j+1](1<=i<=m,1<=j<=n)，注意处理一下边界即可，初始化f[0,1]=1。由于f[i]只与f[i-1]有关，所以可以用滚动数组将空间复杂度降一维。

R1123595 Accepted 100 From IwfWcf－ P1485 FPC Vijos Dolphin 2009-1-26 11:27:14

Vijos 1361 天平称量 解题报告

利用分治求解，将n个球分成3份，取其中两份称量，若不等则较重的球必然在较大的一份中，否则较重的球必然在未称的的一份中。在此基础上再继续三分直到分得的一份中只包含一个球。

因此可以得到递推式f[i]=f[i div 3]+1(i mod 3=0),f[i div 3+1]+1(i mod 3<>0);

Vijos题解中许多人提到的利用公式trunc(ln(n)/ln(3))+1得到的结果对于n=3^i时是错误的，只是数据中没有这种情况。

R1070492 Accepted 100 From IwfWcf P1361    FPC Vivid Puppy 2008-11-18 17:35:46

ZJU/ZOJ 1666 Square Coins 解题报告

题目大意是给出若干个面值小于300的完全平方数的硬币，求出对于给定的面值，用这些硬币组合成这一面值的方案数。

很明显的背包式递推，一种面值的方案数等于所有能够单步抓化为这种面值的状态之和。因此可以得到递推式f[i+j^2]=f[i+j^2]+f[i](1<=j^2<=300,1<=i<=300-j^2)，边界条件是f[0]=1。

3068468    2008-09-13 14:13:32    Accepted    1666    FPC    00:00.00    404K    IwfWcf

ZJU/ZOJ 1827 The Game of 31 解题报告

题目大意是有分值为1-6的牌各4张，两人轮流取牌，如果其中一方取牌后对方无论如何取牌都会导致取过的牌的分值总和大于31，则当前取完牌的一方获胜。现给出两人已经取了的一些牌的信息，假设此后两人均使用最优策略取牌，问在当前局面下谁将获胜？

比较经典的博弈类递推模型，如果用f[i1,i2,i3,i4,i5,i6,sum]来表示当前已经取了的6种分值的牌的信息以及取了的牌的分值总和，则显然当sum=31时该状态是必胜态。于是根据博弈类递推问题的递推通式可以确定可以通过单步转化为必胜态的状态必为必败态，类似的，如果一个状态通过单步转化而成的全部是必败态，则其必为必胜态。

3067327 2008-09-12 13:05:46 Accepted 1827 FPC 00:00.01 880K IwfWcf@LZOI

ZJU/ZOJ 1893 A Multiplication Game 解题报告

题目大意是从1开始两个人轮流乘上2-9中的一个数，最先使结果>=n的获胜，假设两人均采取最优策略，问谁有获胜。

经典的博弈问题，以n=1000为例，若占住999到112，则对手必胜。必须让对手占领此段。如果56被对手占住，入必败段。问题转化成为占56。以此类推，程序实现就是不断除9除2一直到n<=1。

3026876 2008-08-07 18:25:30 Accepted 1893 FPC 00:00.00 408K IwfWcf

ZJU/ZOJ 1619 Present 解题报告

题目大意是有n个人各自买了一份礼物，打乱放在一起，每个人拿一份带走，问恰好有m个人拿回了自己那份礼物的几率是多少。

很明显的组合数学问题，题目所求的情况数实际就是c(n,m)*(n-m)的错排数。化简可得这样一条通项公式：∑((-1)^i/i!)/m!(2<=i<=n-m)。不过我没推出求∑((-1)^i/i!)的递推式，所以还是用了朴素的方法c(n,m)*(n-m)的错排数/n的全排列数，化简可得(n-m)的错排数/((n-m)!*m!)。可以做两个预处理优化，预先求出0到99的阶乘和错排数，用到时直接调用计算即可。

用f(n)表示n的错排数，求f(n)除了可以通过由容斥原理得到的f(n)的通项公式f(n)=n![1-1/1!+1/2!-1/3!+……+(-1)^n*1/n!]来求外，还可以通过递推来求。显然将任一位置的元素错排都有n-1种方法（将其插入到不同于自己位置的其它元素位置），假设第一个选取的元素为第i个位置的元素，将其插入第k个位置。我们可以分两种情况来考虑，假设第k个位置的元素插入到第i个位置，则实际上是对剩下的n-2个元素进行错排；假设第k个位置的元素不插入第i个位置，则实际上是对剩下的n-1个元素进行错排。根据乘法原理f(n)=(n-1)*(f(n-1)+f(n-2))。显然通过递推的方法来求错排数，无论是编程复杂度还是时间复杂度都优于用通项公式来求。

3018896 2008-08-02 22:24:15 Accepted 1619 FPC 00:00.01 416K IwfWcf@LZOI