hdu3089 Josephus again|快速约瑟夫环

题目链接：戳我

貌似是高一昨天的考试题T2？？？？？感觉挺好玩的就搞了搞qwqwq 其实是HDU上面的题啦。。。。

对于普通的约瑟夫问题，大概是n个人围成一个环，从1开始报数，数到k，那个人出队，最后留下来一个人的时候他就是胜利者，问最后胜利者是谁。

这个一般我们都用递归或者递推搞，设\(f[n]\)表示n个人的时候最后的胜利者的编号。（如果从0开始编的话），显然有\(f[1]=0\)。递推式子为\(f[i]=(f[i-1]+k)\mod i\)

但是显然O(n)的递推对于这道题来说时间复杂度还是有点高。但是之后我们发现，递推的时候，如果\(f[i-1]+k\)不超过i的话，我们可以一次多加几个，这样的话i就不需要一次加一这样转移了。

所以有（ans表示f[i]）——当\(ans+k\times m<i+k-1\)的时候，我们可以一次性把这个范围内的k都加上（\(k<\frac{i-ans-1}{m-1}\)）

其实还有一点小细节。。比如说加超了怎么办以及k=1的情况不能再除了，大家自己思考思考或者参考一下代码。

最后不要忘了+1。

代码如下：

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define MAXN 100010

using namespace std;

long long n,k;

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("ce.in","r",stdin);

    #endif

    while(scanf("%lld%lld",&n,&k)!=EOF)

    {

        if(k==1)

            {printf("%lld\n",n);continue;}

        long long i=2,ans=0;

        while(i<=n)

        {

            if(ans+2*k<i+k-1)

            {

                long long cur_ans=(i-ans-1)/(k-1);

                if((i-ans-1)%(k-1)==0) cur_ans--;

                if(i+cur_ans>n) {ans=(ans+(n-i+1)*k)%n; break;}

                i+=cur_ans;

                ans=(ans+cur_ans*k)%i;

            }

            else

                ans=(ans+k)%i,i++;

        }

        printf("%lld\n",ans+1);

    }

    return 0;

}

巴特西

hdu3089 Josephus again|快速约瑟夫环

题目链接：戳我

最新文章

热门文章