Codeforces 101864A 打表

传送门:题目

题意：

大概意思就是总共有N个犯人，形成一个序列[1-n]，有一个犯人在第X位，然后警察们制定了一个规则，让[1-L？]犯人出队，围成一个约瑟夫环，警察们要杀N-1个人，只允许L人中存活一人，杀人规则是：
让[1-L？]个犯人围城一个圈，然后留一人，杀一人。比如，下图：

留下一号选手，击杀二号选手。
留下三号选手，击杀四号选手。
留下五号选手，击杀六号选手。
留下七号选手，击杀八号选手。
留下一号选手，击杀三号选手。
留下五号选手，击杀七号选手。
留下一号选手，击杀五号选手。
留下一号选手，咦？好像没人可以杀了。我们数一数，上面正好七行，正好满足题意，留下一个幸存者，恭喜一号选手获胜。

不难发现，这正是著名的约瑟夫环问题。而这正好是一个特殊的约瑟夫环：Josephus(n,2)。为什么Josephus(n,2)特殊，稍后再讲。我们继续说题意。

上面L打了个问号，因为题目的意思是，上面区间的右界是[L,N]的任何一个数。也就是说：

第一种情况：[1-L]出队，只允许存活一人
第二种情况：[1-L+1]出队，只允许存活一人
等等
第N-L+1种情况：[1-N]出队，只允许存活一人

没出队的肯定活着
好了，题目问：所有出队的情况，X号犯人，能存活的概率。
其中： 1≤X,L,N≤1015 1 ≤ X , L , N ≤ 10 15

题解：

所有出队的情况，N-L+1做分母
分子我们考虑两种情况，一种是X号犯人根本没出队，肯定存活。另一种就是本问题的核心了。如果没有那个神奇的 1015 10 15 ,我们直接写个Josephus(i,2)函数，返回幸存者编号，如果是X，分子++。显然,这道题没有这么简单。完全没有思路，先打个表再说：我们输出：i ∈ ∈ [1,100]，Josephus（i，2）的返回值。

打表代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int main(void){
int m=2, ans;
for(int i=1;i<=100;i++){
ans=0;
for(int j=2;j<=i;j++)
ans=(ans+m)%j;//约瑟夫出圈公式
cout<<ans+1<<" ";
}
cout<<endl;
return 0;
}

得到下图结果：

看着比较乱，我们不妨换一下行：

1
1 3
1 3 5 7
1 3 5 7 9 11 13 15
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
……

我们发现，每当Josephus(i，2)中，i为 2k,k∈[0,1,2,3,......] 2 k , k ∈ [ 0 , 1 , 2 , 3 , . . . . . . ] 时，Josephus(i，2)==1,然后开始奇数递增。
一个很神奇的事情发生了，比如说现在X==5，那么X在每一行只能存活1次，所以我们只需要计算[X，N]横跨了那几行，如果是完全横跨，分子++，如果一行中只有部分在[X，N]内，判断一下X值，是不是在区间内就行了，一个很巧妙的办法，直接把X/2，为何巧妙？

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long//作者比较懒，直接把所有int换成long long
void solve(int i)
{
int X, L, N;
scanf("%I64d%I64d%I64d", &X, &L, &N);
int ans = max(X - L, 0ll);
if (X & 1ll) //x是奇数
for (int Y = 1 ; Y + X / 2 <= N ; Y <<= 1)
{//X是1，3，5，7
if (Y + X / 2 < L || Y <= X / 2)//那么X/2就是0，1，2，3，直接就是X的在行的第几位了。
continue;
++ans;
}
int P = ans, Q = N - L + 1;
int g = __gcd(P, Q);//不要忘记化简分子和分母啊，__gcd是algorithm中的一个函数，很方便
P /= g;
Q /= g;
cout << "Case " << i << ": " << P << "/" << Q << "n";
}
signed main()
{//不能是long long main啊，所以我们就用signed吧，反正signed==int
int T;
scanf("%I64d", &T);
for (int i = 1 ; i <= T ; ++i)
solve(i);
}

最后

以上就是默默项链最近收集整理的关于Codeforces 101864A 打表的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。