子问题与原问题........

题意：

有k个坏人k个好人坐成一圈，前k个为好人（编号1~k），后k个为坏人(编号k+1~2k)

这道题起初看以为是道模拟题，因为数据结构课上写过。但是必然超时····到11的时候就卡死了。于是乎找到题解打表过了~~~~

搜资料后发现，运用重新标号，子问题求解。

最初的约瑟夫：将问题变为有n个人 编号为0~n-1，从0开始报数，到m-1时，此人出列。再从下一个开始。求胜利者的编号。

第一个出队的人 必然是 m%n-1，记k=m%n,那此时队的编号是 k,k+1,k+2,.....n-1,0,1.2...k-2

现在重新标号k --> 0  k+1 --> 1  k+2 --> 2  ...  ...  k-2 --> n-2  k-1 --> n-1  变换后就完完全全成为了(n-1)个人报数的子问题。（因为是模拟过程，因此n-1个人的答案必然也是n个人的答案）。若知道n-1个人时胜利者编号为x,那么对应到n个人队中的编号x‘=(x+k)%n.至此递推公式得到，f[1]=0;

POJ 1012 

ans[i] 对应第i次出队人的编号 ans[0]=0;
ans[i]=(ans[i-1]+m-1)%(n-i+1);   (i>1  ,  总人数n=2k 则n-i为第i轮剩余的人数)

优化：

看到很多人对m并不是递增+1，而是m+=k+1  或m+=k+2。 为什么？考虑当最后剩下K+1个人。此时必然K+1为终止点，但是起始位置要看上一轮K+2。K+2可能在K+1的左侧，那么m必然是t*(k+1+1),也可能在右侧，m=t*(k+1),

打表过的，就不贴代码了。

POJ 1012 Joseph 变形约瑟夫环