[ABC115D] Christmas

Hyc_ · 2023-04-30 19:21:26 · 题解

由题中的式子可推出：str_{50} 的长度为 4503599627370493，所以此题无法暴力。

由递推式得：str_i = B+str_{i-1}+P+str_{i-1}+B。

所以我们可以从 str_n 到 str_1 依次尝试，若 str_i 完全在区间 1\sim x 内，就加上 str_i 中 P 的数量，然后返回，若部分不在就递归尝试 str_{i-1}，若完全不在就直接返回。

时间复杂度 O(n\log_2n)。

注意：

• 区间 l=r 时直接返回。
• 区间中点一定为 P 且不会被更小区间包含所以区间不被完全包含当区间中点被包含时答案要加一。
• 不开long long见祖宗。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,x,ans;
struct node{ll h,b;}a[52];
//a[i].h为str[i]的长度
//a[i].b为str[i]中'P'的数量
ll find(ll s){//找长度为s的str中有几个'P'
    for(int i=0;i<=n;i++)
        if(a[i].h==s)
            return a[i].b;
    return 0;
}
void dfs(ll l,ll r){
    ll mid=(l+r)>>1;
    if(l>x)return;//左端点比x大，直接返回
    if(r<=x){//若l~r在1~x内一定是一个完整的str，停止向下递归
        ans+=find(r-l+1);
        return;
    }
    if(mid<=x)ans++;//此位置在str[i]的正中间一定为'P'，且不会被str[i-1]包含
    if(l==r)return;//考试时没写这行挂了25分TLE
    dfs(l+1,mid-1);//搜左侧的str[i-1]
    dfs(mid+1,r-1);//搜右侧的str[i-1]
} 
int main(){
    scanf("%lld%lld",&n,&x);
    a[0].h=a[0].b=1;
    for(int i=1;i<=n;i++){
        a[i].h=a[i-1].h*2+3;
        a[i].b=a[i-1].b*2+1;
    }//预处理str[i]的长度及其中'P'的数量
    dfs(1,a[n].h);
    printf("%lld\n",ans); 
    return 0;
}

AtCoder 的 AC 记录。