{"id":496,"date":"2020-05-10T23:43:08","date_gmt":"2020-05-10T15:43:08","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=496"},"modified":"2020-05-15T10:40:06","modified_gmt":"2020-05-15T02:40:06","slug":"5-%e8%a1%a5%e9%a2%98-%e7%ac%ac%e5%85%ad%e6%ac%a1%e8%ae%ad%e7%bb%83","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/05\/10\/5-%e8%a1%a5%e9%a2%98-%e7%ac%ac%e5%85%ad%e6%ac%a1%e8%ae%ad%e7%bb%83\/","title":{"rendered":"5-8 \u8865\u9898  \u7b2c\u4e03\u6b21\u8bad\u7ec3"},"content":{"rendered":"<h4><a href=\"https:\/\/vjudge.net\/problem\/UVA-12670\">UVA12670 Counting ones<\/a><\/h4>\n<p>\u9996\u5148\u628an\u8f6c\u6362\u62102\u8fdb\u5236\uff0c\u7136\u540e\u679a\u4e3e\u4e0a\u9650\u53d8\u62101.<\/p>\n<pre><code class=\"language-c++\">#include &lt;iostream&gt;\n#include &lt;cstring&gt;\n#include &lt;cmath&gt;\nusing namespace std;\ntypedef long long ll;\nll a[200];\nll dp[200];\nll dfs(int pos, bool limit, ll now){\n    if (pos==-1)    return now;\n    if (!limit &amp;&amp; dp[pos]!=-1)  return now*pow(2,pos+1)+dp[pos];\n    int up = limit? a[pos]:1;\n    ll ans = 0;\n    for (int i=0;i&lt;=up;i++){\n        ans += dfs(pos-1, limit &amp;&amp; i==a[pos], now+i);\n    }\n    if (!limit) dp[pos] = ans;\n    return ans;\n}\nll solve(ll n){\n    memset (dp, -1, sizeof dp);\n    memset (a, 0, sizeof a);\n    int pos = 0;\n    a[0] = n;\n    while (a[pos]){\n        a[pos+1] += a[pos] \/ 2;\n        a[pos] %= 2;\n        pos++;\n    }\n    return dfs(pos-1, true, 0);\n}\nint main(){\n    ll l,r;\n    while (cin &gt;&gt; l &gt;&gt; r){\n        cout &lt;&lt; solve(r) - solve(l-1) &lt;&lt; endl;\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>UVA12670 Counting ones \u9996\u5148\u628an\u8f6c\u6362\u62102\u8fdb\u5236\uff0c\u7136\u540e\u679a\u4e3e\u4e0a\u9650\u53d8\u62101. #incl [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[31],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/496"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=496"}],"version-history":[{"count":4,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/496\/revisions"}],"predecessor-version":[{"id":500,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/496\/revisions\/500"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=496"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=496"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=496"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}