2 条题解
-
0
scy的代码（dp:）
#include<bits/stdc++.h> #define LL long long using namespace std; LL f[21][4];//f[i][j]: 由i个数构成的左边(高位)有j个6的数的个数 void init() { f[0][0]=1; f[0][1]=f[0][2]=f[0][3]=0; for(int i=1;i<20;i++) { f[i][0]=9*(f[i-1][0]+f[i-1][1]+f[i-1][2]); f[i][1]=f[i-1][0]; f[i][2]=f[i-1][1]; f[i][3]=f[i-1][3]*10+f[i-1][2]; } } int main() { init(); int T;scanf("%d",&T); while(T--) { int n,m=3; scanf("%d",&n); while(f[m][3]<n) m++;//先确定这个数的位数 for(int i=m,k=0;i;i--)//k记录左边有多少个连续的6 { for(int j=0;j<=9;j++) { LL t=f[i-1][3]; if(j==6 || k>=3)// j==6才有连接作用，k>=3则不需要考虑j的链接作用 for(int l=max(3-k-(j==6),0);l<3;l++) t+=f[i-1][l]; if(t<n) n-=t; else { if(k<3){if(j==6) k++;else k=0;}//k>=3且j不等于6也要保持k==3 printf("%d",j); break; } } } puts(""); } return 0; }hansang的代码(记搜：
#include<bits/stdc++.h> //hansang.Firenze using namespace std; typedef long long LL; const int N=30; LL f[N][2][2], a[N]; LL dfs(int x, int l1, int l2, bool lim){ if(x==0) return 1; if(!lim && f[x][l1][l2]!=-1) return f[x][l1][l2]; int up=(lim)? a[x]: 9; LL ans=0; for(int i=0; i<=up; i++){ if(l2 && l1 && i==6) continue; ans+=dfs(x-1, (i==6), l1, lim && (i==up)); } if(!lim) f[x][l1][l2]=ans; return ans; } LL check(LL x){ int len=0; while(x>0) a[++len]=x%10, x/=10; return dfs(len, 0, 0, 1); } int main(){ //freopen("a.in", "r", stdin); for(int i=1; i<=25; i++) for(int j=0; j<=1; j++) for(int k=0; k<=1; k++) f[i][j][k]=-1; int T; scanf("%d", &T); while(T--){ LL n; scanf("%lld", &n); LL l=1, r=(LL)1e18, p; while(l<=r){ LL mid=(l+r)/2, x=check(mid); if(mid-x+1>=n) r=mid-1, p=mid; else l=mid+1; } printf("%lld\n", p); } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:56:36
scy的代码（dp:
#include<bits/stdc++.h> #define LL long long using namespace std; LL f[21][4];//f[i][j]: 由i个数构成的左边(高位)有j个6的数的个数 void init() { f[0][0]=1; f[0][1]=f[0][2]=f[0][3]=0; for(int i=1;i<20;i++) { f[i][0]=9*(f[i-1][0]+f[i-1][1]+f[i-1][2]); f[i][1]=f[i-1][0]; f[i][2]=f[i-1][1]; f[i][3]=f[i-1][3]*10+f[i-1][2]; } } int main() { init(); int T;scanf("%d",&T); while(T--) { int n,m=3; scanf("%d",&n); while(f[m][3]<n) m++;//先确定这个数的位数 for(int i=m,k=0;i;i--) //k记录左边有多少个连续的6 { for(int j=0;j<=9;j++) { LL t=f[i-1][3]; if(j==6 || k>=3)// j==6才有连接作用，k>=3则不需要考虑j的链接作用 for(int l=max(3-k-(j==6),0);l<3;l++) t+=f[i-1][l]; if(t<n) n-=t; else { if(k<3){if(j==6) k++;else k=0;}//k>=3且j不等于6也要保持k==3 printf("%d",j); break; } } } puts(""); } return 0; }
hansang的代码(记搜：#include<bits/stdc++.h> //hansang.Firenze using namespace std; typedef long long LL; const int N=30; LL f[N][2][2], a[N]; LL dfs(int x, int l1, int l2, bool lim){ if(x==0) return 1; if(!lim && f[x][l1][l2]!=-1) return f[x][l1][l2]; int up=(lim)? a[x]: 9; LL ans=0; for(int i=0; i<=up; i++){ if(l2 && l1 && i==6) continue; ans+=dfs(x-1, (i==6), l1, lim && (i==up)); } if(!lim) f[x][l1][l2]=ans; return ans; } LL check(LL x){ int len=0; while(x>0) a[++len]=x%10, x/=10; return dfs(len, 0, 0, 1); } int main(){ //freopen("a.in", "r", stdin); for(int i=1; i<=25; i++) for(int j=0; j<=1; j++) for(int k=0; k<=1; k++) f[i][j][k]=-1; int T; scanf("%d", &T); while(T--){ LL n; scanf("%lld", &n); LL l=1, r=(LL)1e18, p; while(l<=r){ LL mid=(l+r)/2, x=check(mid); if(mid-x+1>=n) r=mid-1, p=mid; else l=mid+1; } printf("%lld\n", p); } return 0; }
- 1
