思路与算法

从状态(n,十进制串n)做深度优先搜索。每到一个状态，把当前字符串放入哈希集合；枚举1≤k≤n/2，在左端拼接k，再递归到(k,新串)。最终集合大小就是答案。

正确性说明

任一合法操作序列的下一步恰是枚举范围中的某个k，故归纳可知搜索不漏任何合法最终串；每一步也都遵守当前数的一半限制，不会生成非法串。集合按完整最终串去重，不同分段方式得到相同十进制整数只计一次。正整数无前导零，字符串相等与最终整数相等等价。

复杂度

设合法操作序列状态数为K，最大串长为D，插入哈希表均摊O(D)，总时间均摊O(KD)，集合空间O(UD)，U≤K是不同结果数。递归深度≤floor(log2 n)+1。修订域n≤200的完整搜索至多205658个状态；不是声称对原n1000也可同资源枚举。

易错点

前缀是十进制拼接，不是算术相加。每步限制针对最近加上的整数；按最终整数去重，不按路径计数。n=24有93个不同整数，而忽略拼接冲突的数列递推为94。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
unordered_set<string> all;
void dfs(int n, const string &s) {
    all.insert(s);
    for (int k = 1; k <= n / 2; k++)
        dfs(k, to_string(k) + s);
}
int main() {
    int n;
    cin >> n;
    dfs(n, to_string(n));
    cout << all.size() << '\n';
}