Codeforces Round ＃219（Div. 2)373 B. Making Sequences is Fun(二分+找规律)

题目意思大概是给你w，m，k三个数，让你从m开始找 m m+1 m+2 m+3...........m+m', 使得他们的权值之和不超过w，计算权值的方法如下S(n)·k
。 S(n)表示n有多少位数,让你计算出最多有多少个这样的数。

乍一眼看去，10^16如此大的数肯定不能暴力，然后稍微思考一下就可以找到规律了，规律如下。

1-10 有9个一位数

1-100 有9个一位数有90个二位数

1-1000 有9个一位数有90个二位数有900个三位数

1-10000 有9个一位数有90个二位数有900个三位数有9000个四位数

。。。。。。。。。。。。

那么1-n有多少个几位数很快就可以计算出来了，然后用二分法计算结果。代码如下

#include <stdio.h>

#include <iostream>

#define ll long long

#define inf 100000000000000000

//二分上界必须大于10^16，不然会出错

using namespace std;

ll w, m, k;

ll getans(ll x)

{

    ll cmp = 10;

    ll add = 9;

    ll ans = 0;

    ll sum = 0;

    ll cnt = 1;

    while (x >= cmp)

    {

        sum += add;

        ans += add*cnt;

        cnt++;

        add *= 10;

        cmp *= 10;

    }

    ans += (x - sum)*cnt;

    return ans;

}

inline ll getval(ll x)

{

    return (getans(x)-getans(m-1));

}

ll binarysearch(ll l, ll r, ll val)

{

    if (l == r)

    {

        while (getval(l) > val)

            l--;

        return l;

    }

    ll mid = (l + r) >> 1;

    if (getval(mid) < val)

        return binarysearch(mid+1, r, val);

    else

        return binarysearch(l, mid, val);

}

int main()

{

    while (cin >> w >> m >> k)

    {

        ll t = binarysearch(m, inf, w/k);// 二分的第三个参数必须这样，不能在其他地方乘，不然也会溢出

        if (t < m)

            puts("0");

        else

            cout << t - m + 1 << endl;

    }

    return 0;

}

巴特西

Codeforces Round ＃219（Div. 2)373 B. Making Sequences is Fun(二分+找规律)

最新文章

热门文章