本文共 1234 字，大约阅读时间需要 4 分钟。
题意：给定n，输出第n大包含666的数字。
分析：dp[i][j][k][l]表示 长度为i,当前位是否是6，前一位是否6，是否已经包含666，表示的数量，再用二分找出第n大的这样的数字。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef pair PII;typedef long long ll;#define lson l,m,rt<<1#define pi acos(-1.0)#define rson m+1,r,rt<<11#define All 1,N,1#define read freopen("in.txt", "r", stdin)const ll INFll =0xfffffffffLL;const int INF= 0x7ffffff;const int mod =1000000007;ll dp[64][2][2][2],n;int bit[64];ll dfs(int i,int j,int k,int l,int e){ if(i==0) return l; if(!e&&dp[i][j][k][l]!=-1) return dp[i][j][k][l]; int u=e?bit[i]:9; ll num=0; for(int v=0;v<=u;++v){ if(l==1) num+=dfs(i-1,v==6,j,1,(e&&v==u)); else num+=dfs(i-1,v==6,j,j&&k&&v==6,(e&&v==u)); } return e?num:dp[i][j][k][l]=num;}ll getnum(ll x){ int len=0; while(x){ bit[++len]=x%10; x/=10; } return dfs(len,0,0,0,1);}int main(){ memset(dp,-1,sizeof(dp)); int t; scanf("%d",&t); ll n; while(t--){ scanf("%I64d",&n); ll l=1,r=INFll,mid; while(l<=r){ mid=(l+r)>>1; if(getnum(mid)
转载于:https://www.cnblogs.com/zsf123/p/4679260.html