约瑟夫环-递推
约瑟夫环问题:有n个人围成一个圈,标号分别为0~n-1,从第一个人开始从1进行数数,数到k的人淘汰出圈外,求最后一个被淘汰的人的编号。 之前比较暴力的解法就是用线性结构模拟环,模拟淘汰的过程,复杂度为O(NK) 利用递推的思想我们可以实现O(N)的复杂度。 推理的思路如下: ...
约瑟夫环问题:有n个人围成一个圈,标号分别为0~n-1,从第一个人开始从1进行数数,数到k的人淘汰出圈外,求最后一个被淘汰的人的编号。 之前比较暴力的解法就是用线性结构模拟环,模拟淘汰的过程,复杂度为O(NK) 利用递推的思想我们可以实现O(N)的复杂度。 推理的思路如下: ...
A题题意:有一长度为N的连续序列,A与B交替从序列中取一段连续序列,每次取的序列长度为1-K,当某个人进行选择时,序列为空,则另一人获得胜利,A先进行选择,输入获胜者。 样例: Input Output 1 1 A 9 3 A ...
新的路开始了