题解：P12464 『FCRT / 1 - 1』Seats

· · 题解

默认下面的 \log 的底数为 2，k 为一自然数。

题目解法

看到 N\le 9\times 10^{18} 就可以想到这题可以先打表，找找规律。打表代码没存，就不放了。打出来的表：

1 1 2 2 3 3 3 4 5 5 5 5 5 6 7 8 9 9 9 9 9 9 9 9 9 10 11 12 13 14 15 16 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 18 19 20

第一眼似乎没有规律，但是可以发现每个数字都出现了一次及以上，且单调不减，所以把每个数字出现的次数统计一下（缩表）。

2
2
3
1
5
1
1
1
9
1
1
1
1
1
1
1
17
1
1
1

可以发现，令接下来第 i 个非 1 的数 =x，则后面跟着的 1 的个数为 x-2，与 x 的和为 2^{i-1}（第 1 项例外），总和（缩表前的项数） =2^1+2^2+\dots+2^{i-1}+2=2^i。

接下来就容易一些了。举个例子，N=10 时，首先要求出比 N 小的最大的 2^k： 2^{\lfloor\log(N)\rfloor}=8，这就是前面提到的“总和”。去掉 8，我们的表如下所示：

5
1
1
1
9
1
1
1
1
1
1
1
17
1
1
1

去掉了 8，还剩下 10-8=2。

因为 8 是小于 N 的最大的 2^k，所以可以把 9 及之后的给去掉：

5
1
1
1

再把表扩展开：

5 5 5 5 5 6 7 8

找到第二项 5，即是最终答案。

对于其他的 N 同理。

特判：N\le 2 时，答案是 1。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
int n;
signed main(){
    cin>>n;
    if(n<=2) return printf("1\n"),0;
    int x=log2(n);
    int y=pow(2,x);
    n-=y;
    y/=2;
    if(n<=y+1) cout<<y+1;
    else cout<<y+1+(n-(y+1));
    return 0;
}

时间复杂度 O(\log N)。