Project Euler 637

题目

Flexible digit sum

Given any positive integer \(n\), we can construct a new integer by inserting plus signs between some of the digits of the base \(B\) representation of \(n\), and then carrying out the additions.

For example, from \(n=123_{10}\) (\(n\) in base \(10\)) we can construct the four base 10 integers \(123_{10}\), \(1+23=24_{10}\), \(12+3=15_{10}\) and \(1+2+3=6_{10}\)

Let \(f(n,B)\) be the smallest number of steps needed to arrive at a single-digit number in base \(B\). For example, \(f(7,10)=0\) and \(f(123,10)=1\).

Let \(g(n,B_1,B_2)\) be the sum of the positive integers \(i\) not exceeding \(n\) such that \(f(i,B_1)=f(i,B_2)\).

You are given \(g(100,10,3)=3302\).

Find \(g(10^7,10,3)\)

解决方案

解决过程比较暴力。对于一个数\(n\)，通过二进制枚举其每一个划分，并且将划分的值进行求和得到\(s\)。最终的目标是找到一个最优秀的\(s\)。也就是说，\(\displaystyle{f(n,B)=\min_{s}\{f(s,B)+1\}}\)。

不过，直接暴力枚举后继状态\(s\)效果非常差，以下是一些改进过程：

• 枚举状态的顺序：先枚举密的划分，再枚举疏的划分。因为基于一种虚假的贪心思想是，划分的越多，变成个位数的步骤越少。
• 按照上面的枚举顺序，求解\(f(n,B)\)。当枚举到后继状态\(s\)满足\(f(s,B)=0\)时，说明此时必定有\(f(n,B)=1\)，这是显而易见的。如果后继状态\(s\)满足\(f(s,B)=1\)时，说明此时有\(f(n,B)=2\)，因为一开始枚举的状态是将所有数位都划分，如果在这种情况下都无法满足\(f(n,B)=0\)，那么后继更不可能存在\(s\)满足\(f(s,B)=0\)，因为这个划分的内部至少存在一个两位数；因此如果遇见\(f(s,B)=1\)，那么及时停止循环。

由于对于绝大多数\(n\)而言，\(f(n,3)\le 2\)成立，因此上述优化可以有效增加效率。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=10000000;
const int B1 = 10,B2 = 3;
int f1[N+4],f2[N+4],w;
int s[44],p;
void parse(int n,int b){
    p=0;
    for(;n;n/=b)
        s[p++]=n%b;
    reverse(s,s+p);
}
void solve(int n,int *f,int b){
    for(int i=0;i<=min(b-1,n);i++)
        f[i]=0;
    for(int i=b;i<=n;i++){
        int &w=f[i];w=1e9;
        parse(i,b);
        int msk=1<<p;
        // 优化点 (1)
        for(int st=msk-1;st>=(msk>>1);st--){
            int sum=0,t=0;
            for(int i=0;i<p;i++){
                t=t*b+s[i];
                if(st>>i&1){
                    sum+=t;t=0;
                }
            }
            w=min(w,f[sum]);
            // 优化点 (2)
            if(w<=1) break;
        }
        ++w;
    }
}
int main(){
    solve(N,f1,B1);
    solve(N,f2,B2);
    ll ans = 0;
    for(int i=1;i<=N;i++){
        if(f1[i]==f2[i]){
            ans += i;
        }
    }
    printf("%lld\n",ans);
}