[公告][讨论]算法问题讨论交流帖

本帖在大年三十前有效（时间可能会向后延迟，试情况定）
为了增加大家的学习讨论氛围，同时使大家在新春佳节时能有更多收获特开此帖
。
大家可以在本帖中提出算法问题（其它问题恕不讨论回答），我将尽我所能，与
大家讨论，帮助解决。既是对我算法学习的巩固与检验，又是对大家的帮助提高
。
提出的算法可以包括但不局限于以下范围(范围尽量在NOI范围内):
枚举
贪心
递归
递推
高精度计算
动态规划(不包括状态压缩DP)：
  较底难度递推
  较低难度记忆化搜索
搜索：
  广度优先搜索：
    普通广度优先搜索
    双向广度优先搜索
  深度优先搜索
  迭代加深搜索
程序优化相关:
  优化时间效率:
    减枝等
  优化空间效率
数据结构相关(不包括图,数据结构尽量不用链表方式):
  排序
提出的算法中请不要涉及过深,过高难度的,最好包括在以上方面.
请不要提供您的程序让我们改错,如果您思考过这道题,请您提供您的思考过程和
思路
我不是高手,技术并不高超,因此请不要故意刁难我,也不要提出无意义的问题(例
如计算10000000!的精确数值)
提出的算法中请不要包括特别基础的算法,因为那样的算法几乎包括在所有的语
言书籍和算法书籍中:
如:
  三塔问题
  约瑟环问题
  冒泡排序
  选择排序
等,但大数据等除外(例如数据规模为1000000的三塔问题)
请不要直接将作业提出,否则将直接删帖
请不要直接将ACM英文题拿出,最好提供中文翻译
提出的问题我们会提供算法描述,但是不保证提供代码(尤其是对于类似 拱猪分
值计算 等算法性较低只是实现较烦琐的题).因为算法是灵魂,给出了算法,程序
很容易实现
  
本帖不保证您的问题一定被解决，但我们会尽力，难题将会与大家一同讨论。欢
迎大家积极讨论。

[[it] 本帖最后由 卧龙孔明 于 2008-2-3 08:55 编辑 [/it]]
----------------解决方案--------------------------------------------------------
顶一下，想问一下最大流的最短增广路算法，那个很难懂的东西。。。
你怎么理解它的？
----------------解决方案--------------------------------------------------------
ls来拆台了
您说的那些算法我不了解,我会放在帖顶,请其他了解那个算法的人来解答,同时我会在今晚或明晚错算法书籍中查阅此算法的资料,尽力解答

提问的算法请尽量包含在以上列出的表中
----------------解决方案--------------------------------------------------------
你所面向的对象比较正常，而偶就故意弄了一个专帮习题作业那些超简单题目的
----------------解决方案--------------------------------------------------------
网络最大流问题是我队友研究的比较多，我只少许看了一下，增广路径定理和最大流最小割定理。根据增广路径定理其实很容易就能用dfs或者bfs写出一个求最大流的算法，但效率并不高，这时候有人告诉你，这样这样这样写效率就会高了――最短增广路算法，至于为什么效率高了，可以看复杂性证明，反正我是没看，我关心的是这个算法是怎么被想出来的，可惜没人能告诉我。
----------------解决方案--------------------------------------------------------
昨天晚上看了一晚上<算法艺术>的网络流部分,结果我发现那属于图论的一部分,可是我对图论还没有进一步学习(只是在2006年8月看过几个基本的图算法),因此在第一次发帖中就将图放在外面.
网络流很神奇啊,复杂度这么小,同时可以解决许多搜索严重超时的问题.日后重新进一步学习图论后一定好好看看这部分
----------------解决方案--------------------------------------------------------
好神奇啊
----------------解决方案--------------------------------------------------------
约瑟夫环常规解法时间复杂度和空间复杂太让人受不了了，有没有更简单的算法？
----------------解决方案--------------------------------------------------------
有更好的解法
以下转载内容关于约瑟夫问题:

约瑟夫问题的数学解法
对于约瑟夫问题，无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)
当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。
问题描述：n个人(编号1~n)，从1开始报数，报到m的退出，剩下的人继续从1开始报数. 求胜利者的编号
我们知道第一个人(编号一定是(m-1) mod n+1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环
(以编号为k=m mod n+1的人开始):
k k+1 k+2 ... n-1, n, 1, 2, ... k-2
并且从k开始报1

现在我们把他们的编号做一下转换：
k   --> 1
k+1   --> 2
k+2   --> 3
...
...
k-2   --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗!

变回去的公式，x' =(x+k-2) mod n+1
            =(x+m mod n-1) mod n+1
            =(x+m-1) mod n+1
如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的 情况 ---- 这显然就是一个倒推问题！

思路出来了，下面写递推公式：

令f[i]表示i个人玩游戏报m退出最后胜利者的编号

递推公式
f[1]=1;
f[i]=(f[i-1]+m-1) mod i+1; (i>1)

p.s: f[i]=(f[i-1]+k-2) mod i+1 也可以，但先要算出k:=m mod i+1
这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了
----------------解决方案--------------------------------------------------------
大概意思懂了，具体的数学推导还没演算，明天早上起床后再演算一下。强烈鄙视教科书和中国教育。
----------------解决方案--------------------------------------------------------