题解 | #萌萌的好数#

赛时看到D题过的比C题还多，觉得很诧异？？原来是我把D想复杂了……

看到题解区很少数位 做法，我来写一个 版本的二分+数位 。

首先找到比一个数小的“好数”个数，就是改改数位 板子，用 表示第 位数位和为 的方案数，所以只需要找到最小的这个数即可。由于一定满足单调性，所以想到二分。（为什么要找到最小的，因为对于 和 来说，比其小的“好数”都是 ，所以找最小是为了消除那些本身不是“好数”的数的影响）。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int N=2e5+5;
const int mod=998244353;
int dp[20][200],num[20];
int dfs(int pos,int sum,int lim)
{
    if(pos<1) 
    {
        if(sum%3==0) return 0;
        else return 1;
    }
    if(!lim&&dp[pos][sum]!=-1) return dp[pos][sum];
    int top=lim?num[pos]:9;
    int ans=0;
    for(int i=0;i<=top;i++)
    {
        if(pos==1&&i==3) continue; 
        ans+=dfs(pos-1,sum+i,lim&&i==top);
    }
    if(!lim) dp[pos][sum]=ans;
    return ans;
}
int solve(int x)
{
    int l=1,r=1e18;
    int ans=1e18;
    while(l<=r)
    {
        memset(dp,-1,sizeof dp);
        memset(num,0,sizeof num);
        int t=0,mid=(l+r)/2,p=mid;
        while(p)
        {
            num[++t]=p%10;
            p/=10;
        }
        int cnt=dfs(t,0,1);
        if(cnt>=x) ans=min(ans,mid),r=mid-1;
        else l=mid+1;
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        cout<<solve(n)<<endl;
    }
    return 0;
}