HDU-7106

题目大意

定义\(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...\)等。因为此时\(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\)的值，计算对称轴。计算对称轴两侧的值。（如果开口向下，那么它的最小值显然就是两侧，那么就u不需要计算对称轴两侧的值了）

代码

#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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2021/09/06/HDU-7106/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！