Wannafly挑战赛15 C“出队”（约瑟夫环类问题）

•参考资料

•题意

　　n 个人围成一圈，1,2 报数，报 1 的离队，求编号为 x 的第几次出队；

•对博文[1]的理解

　　第一轮出队的编号一定为奇数，如果 x 为奇数，那么 x 一定在第一轮就出队了，ans = (x+1) / 2；

　　如果 x 不为奇数，那么，执行的过程如下：
 while(x% == )

 {

     x /= ;

     if(n&)

         x++;

     ans += n/;

     n -= n/;

 }
　　下面来解释一下上述代码的作用；

　　①如果 x 为偶数，那么在第一轮出队中，x 及其之前的偶数不出队，共 x/2 个编号；

　　②如果 n 为偶数，那么第一轮出队中共出队 n/2 个编号，还剩下 n/2 个编号，x 为剩下的编号中的第 x/2 个编号；

　　在第二轮出队中，剩下的第一个编号依旧是第一个出队的编号，相当于剩下的 n/2 个编号重复一遍上述①②过程；

　　如果 n 为奇数，那么第一轮出队中共出队 n/2+1 个编号，还剩下 n/2 个编号；

　　但是，这剩下的 n/2 个编号在第二轮出队中，第一个出队的编号不再是第一个编号，而是第二个编号，与上述②过程不同；

　　这该如何处理呢？

　　很好办，在第一轮的出队中，让最后一个出队的编号 n 放到第二轮出队的队首位置，那么第二轮出队的编号中，第一个出对的依旧是第一个编号；

　　其余编号的变化是在之前的基础上+1，接着重复上述①②过程；

•Code

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 ll n,x;

 int q;

 ll Solve()

 {

     ll ans=;

     ll cur=n;

     while(x% == )

     {

         x /= ;///x及其之前共有x/2个编号

         if(cur&)///如果当前剩余奇数个编号，将最后一个编号放到下一轮出队

             x++;

         ans += cur/;

         cur -= cur/;

     }

     ans += (x+)/;

     return ans;

 }

 int main()

 {

     scanf("%lld%d",&n,&q);

     while(q--)

     {

         scanf("%lld",&x);

         printf("%lld\n",Solve());

     }

     return ;

 }

•对博文[2]的理解

　　

　　短小精悍的代码，tql！

　　如果 x 不为奇数，那么 x 肯定不再这一轮中出队，而 x 之前的偶数也不再这一轮中出队；

　　即有 x/2 个编号不在这一轮中出队，那么相当于在这 n 个编号的队尾增加 x/2 个编号， x 变成队尾编号；

　　接着执行上述过程；

•Code

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 ll n,x;

 int q;

 ll Solve()

 {

     while(x% == )

         x=n+x/;///将x/2个编号加入队尾，x变为队尾编号，并判断x是否可以在第一轮中出队

     return x/+;

 }

 int main()

 {

     scanf("%lld%d",&n,&q);

     while(q--)

     {

         scanf("%lld",&x);

         printf("%lld\n",Solve());

     }

     return ;

 }

巴特西

Wannafly挑战赛15 C“出队”（约瑟夫环类问题）

•参考资料

•题意

•对博文[1]的理解

•Code

•对博文[2]的理解

•Code

最新文章

热门文章