{"id":20,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-09-08-%e6%95%b0%e4%bd%8ddp%e4%ba%8c%e5%88%86\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-09-08-%e6%95%b0%e4%bd%8ddp%e4%ba%8c%e5%88%86","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-09-08-%e6%95%b0%e4%bd%8ddp%e4%ba%8c%e5%88%86\/","title":{"rendered":"2020-09-08 \u6570\u4f4dDP+\u4e8c\u5206"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

http:\/\/icpc.upc.edu.cn\/problem.php?cid=2573&pid=6<\/a><\/p>\n

<\/a>\u9898\u76ee\u63cf\u8ff0<\/h6>\n

Tom is very interested in number problem. Nowadays he is thinking of a problem about A-number and B-number.<\/p>\n

A-number is a positive integer whose decimal form contains 7 or it can be divided by 7. We can write down the first 10 A-number ( a[i] is the ith A-number)<\/p>\n

{a[1]=7,a[2]=14,a[3]=17,a[4]=21,a[5]=27,a[6]=28,a[7]=35,a[8]=37,a[9]=42,a[10]=47};<\/p>\n

B-number is Sub-sequence of A-number which contains all A-number but a[k] ( that k is a A-number.) Like 35, is the 7th A-number and 7 is also an A-number so the 35 ( a[7] ) is not a B-number. We also can write down the first 10 B-number.<\/p>\n

{b[1]=7,b[2]=14,b[3]=17,b[4]=21,b[5]=27,b[6]=28,b[7]=37,b[8]=42,b[9]=47,b[10]=49};<\/p>\n

Now Given an integer N, please output the Nth B-number.<\/p>\n

<\/a>\u8f93\u5165<\/h6>\n

The input consists of multiple test cases.<\/p>\n

For each test case, there will be a positive integer N as the description.<\/p>\n

<\/a>\u8f93\u51fa<\/h6>\n

For each test case, output an integer indicating the Nth B-number.<\/p>\n

You can assume the result will be no more then 2^63-1.<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h6>\n
1\n7\n100\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h6>\n
7\n37\n470\n<\/code><\/pre>\n
\u6570\u4f4dDP+\u4e8c\u5206\u67e5\u627e
 https:\/\/www.cnblogs.com\/shinecheng\/p\/3601235.html<\/a>
 https:\/\/blog.csdn.net\/weixin_33827965\/article\/details\/93230896<\/a><\/p>\n
#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> unsigned<\/span> long<\/span> long<\/span> ll;<\/span> \/\/\/2^63-1 \u5efa\u8bae\u7528unsigned long long <\/span>\nll newx;<\/span>\nll number[<\/span>1005<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nll dp[<\/span>1005<\/span>]<\/span>[<\/span>1005<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nll power[<\/span>300<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\ninline<\/span> ll dfs<\/span>(<\/span>ll i,<\/span>ll mod,<\/span>int<\/span> lim)<\/span> \/\/\/lim\u4e3a\u6807\u8bb0\u662f\u5426\u6709\u4e0a\u9650<\/span>\n{<\/span>\n    if<\/span>(<\/span>i==<\/span>0<\/span>)<\/span>\n        return<\/span> mod==<\/span>0<\/span>;<\/span>\n    if<\/span>(<\/span>!<\/span>lim&&<\/span>~<\/span>dp[<\/span>i]<\/span>[<\/span>mod]<\/span>)<\/span>  \/\/\/ ~(-1)=0<\/span>\n        return<\/span> dp[<\/span>i]<\/span>[<\/span>mod]<\/span>;<\/span>\n    int<\/span> end1=<\/span>lim?<\/span>number[<\/span>i]<\/span>:<\/span>9<\/span>;<\/span>\n    ll ans=<\/span>0<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> j=<\/span>0<\/span>;<\/span>j<=<\/span>end1;<\/span>j++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>j!=<\/span>7<\/span>)<\/span>\n            ans+<\/span>=<\/span>dfs<\/span>(<\/span>i-<\/span>1<\/span>,<\/span>(<\/span>mod-<\/span>(<\/span>j*<\/span>power[<\/span>i-<\/span>1<\/span>]<\/span>)<\/span>%<\/span>7<\/span>+<\/span>7<\/span>)<\/span>%<\/span>7<\/span>,<\/span>lim&&<\/span>j==<\/span>end1)<\/span>;<\/span>  \/\/\/\u53d6\u4f59\u4e3a7\u7684\u60c5\u51b5<\/span>\n        else<\/span> if<\/span>(<\/span>j==<\/span>7<\/span>)<\/span>\n            ans+<\/span>=<\/span>(<\/span>lim&&<\/span>j==<\/span>end1)<\/span>?<\/span>(<\/span>newx%<\/span>power[<\/span>i-<\/span>1<\/span>]<\/span>+<\/span>1<\/span>)<\/span>:<\/span>power[<\/span>i-<\/span>1<\/span>]<\/span>;<\/span> \/\/\/\u9996\u4f4d\u4e3a7\u7684\u60c5\u51b5<\/span>\n    }<\/span>\n    if<\/span>(<\/span>!<\/span>lim)<\/span> \/\/\/\u6ca1\u6709\u9650\u5236<\/span>\n        dp[<\/span>i]<\/span>[<\/span>mod]<\/span>=<\/span>ans;<\/span>\n    return<\/span> ans;<\/span>\n}<\/span>\nll js<\/span>(<\/span>ll p)<\/span>\n{<\/span>\n    newx=<\/span>p;<\/span>\n    if<\/span>(<\/span>p==<\/span>0<\/span>)<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    int<\/span> k=<\/span>0<\/span>;<\/span>\n    while<\/span>(<\/span>p!=<\/span>0<\/span>)<\/span>\n    {<\/span>\n        number[<\/span>++<\/span>k]<\/span>=<\/span>p%<\/span>10<\/span>;<\/span>\n        p=<\/span>p\/<\/span>10<\/span>;<\/span>\n    }<\/span>\n    return<\/span> dfs<\/span>(<\/span>k,<\/span>0<\/span>,<\/span>1<\/span>)<\/span>-<\/span>1<\/span>;<\/span>\n}<\/span>\nll out<\/span>(<\/span>ll n)<\/span>\n{<\/span>\n    ll l=<\/span>1<\/span>,<\/span>r=<\/span>(<\/span>1ll<\/span><<<\/span>63<\/span>)<\/span>-<\/span>1<\/span>;<\/span>\n    while<\/span>(<\/span>l<<\/span>r)<\/span>\n    {<\/span>\n        ll mid=<\/span>(<\/span>l+<\/span>r)<\/span>\/<\/span>2<\/span>;<\/span>;<\/span>\n        ll a=<\/span>js<\/span>(<\/span>mid)<\/span>;<\/span>\n        ll b=<\/span>a-<\/span>js<\/span>(<\/span>a)<\/span>;<\/span>\n        if<\/span>(<\/span>b>=<\/span>n)<\/span>\n            r=<\/span>mid;<\/span>\n        else<\/span>\n            l=<\/span>mid+<\/span>1<\/span>;<\/span>\n    }<\/span>\n    return<\/span> l;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    power[<\/span>0<\/span>]<\/span>=<\/span>1<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>100<\/span>;<\/span>i++<\/span>)<\/span>\n        power[<\/span>i]<\/span>=<\/span>power[<\/span>i-<\/span>1<\/span>]<\/span>*<\/span>10<\/span>;<\/span>\n    ll n;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span>i<<\/span>200<\/span>;<\/span>i++<\/span>)<\/span>\n        for<\/span>(<\/span>int<\/span> j=<\/span>0<\/span>;<\/span>j<<\/span>200<\/span>;<\/span>j++<\/span>)<\/span>\n            dp[<\/span>i]<\/span>[<\/span>j]<\/span>=<\/span>-<\/span>1<\/span>;<\/span>\n    while<\/span>(<\/span>scanf<\/span>(<\/span>\"%lld\"<\/span>,<\/span>&<\/span>n)<\/span>!=<\/span>EOF<\/span>)<\/span>\n        printf<\/span>(<\/span>\"%lldn\"<\/span>,<\/span>out<\/span>(<\/span>n)<\/span>)<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/icpc.upc.edu.cn\/pr…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-20","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/20","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=20"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/20\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=20"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=20"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=20"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}