UESTC 1689 吉利数字

数位dp加二分，类似的还有HDU 3271 SNIBB #include #include #include #include #include #
2023-12-08 技术

数位dp加二分，类似的还有HDU 3271 SNIBB 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
#define int64 __int64
#define M 100005
#define N 1005
#define inf 1000010
#define mod 1000000009int dig[25] ,x , y;
ll dp[25][25][25];ll Dfs(int index , int six ,int eight , int lim)
{if (six > x || eight > y)return 0;if (!index)return six == x && eight == y;if (!lim && dp[index][six][eight] != -1)return dp[index][six][eight];int i , up = lim ? dig[index] : 9;ll ret = 0;for (i = 0 ; i <= up ; i++){ret += Dfs(index-1 , six+(i==6) , eight+(i==8) , lim&&i==up);}if (!lim)dp[index][six][eight] = ret;return ret;
}ll Solve(ll k)
{int len = 0;while (k){dig[++len] = k%10;k /= 10;}return Dfs(len,0,0,1);
}int main()
{ll l , r;int t = 1 , tcase;scanf("%d",&tcase);while (tcase--){scanf("%lld%lld%d%d",&l,&r,&x,&y);memset(dp , -1 ,sizeof dp);printf("Case #%d:\n",t++);ll lcount = Solve(l-1);ll ans = Solve(r)-lcount;int q;ll ret;scanf("%d",&q);while (q--){ll k;scanf("%lld",&k);if (ans < k)printf("That's too bad!\n");else{ll L = l , R = r , mid;while (L <= R){mid = (L+R)>>1;if (Solve(mid)-lcount >= k){ret = mid;R = mid-1;}elseL = mid+1;}printf("%lld\n",ret);}}}return 0;
}


 

 

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！

推荐阅读