B. Sum of Two Numbers
The sum of digits of a non-negative integer $a$ is the result of summing up its digits together when written in the decimal system. For example, the sum of digits of $123$ is $6$ and the sum of digits of $10$ is $1$. In a formal way, the sum of digits of $\displaystyle a=\sum_{i=0}^{\infty} a_i \cdot 10^i$, where $0 \leq a_i \leq 9$, is defined as $\displaystyle\sum_{i=0}^{\infty}{a_i}$.
Given an integer $n$, find two non-negative integers $x$ and $y$ which satisfy the following conditions.
- $x+y=n$, and
- the sum of digits of $x$ and the sum of digits of $y$ differ by at most $1$.
It can be shown that such $x$ and $y$ always exist.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10\,000$).
Each test case consists of a single integer $n$ ($1 \leq n \leq 10^9$)
Output
For each test case, print two integers $x$ and $y$.
If there are multiple answers, print any.
Example
input
5 1 161 67 1206 19
output
1 0 67 94 60 7 1138 68 14 5
Note
In the second test case, the sum of digits of $67$ and the sum of digits of $94$ are both $13$.
In the third test case, the sum of digits of $60$ is $6$, and the sum of digits of $7$ is $7$.
解题思路
经典思维题想不出来。比赛的时候想了很久，最后还是写暴搜过的，先贴个代码。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
vector<int> num;
int pow10[10];
int ans[2];
int get(int x) {
int ret = 0;
while (x) {
ret += x % 10;
x /= 10;
}
return ret;
}
bool dfs(int a, int b, int u, int r) {
if (u == num.size() && a + b == n) {
ans[0] = a, ans[1] = b;
return true;
}
for (int i = 0; i <= 9; i++) {
int j = ((num[u] - i - r) % 10 + 10) % 10;
int t = abs(get(i * pow10[u] + a) - get(j * pow10[u] + b));
if (t <= 1 && dfs(i * pow10[u] + a, j * pow10[u] + b, u + 1, (i + j) / 10)) return true;
}
return false;
}
void solve() {
scanf("%d", &n);
num.clear();
for (int i = n; i; i /= 10) {
num.push_back(i % 10);
}
pow10[0] = 1;
for (int i = 1; i < num.size(); i++) {
pow10[i] = pow10[i - 1] * 10;
}
dfs(0, 0, 0, 0);
printf("%d %d\n", ans[0], ans[1]);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
View Code
思路就是从低位开始往高位搜，假设$n$的第$i$位是$a_i$，$y$的第$i$位是$b_i$，$x$的第$i$位是$c_i$，然后从$0 \sim 9$枚举$b_i$，那么$c_i = (a_i - b_i - r) \bmod 10$，其中$r$是来自低位的进位，同时还要满足$b_i + c_i \leq s$，$s$是指允许两数相差的最大值。实际上加上这些约束条件的剪枝后有效状态是非常少的（大概十多个，其中只要看哪个位两数相差为$1$就好了），因此可以过。
实际上这是道思维题来的。每一位都可以看作是独立的，因此可以没有进位。如果$n$是偶数的话那么直接$x = y = \frac{n}{2}$就好了。否则$n$是奇数，枚举$n$的每一位，如果$a_i$是偶数，那么$b_i = c_i = \frac{a_i}{2}$。如果$a_i$是奇数，那么$b_i$和$c_i$一个取$\left\lfloor \frac{a_i}{2} \right\rfloor$，一个取$\left\lceil \frac{a_i}{2} \right\rceil$，为了保证最后所有位数之和相差不超过$1$，可以交替地给$b_i$和$c_i$分配较大的数和较小的数。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 void solve() {
5 int n;
6 scanf("%d", &n);
7 int a = 0, b = 0, s = 0;
8 for (auto &c : to_string(n)) {
9 int x = c - '0';
10 if (x & 1) {
11 a = a * 10 + (x + s) / 2; // s是奇数，那么把较大的数分配给a
12 b = b * 10 + (x + !s) / 2; // s是偶数，那么把较大的数分配给b
13 s ^= 1;
14 }
15 else {
16 a = a * 10 + x / 2;
17 b = b * 10 + x / 2;
18 }
19 }
20 printf("%d %d\n", a, b);
21 }
22
23 int main() {
24 int t;
25 scanf("%d", &t);
26 while (t--) {
27 solve();
28 }
29
30 return 0;
31 }
参考资料
Codeforces Round #851 (Div. 2) Editorial：https://codeforces.com/blog/entry/112584
标签：digits,10,int,Sum,Two,leq,Numbers,test,sum From： https://www.cnblogs.com/onlyblues/p/17111272.html