HDU7106 Function 题解

题目大意

定义 $g(x)$ 表示 $x$ 十进制下每一位数字之和，比如 $g(123) = 1+2+3 = 6$。

求 $f(x) = Ax^2g(x) + Bx^2 + Cxg^2(x) + Dxg(x)$，在 $[1, n]$ 之间的最小值（$x$ 为整数）。

其中 $A, B, C, D, n$ 为题目输入，$1 \le n \le 10^6$。

思路

$f(x)$ 可以转化为 $f(x) = [Ag(x)+B]x^2 + [Cg^2(x)+Dg(x)]x$。

不难发现，$g(x)$ 的值域是 $[1, n]$。而 $g(x)$ 的值一旦确定，那么 $f(x)$ 就成为了只能取特定自变量值的二次函数。

比如 $g(x) = 10$ 时，$x$ 可取 $10, 19, 28, \ldots$ 等。因为此时 $f(x)$ 已经是二次函数了，那么它的最小值，显然为：

• 开口向下：取两端边界值。
• 开口向上：取对称轴两侧的那两个值。

所以我们对于 $g(x)$ 的每一个值，计算它的最小值，最后再比较即可。

具体做法

1. 先预处理出 $v$ 数组，$v[i][j]$ 表示，在满足 $g(x)=i$ 的所有 $x$ 中，从小到大的第 $j+1$ 个是多少。比如 $v[2][1]$ 显然是11（因为第一个是2）。
2. 枚举 $g(x)$ 从1到54的值，计算对称轴，计算对称轴两侧的值。（如果开口向下，那么它的最小值显然就是两侧，那么就不需要计算对称轴两侧的值了）

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int maxN = 10010;
typedef long long ll;

vector<ll> v[maxN];
ll a, b, c, d, n, T;

ll calcG(ll x)
{
    ll ans = 0, tmp = x;
    while(tmp) {
        ans += tmp % 10;
        tmp /= 10;
    }
    return ans;
}

ll calc(ll x)
{
    ll g = calcG(x);
    return a * x * x * g + b * x * x + c * x * g * g + d * g * x;
}

inline void init()
{
    for(int i = 1; i <= 1000000; ++i) {
        v[calcG(i)].push_back(i);
    }
}

int main()
{
    init();
    scanf("%d", &T);
    while(T--) {
        scanf("%lld%lld%lld%lld%lld", &a, &b, &c, &d, &n);
        ll ans = calc(1);
        for(int i = 1; i <= 54; ++i) {
            ll A = a * i + b;
            if(A == 0)
                continue;
            ll B = c * i * i + d * i;
            ll mid = (-B) / (A + A);
            if(mid <= 0)
                continue;
            ll tmp = upper_bound(v[i].begin(), v[i].end(), mid) - v[i].begin();
            ll bound = upper_bound(v[i].begin(), v[i].end(), n) - v[i].begin();
            if(tmp < bound && tmp >= 0 && v[i][tmp] <= n) ans = min(calc(v[i][tmp]), ans);
            if(tmp - 1 <bound && tmp - 1 >= 0 && v[i][tmp - 1] <= n) ans = min(calc(v[i][tmp - 1]), ans);
        }
        for(int i = 1; i <= 54; ++i) {
            ll x1 = v[i][0];
            if(x1 > n)
                break;
            ll x2 = v[i][upper_bound(v[i].begin(), v[i].end(), n) - v[i].begin() - 1];
            ans = min(ans, min(calc(x1), calc(x2)));
        }
        printf("%lld\n", ans);
    }
    return 0;
}