思路:二分+数位DP,二分没什么好说的,主要是数位DP,我一开始状态是设计成dp[N][100],表示i位,后两位为j,这样是会T的。。而其实第二维,只要开3就够了,表示末尾连续的6的个数,因为超过3个就不用转移了
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N = 15; int t; ll n; int bit[N], bn; void get(ll x) { bn = 0; while (x) { bit[bn++] = x % 10; x /= 10; } for (int i = 0; i < bn / 2; i++) swap(bit[i], bit[bn - i - 1]); } ll dp[N][4]; ll solve(ll x) { get(x); memset(dp, 0, sizeof(dp)); int pre = 0, flag = 0; for (int i = 0; i < bn; i++) { for (int j = 0; j < 3; j++) { for (int x = 0; x < 10; x++) { if (x == 6) dp[i + 1][j + 1] += dp[i][j]; else dp[i + 1][0] += dp[i][j]; } } if (flag) continue; for (int x = 0; x < bit[i]; x++) { if (x == 6) dp[i + 1][pre + 1]++; else dp[i + 1][0]++; } if (pre == 2 && bit[i] == 6) flag = 1; if (bit[i] == 6) pre++; else pre = 0; } ll ans = x + 1; for (int j = 0; j < 3; j++) ans -= dp[bn][j]; ans -= !flag; return ans; } int main() { scanf("%d", &t); while (t--) { scanf("%lld", &n); ll l = 666LL, r = 66650000000LL; while (l < r) { ll mid = (l + r) / 2; ll tmp = solve(mid); if (solve(mid) >= n) r = mid; else l = mid + 1; } printf("%lld\n", l); } return 0; }