http://acm.tdzl.net:83/JudgeOnline/showcontest?contest_id=1016

A Gardon's box I
1-n按顺序入栈，要求列出所有可能的出栈序列。
n<=10，DFS即可。每次有入栈和出栈两种选择。优先选择出栈可以得到字典序的排列。
也可n!生成排列再每次O(n)进行判断。

B Gardon's box II
问题同上，求所有可能性的总数。
我的解法是将这个问题等同于如下问题：
若干人买票，有些人手持50元的钱，有的人手持100元的钱，售票员一开始没有零钱找，问有多少种排列方法。
这个问题首先由C(2n,n)种排列中，有若干不合法的排列，将任一不合法的排列第一个不合法位置之后的所有拿50元的换成100元，拿100元的换成50元，即得到一个n-1个50元和n+1个100元的排列。并且任一这种排列也可以用相同方法得到之前问题的不合法排列。
所以，原问题的所有合法排列数为：C(2n,n)-C(2n,n-1)或者C(2n,n)/(n+1)

C Gardon's box III
给任一入栈顺序，要求出栈顺序按照字典序第k大的排列。
解法是从第一个元素开始直接计算出每个位置应该的值。
设函数B(i,j)表示栈中有i个元素，并且还有j个元素没有入栈的所有排列数，则对于每一个位置可以轻易计算出选择某一个数时所有的排列总数c。此时将k不断减去c直至k小于等于c，就可以确定出这一位置的数字。

D Gardon's box IV
三维空间的九宫问题，问是否有解。
方法是判断逆序数和0的三个坐标之和的奇偶性。任意一次移动（相当于交换两个元素）必然带来逆序数奇偶的改变，同时0的三个坐标之和的奇偶性也会改变。并且可以构造证明当有两个以上边长大于等于2时，一定有解。
要考虑的特殊情形就是两个方向的边长都是1的时候，譬如
1 1 4
1 2 3 0
3 1 2 0
不能根据逆序数来判断，而应该将0去掉以后比较剩下所有元素，依次相等才有解。

E Clean the house
三分图匹配，DFS可以过，也可以模仿二分图匹配用增广法求解。

F Apple
概率题，两个人玩游戏，B每轮赢得几率为p，A持有a个苹果，b持有b个苹果，每轮败者给胜者1个苹果，直至其中一人手里没有苹果。问游戏平均要经过多少轮才能结束。
可列出如下等式，设f(i)为B持有i个苹果时的期望值，则有
f(i)=(1-p)f(i-1)+pf(i+1)+1
并且f(0)=f(a+b)=0
可二分搜索f(1)并确认f(a+b)的值，不过实践证明精度很低。我的解法如下：
设f(i)=k(i)f(1)+t(i)
则有
k(0)=0 t(0)=0
和
k(1)=1 t(1)=0
最后解出k(a+b)和t(a+b)，则直接可得出f(1)=-t(a+b)/k(a+b)
然后直接将k(b)和t(b)带入求出f(b)即可。

G Garra Fibonacci
F(0)=a F(1)=b F(i)=N，并且对于0<=i F(i)都是非负整数，给出i和N，问有多少组可能的a。
设f(i)为fibonacci序列，并且设f(-1)=1 则有
F(i)=f(i-1)a+f(i)b
首先用扩展欧几里德求出一组ax+by=1（其实x和y的绝对值就是f(i-1)和f(i-2)），然后将它乘上N，再通过取余得到a最小的非负解（每当a增加f(i)，b就要减少f(i-1)）
此时如果b是负数，则无解，否则b/f(i-1)取整+1即为最终解。

H Gauss Pascal Number
对所有的j<n and (i+j)=0 mod m求C(i,j)
首先看对某一行第k行（也就是C(k-1,j)行，先假设k%m==0）
设i^m=1，则(1+i)^n的常数系数即为所有对应项之和。该乘法可以表示成如下矩阵A的幂：
1 1 0 ... 0 0
0 1 1 ... 0 0
0 0 1 ... 0 0
.     ... . .
.     ... . .
0 0 0 ... 1 0
0 0 0 ... 1 1
1 0 0 ... 0 1
其实若k%m==0，该行所有对应项之和就是该矩阵乘积左上角元素。若k%m!=0，其实取出第一行第((m-k)%m)项即可。
所以，对于不同行的偏移情况，构造轮换矩阵C
0 0 0 ... 0 1
1 0 0 ... 0 0
0 1 0 ... 0 0
.     ... .
.     ... .
.     ... .
0 0 0 ... 1 0
左乘即可。
因此构造矩阵：
A I
O C
求n次幂，将右上角矩阵取出，补上C的(m-(n%m))%m次方（或者直接取出对应项）即可。
这样就避免了复杂度里出现N，总复杂度m^3*log n

• 赞~ E能不能详细说下? (0) RoBa 2006-10-15 18:05:44
• 除了E全部都是数学题，太不平衡了 (2240) frkstyc 2006-10-15 18:31:41
• Re:DYGG's contest 12解题报告 (2240) mmdcat 2006-10-16 13:29:29
  • 汗 不小心点错了 (0) mmdcat 2006-10-16 13:29:59
• 这不是我们学校的牛人邓云么 (0) bergkamp 2006-12-28 13:01:11
  • 恩。。。是我师父啊 (0) flymouse 2006-12-28 13:33:43
• Re:DYGG's contest 12解题报告 (2240) 0806401014 2009-08-21 15:12:45