国家集训队2005论文集 唐文斌

《国家集训队2005论文集 唐文斌》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、正难则反——浅谈逆向思维在解题中的应用绍兴市第一中学唐文斌引入有一排路灯，一共八盏，均关闭。要求打开其中三盏，没有任意两盏相邻，有多少种不同的方式。如果直接考虑三盏打开的灯，需要讨论！不妨来考虑没有被打开的那些灯。引入要开3盏灯，则有5盏是关闭的两盏相邻的关闭的灯之间只能插入一盏开着的灯等价于在六个可选位置中选三个插入开着的灯所以答案为C(6,3)逆向思维引入逆向思维是一种思考问题的方式，它有悖于通常人们的习惯，而正是这一特点，使得许多靠正常思维不能或是难于解决的问题迎刃而解。问题答案例一、DinnerIsReady[题

2、目描述]M根骨头分给n个孩子，第i个孩子有两个参数Mini和Maxi，表示第i个孩子至少要得到Mini根骨头，至多得到Maxi根骨头。给出n(0

3、n=MMin1≤X1≤Max1Min2≤X2≤Max2……Minn≤Xn≤Maxn对于方程组的简单形式xxxX1+X2+…+Xn=MxxxXi≥0(1≤i≤n)我们知道方程解数为C(M+n-1,n-1)设Yi=Xi+Mini则方程组变为：Y1+Y2+Y3…+Yn=M-Min1-Min2-…-Minn0≤Y1≤Max1-Min10≤Y2≤Max2-Min2……0≤Yn≤Maxn-Minn下界我们可以通过换元得到简单形式但是上界仍然无法解决！例一、DinnerIsReady设S为全集，表示满足Xi≥Mini的整数解集。设Si

4、为S中满足约束条件Xi≤Maxi的整数解集,Si为Si在S中的补集，即满足Xi>Maxi(Xi≥Maxi+1)

5、Si

6、无法计算，但是，

7、Si

8、可解！！！那么，我们是否可以通过可解的

9、Si

10、从而得到无法计算的

11、Si

12、呢？例一、DinnerIsReady于是，我们就得到了：例一、DinnerIsReady至此，问题已经被解决。时间复杂度为O(2n*(n+M))在原集合Si的模

13、Si

14、不可解的情况下，我们通过可解的

15、Si

16、得到了一个基于容斥原理的算法。例二、GreedyPath[题目描述]给定一个有向图G=(V,E)对于e∈E

17、,有参数Ce和Te,分别表示该条边的费用与时间。求一个回路，使得回路中费用总和与时间总和的比值最大。例二、GreedyPath题目是求一条回路，但不是边权和最大或者最小，不能直接使用经典算法，似乎无从下手。我们的目标是找一条回路C=(V’,E’),使得F(C)最大：例二、GreedyPath设S为G中所有回路组成的集合。假定C*=(V*,E*)∈S就是我们要求的最优回路定义函数O(t):例二、GreedyPath我们做一个猜想：如果有o(t*)=0，也就是存在C*=(V*,E*)∈S满足：我们认为C*就是最优回路！证明：

18、如果存在另一条回路C1=(V1,E1)∈S更优则与O(t*)=0矛盾例二、GreedyPath更进一步，可以发现：如果t*是最优答案，则存在：根据该性质，便得到了算法：我们只要从一个包含t*的区间(tl,th)开始，不断地二分，计算o((tl+th)/2)，得到新的上下界，直到达到精度要求。时间复杂度为O(lgK*N3)例三、BuildingTowers[题目描述]用N块积木来搭建H层的塔(不一定要用完所有的积木)要求相邻的两层积木数量相差为1最底层积木数量为M(N≤32767,H≤60,M≤10)任务1：可以搭建成多少

19、种不同的塔?任务2：用H个整数从底到顶表示一个塔的结构，问字典序第K小的塔是什么？(H=6,M=2,N=13)例三、BuildingTowers动态规划算法用F[i,j,k]表示当前层有i块砖，还剩下j层，可用的砖块数量为k的方案总数动态规划方程：F[i,j,k]=F[i+1,j+1,k-i]+F[i-1,j+1,k-i]边界条件:F[M,H,N]=1,其他为０例三、BuildingTowers容易看出，这个动态规划方程一共涉及了N*M*K个状态，最大约为60*70*2400=10M。如果每个状态用一个double来保存

20、信息，则至少需要80M的内存不论是时间复杂度，还是空间复杂度，都让人难以接受。失败例三、BuildingTowers将规划的顺序作一个反转，有什么好处呢？记忆化因子自顶向下的搜索算法逆向动态规划自底向上的动态规划算法例三、BuildingTowers逆向动态规划的好处在于：1)自顶向下的看问题，有“一览众山小”的开阔