Power Crisis

这道题被严重恶意评分了，实际应该是绿题。

因为其实我们只需要模拟即可。这里我们引入一种新的东西：约瑟夫环。

它能直接告诉你约瑟夫问题中最后一个存活下来的人是谁。（不过下标是从0开始的，实际使用的时候需要+1）

如果有n个人，每次报到m的时候出列，那么令f[i]表示有i个人的时候最后存活的人的下标，那么有f[i+1] = (f[i] + m) % i,其中f[0] = 0;

怎么推的呢？对于一个序列，在长度相同的时候，获胜的人应该是固定的，我们假设现在报到m的人出列了，下一个人（m+1）成为了队首，其实相当于所有人往前移动了m位.那么倒着退回去，我们也就能知道其实获胜的人相对应向后移了m位，不过因为人数在增加，所以我们要每次%i。

对于这道题，因为1已经出去了，所以我们要求的就是n-1的约瑟夫环的最小m，使得f[n-1] = 11，这样我们模拟即可。

看一下代码。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<set>

#include<queue>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const int M = ;

const int INF = ;

int read()

{

    int ans = ,op = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

    if(ch == '-') op = -;

    ch = getchar();

    }

    while(ch >= '' && ch <= '')

    {

    ans *= ;

    ans += ch - '';

    ch = getchar();

    }

    return ans * op;

}

int n;

int main()

{

   while()

   {

      n = read();

      if(!n) break;

      rep(i,,n-)

      {

     int k = ;

     rep(j,,n-) k = (k + i) % j;

     if(k == )

     {

        printf("%d\n",i);

        break;

     }

      }

   }

   return ;

}

巴特西

Power Crisis

最新文章

热门文章