题解:P14683 [ICPC 2025 Yokohama R] Decompose and Concatenate

· · 题解

题意

给你一个 n_s,拆成 a+b=n_s,把 ab 的数字连起来得到新数,找所有拆法中这个新数的最大值。

思路

1.设 a+b=nbk 位数,则拼接结果:C = a \times 10^k + b,因为 C = (n - b) \times 10^k + b

2.当 b 的位数固定为 k 时,k 就固定了,10^k是常数。对 b 求导:\frac{dC}{db} = -10^k + 1,因为 k \ge 1,所以 -10^k+1C 随着 b 增大而减小。因此,对于固定位数 k,要最大化 C,必须取最小的可能的 k 位数作为 b。最小的 k 位数是 10^{k-1}

算法步骤

读入 n。对于 k = 118: 计算 b = 10^{k-1}。如果 b \ge n,跳出循环。计算 a = n - b。拼接:C =a + b。更新最大值,比较字符串长度与字典序。

时间复杂度
```cpp #include <bits/stdc++.h> using namespace std; #define int long long signed main() { string n_s; cin>>n_s; //用 stoll 把字符串转成 long long 进行计算 int n=stoll(n_s); string best=""; //best表示最大拼接字符串 // 枚举 b 的位数 k for (int k=1;k<=18;k++) { int b=1; for(int i=1;i<k;i++) { b*=10; // b = 10^(k-1) } if(b>=n) break; // b 必须小于 N int a=n-b; // 使用字符串拼接避免溢出 string a_s=to_string(a); string b_s=to_string(b); // 拼接:a_s后面接 b_s string c=a_s+b_s; if(c.size()>best.size()||(c.size()==best.size()&&c>best)) { best=c; } } cout<<best; return 0; } ``` 肥美的题解...