题解 P1647 【锁】

gcwixsxr · 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 时, 满足要求的数据为：

同样是满足这个规律的,对吧,按照这个规律,可以算出 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;
}