自动搬运

查看原文

来自洛谷，原作者为

	gcwixsxr lxyddd

搬运于2025-08-24 21:27:29，当前版本为作者最后更新于2020-08-19 22:58:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本蒟蒻做这道题时,还只有一个题解,于是本蒟蒻也想分享一下自己的方法。

首先找一下规律:(以下01串均为二进制表示)

当 $n$ 为 $1$ 时, 满足要求的数据为 $0,1$。

当 $n$ 为 $2$ 时, 满足要求的数据为 $00,01,11,10$。

当 $n$ 为 $3$ 时, 满足要求的数据为 $000,001,011,010,110,100,101,111$。

可以发现,每 $2^n$ 个满足要求的数据中,从第 $2^{n-1}+2$ 个到第 $2^n$ 个数的数值分别等于第 $1$ 个到第$2^{n-1}-1$ 个数的数值加上 $2^{n-1}$ ,即 $num_{i+2^{n-1}+1}=num_{i}+2^{n-1}$ ,其中 $i \in[1, 2^{n-1}-1]$,而第 $2^{n-1}+1$ 个数的数值等于第 $2^{n-1}$ 个数加上 $2^{n-1}$ ,即 $num_{2^{n-1}+1}=num_{2^{n-1}}+2^{n-1}$ 。

举个栗子,当 $n$ 为 $3$ 时,如下图,后 $3$ 个分别等于前 $3$ 个的数值加上 $4$ ,第 $5$ 个的值等于第 $4$ 个加 $4$;

还不信?再看看 $n$ 为 $4$ 的时候:

当 $n$ 为 $4$ 时, 满足要求的数据为： $0000,0001,0011,0010,0110,0100,0101,0111$,$1111,1000,1001,1011,1010,1110,1100,1101$

同样是满足这个规律的,对吧,按照这个规律,可以算出 $1$ 到 $2^n$ 中的任何一个数。

按照此规律,能算出任何排名的数的函数如下。

long long work(long long k){//求出排名第k的数的数值
	if(k==1)return 0LL;//如果是第一项,返回0
	if(k==2)return 1LL;//如果是第二项,返回1
	int t=0;long long kl=1;
	while(kl<k){
		kl<<=1;
		t++;
	}
	t--;kl>>=1;//算出小于k的最大2的次幂
	if(k-kl==1)return kl+work(k-1); 
	else return kl+work(k-kl-1);//这两句对应上方规律中的两个递推公式
}

那么,算出排名第 $k$ 的数有什么用呢?

这个时候要用到分治的思想了:

我们先看张图

假设我们要求前 $14$ 个中的最大值,即求 $\max(a_i),i\in[1,14]$,由于后 $8$ 个一定大于前 $8$ 个,又因为$a_{i}=a_{i-9}+8,i\in[10,14]$ ,并且 $a_9=a_8+8$ ,所以,问题就被转化成了求 $\max(a_i)+8,i\in[1,5]\cup\{8\}$,即求前 $5$ 个和第 $8$ 个的的最大值,因此上述的问题被转化到了下图中:

求$\max(a_i)+8,i\in[1,5]\cup\{8\}$,第 $5$ 个一定大于前 $4$ 个,因此问题又被转化,即求$\max(a_5,a_8)+8$,(其实这个时候可以直接调用 $\texttt{work}$ 函数,但也可以继续递推下去),继续转化,$a_8=a_3+4,a_5=a_4+4$,问题变为求$\max(a_3,a_4)+12$.

来到最后一步,$a_3=a_2+2,a_4=a_1+2$,即求$\max(a_1,a_2)+14=15$,这时就可以输出答案辣!

像这样大事化小,小事化了,不就是分治吗?

求解函数;

long long solve(long long k){
	if(k==1)return 0LL;//返回1
	if(k==2)return 1LL;//返回0
	int t=0;long long kl=1;
	while(kl<k){
		kl<<=1;
		t++;
	}
	t--;kl>>=1;
	if(k-kl==1)return kl+work(k-1);//如果是2次幂+1的形式,最大的就是自身
	else return (long long)kl+max(solve(k-kl-1),work(kl));//特判一下中间特殊的一项
}

最后是$AC$代码:

#include<bits/stdc++.h>
using namespace std;
int n;
long long k;
long long work(long long k){
	if(k==1)return 0LL;
	if(k==2)return 1LL;
	int t=0;long long kl=1;
	while(kl<k){
		kl<<=1;
		t++;
	}
	t--;kl>>=1;
	if(k-kl==1)return kl+work(k-1);
	else return kl+work(k-kl-1);
}
long long solve(long long k){
	if(k==1)return 0LL;
	if(k==2)return 1LL;
	int t=0;long long kl=1;
	while(kl<k){
		kl<<=1;
		t++;
	}
	t--;kl>>=1;
	if(k-kl==1)return kl+work(k-1);
	else return (long long)kl+max(solve(k-kl-1),work(kl));
}
void write(long long x, int t){
	if(t-1) write(x>>1,t-1);
	putchar(x&1?'1':'0');
}
signed main(){
	scanf("%d%lld",&n,&k);
	write(solve(k),n);
	return 0;
}