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

传送门

•参考资料

　　[1]:浅梦无痕

　　[2]:Esquecer

　　[3]:My ****

•题意

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

•对博文[1]的理解

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

　　如果 x 不为奇数，那么，执行的过程如下：

1 while(x%2 == 0)
2 {
3     x /= 2;
4     if(n&1)
5         x++;
6     ans += n/2;
7     n -= n/2;
8 }

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

　　①如果 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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 
 5 ll n,x;
 6 int q;
 7 
 8 ll Solve()
 9 {
10     ll ans=0;
11     ll cur=n;
12     while(x%2 == 0)
13     {
14         x /= 2;///x及其之前共有x/2个编号
15         if(cur&1)///如果当前剩余奇数个编号，将最后一个编号放到下一轮出队
16             x++;
17         ans += cur/2;
18         cur -= cur/2;
19     }
20     ans += (x+1)/2;
21     return ans;
22 }
23 int main()
24 {
25     scanf("%lld%d",&n,&q);
26     while(q--)
27     {
28         scanf("%lld",&x);
29         printf("%lld
",Solve());
30     }
31     return 0;
32 }

View Code