ACWING310. 启示录（数位dp+二分）

启示录（数位dp+二分）"/>

ACWING310. 启示录（数位dp+二分）

古代人认为666是属于魔鬼的数。

不但如此，只要某数字的十进制表示中有三个连续的6，古代人也认为这是个魔鬼的数，比如666,1666,6663,16666,6660666等等。

古代典籍中经常用“第X小的魔鬼的数”来指代这些数，这给研究人员带来了极大的不便。

现在请编写一个程序，可以实现输入X，输出对应的魔鬼数。

输入格式
第一行包含整数T，表示共有T组测试数据。

每组测试数据占一行，包含一个整数X。

输出格式
每组测试数据占一行，输出一个魔鬼数。

数据范围
1≤T≤1000,
1≤X≤5∗107
输入样例：
3
2
3
187
输出样例：
1666
2666
66666

题意：
记忆化数位dp加二分应该是常规写法（记忆化更好写？）
lyd书上介绍的是填充法，明天再补充一下

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;
ll MOD;
ll digit[20];
ll dp[20][10];
ll dfs(ll len,ll if6,ll limit)
{if(len == 0)return if6 == 3;if(!limit && dp[len][if6] != -1)return dp[len][if6];ll up = limit ? digit[len] : 9;ll ans = 0;for(ll i = 0;i <= up;i++){ll sta = 0;if(if6 == 3)sta = 3;else if(if6 == 2 && i == 6)sta = 3;else if(if6 == 1 && i == 6)sta = 2;else if(i == 6)sta = 1;ans += dfs(len - 1,sta,limit && i == up);}return limit ? ans : dp[len][if6] = ans;
}ll solve(ll x)
{ll cnt = 0;while(x){digit[++cnt] = x % 10;x /= 10;}return dfs(cnt,0,1);
}int main()
{memset(dp,-1,sizeof(dp));ll T;scanf("%lld",&T);while(T--){ll x;scanf("%lld",&x);ll l = 1,r = 1e10;ll res = 1;while(l <= r){ll mid = (l + r) >> 1;if(solve(mid) >= x){res = mid;r = mid - 1;}if(solve(mid) < x){l = mid + 1;}}printf("%lld\n",res);}return 0;
}