默认下面的

\log

的底数为

2

，

k

为一自然数。

题目解法

看到

N\le 9\times 10^{18}

就可以想到这题可以先打表，找找规律。打表代码没存，就不放了。打出来的表：

TEXT

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

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

CPP

可以发现，令接下来第

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

，我们的表如下所示：

CPP

去掉了

8

，还剩下

10-8=2

。

因为

8

是小于

N

的最大的

2^k

，所以可以把

9

及之后的给去掉：

CPP

再把表扩展开：

CPP

5 5 5 5 5 6 7 8

找到第二项

5

，即是最终答案。

对于其他的

N

同理。

特判：

N\le 2

时，答案是

1

。

代码：

CPP

#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)

。

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

文章操作

题目解法

相关推荐

评论

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