题解：P13650 [NOISG 2016] UnluckyFloors

_0X7F_ · 2026-01-26 20:34:02 · 题解

P13650 [NOISG 2016] UnluckyFloors

题目传送门。\ 提交记录。

题目思路

个人感觉不是很难，是一道数位 DP 加二分的题目。

首先解决第一种情况，就是用 X 减去含有四或十三的数，其实就是求 X 到 1 中有多少数没有四或十三，数位 DP 解决即可。

接着就是第二种情况，二分出常规数字刚好为 X 的情况。注意二分 R 边界不能为 X，因为幸运数字从四开始就都比常规数字大了。

数位 DP 过程：

一，判断判断边界条件。当填数完毕时，返回 1。\ 二，记忆化搜索。当当前状态已被访问，则记忆化搜索。\ 三，循环每一种数字的情况，当当前数位为四或有连续的数位为十三时就跳过。

AC CODE:

#include<bits/stdc++.h>
using namespace std;
int a[17];
long long dp[17][10]; 
long long dfs(int address,bool limit,int pre){
    if(address==-1)return 1;
    if(!limit&&dp[address][pre]!=-1)return dp[address][pre];//记忆化搜索 
    int up=(limit==1)?a[address]:9;//上限 
    long long ans=0;
    for(int i=0;i<=up;i++){
        if(i==4)continue;
        if(pre==1&&i==3)continue;
        ans+=dfs(address-1,limit&&(i==up),i);//下一位数字 
    }
    if(!limit)return dp[address][pre]=ans;//记忆化 
    else return ans;
}
long long sol(long long x){
    int cnt=0;
    while(x>0){
        a[cnt++]=x%10;
        x/=10;
    }
    return dfs(cnt-1,true,0)-1;
}
bool is(long long x){
    string xx=to_string(x);
    if(xx.find("4")!=-1||xx.find("13")!=-1)return false;
    return true;
}
long long two(long long x){
    long long l=1,r=5e18;
    while(l<r){
        long long mid=(l+r)/2;
        if(sol(mid)<x)l=mid+1;
        else r=mid;
    }
    return r;
}
int main(){
    int t;
    cin>>t;
    memset(dp,-1,sizeof(dp));
    while(t--){
        long long op,X;
        cin>>op>>X;
        if(op==1){
            if(!is(X))cout<<"-1\n";
            else cout<<sol(X)<<"\n";
        }else{
            cout<<two(X)<<"\n";
        }
    }
    return 0;
}