基于 1 的算术

问题 - 440C - Codeforces
原题链接

题目描述

\(Vasechkin\) 教授想要将正整数 \(n\) 表示为一些加数的和，其中每个加数可正可负，但都是只包含数字 \(1\) 的整数。例如，他可以将 \(121\) 表示为 \(121=111+11+(-1)\) 。

请你帮助他找到这样的和中所需数字 \(1\) 的最小数量。

输入描述

第一行输入一个整数 \(n\)。其中 \(1\le n < 1e15\)。

输出描述

输出所需的 \(1\) 的最小数量。

样例

输入样例

121

输出样例

6

本人解法

设 \(y_i\) 为 \(i\) 个 1，如 \(y_5 = 11111\)。
想一想，对于 \(10^n\) 只需要使用一个 \(y_{n + 1} - y_{n}\) 即可，为了方便，先把正常需要的 \(y_i\) 的数量统计出来。如 \(150\) 就等于 \(1\) 个 \(10^2\)，\(5\) 个 \(10^5\)，也就是 \(1\) 个 \(y_3\)，\(4\) 个 \(y_2\)，\(-5\) 个 \(y_1\)。

设每个 \(y_i\) 的数量为 \(a_i\)。使 \(a_i\) 减少的方式，只有借助更高的 \(y_{i+1}\)，已知，一个 \(y_{i+1} = 10y_i - y_1\)。因为这题最多有 \(10^{16}\)，也就最多 \(17\) 种 \(y_i\)，因此，对每个 \(y_i\) 操作，暴力每个借助不借助高位，改变 \(a_i\) 的数量，最后统计答案即可。

注意：正负数 \(a_i\) 借助， \(a_i\) 变化是不同的，而每个 \(y_i\) 最多需要借助一次（可自行证明）。

比较容易理解。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 110;

LL n;
vector<int> g;
int a[N], len, minv = 0x3f3f3f3f;

void dfs(int x)
{
    if (x > len)
    {
        
        int sum = 0;
        for (int i = 0; i <= len; i ++ )
            sum += abs(a[i]) * (i + 1);
        minv = min(minv, sum);
        return ;
    }
    
    int y = abs(a[x]), i = x + 1;
    dfs(x + 1);
    
    if (a[x] > 0) // 
    {
        a[x + 1] += 1;
        a[x] -= 10;
        a[0] -- ;
        dfs(x + 1);
        a[x] += 10;
        a[0] ++ ;
        a[x + 1] -- ;
    } 
    else if (a[x] < 0) 
    {
        a[x + 1] --;
        a[x] += 10;
        a[0] ++ ;
        dfs(x + 1);
        a[x] -= 10;
        a[0] -- ;
        a[x + 1] ++;
    }
}

int main()
{
    cin >> n;
    while (n) // 取出每一位
    {
        g.push_back(n % 10);
        n /= 10;
    }
    
    len = g.size();
    for (int i = len - 1; i >= 0; i -- )
    {
        a[i] += g[i];
        if (i) a[i - 1] -= g[i];
        // cout << a[i] << endl;
    }
    dfs(0);
    
    cout << minv << endl;
    
    return 0;
}

这是题解解法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef long long LL;

LL d[100] = {0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111, 1111111111111, 11111111111111, 111111111111111, 1111111111111111, 11111111111111111};
LL n, m;
LL ans = 1e18;

int find(LL x)
{
    int l = 1, r = 16;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (x <= d[mid]) r = mid;
        else l = mid + 1;
    }
    return l;
}

void dfs(int u, LL x, LL sum)
{
    if (!u)
    {
        if (!x) ans = min(ans, sum);
        return;
    }
    LL k = d[find(x)] - x, b = find(x); 
    dfs(u - 1, k % d[u], sum + k / d[u] * u + b);
    dfs(u - 1, x % d[u], sum + x / d[u] * u);
}

int main()
{
    cin >> n;
    dfs(16, n, 0);
    cout << ans;
    return 0;
}

/*
hack
19
7

150
15

111
3
*/