题解：CF1181B Split a Number

xyy_xxyy · 2026-07-23 21:24:31 · 题解

首先我们枚举切割位置 i（1 \le i \le n-1，且 S_{i+1} \neq 0），对每个 i 用高精度计算 A_i + B_i 并取最小，时间复杂度 O(n^2)，会超时。

考虑优化。我们想一个问题：两个正整数相加，结果的位数最少是多少？显然是两数位数的最大值。设前缀长 i，后缀长 n-i，则和的位数 \ge \max(i, n-i)，误差最多只有一位。为使和尽可能小，应首先让和的位数尽可能小，这就希望 \max(i, n-i) 尽可能小。所以我们只需用找到 \max(i, n-i) 最小的数活着稍微大一点的数，这样的数的个数显然是 O(1) 的。之后按题意模拟即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], c[N], Min[N];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("cut.in", "r", stdin);
    // freopen("cut.out", "w", stdout);
    int T = 1;
//  cin >> T;
    while (T--) {
        int n;
        string s;
        cin >> n >> s;
        s = '*' + s;
        vector<int> v;
        int minx = 1e5, minxsz = 1e5;
        for (int i = 1; i < n; i++) {
            if (s[i + 1] != '0') {
                if (max(i, n - i) < minx) {
                    minx = max(i, n - i);
                    v = {i};
                } else if (max(i, n - i) == minx) {
                    v.push_back(i);
                }
            }
        }
//      cout << v.size();
        for (int i : v) {
//          cout << i << '?';
            int x = max(i, n - i);
//          cout << x << '\n';
            for (int j = 1; j <= x + 1; j++) {
                a[j] = 0;
                b[j] = 0;
                c[j] = 0;
            }
            for (int j = 1; j <= i; j++) {
                a[i - j + 1] = s[j] - '0';
            }
            for (int j = i + 1; j <= n; j++) {
                b[n - j + 1] = s[j] - '0';
            }
            for (int j = 1; j <= x; j++) {
                c[j] += a[j] + b[j];
                if (c[j] >= 10) {
                    c[j] -= 10;
                    c[j + 1]++;
                }
            }
            if (c[x + 1] != 0) {
                x++;
            }
//          for (int j = i; j >= 1; j--) {
//              cout << a[j];
//          }
//          cout << '\n';
//          for (int j = n - i; j >= 1; j--) {
//              cout << b[j];
//          }
//          cout << '\n';
//          for (int j = x; j >= 1; j--) {
//              cout << c[j];
//          }
//          cout << '\n';
            if (minxsz > x) {
                minxsz = x;
                for (int j = 1; j <= x; j++) {
                    Min[j] = c[j];
                }
            } else if (minxsz == x) {
                for (int j = x; j >= 1; j--) {
                    if (Min[j] > c[j]) {
                        minxsz = x;
                        for (int k = 1; k <= x; k++) {
                            Min[k] = c[k];
                        }
                        break;
                    } else if (Min[j] < c[j]) {
                        break;
                    }
                }
            }
        }
        for (int i = minxsz; i >= 1; i--) {
            cout << Min[i];
        }
    }
    return 0;
}