给一个整数n, n<10^18,拆成若干段,每段加起来求和。输出所有和中 <= k 的个数。k<10^18。c++dfs代码
时间: 2024-01-22 20:19:53 浏览: 19
以下是使用DFS的C++代码实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
long long n, k, ans = 0;
int a[20];
void dfs(int pos, long long sum) {
if (pos == -1) {
if (sum <= k) ans++;
return;
}
long long cur = 0;
for (int i = pos; i >= 0; i--) {
cur = cur * 10 + a[i];
if (sum + cur * (pos - i + 1) <= k)
dfs(i - 1, sum + cur * (pos - i + 1));
}
}
int main() {
cin >> n >> k;
int len = 0;
while (n) {
a[len++] = n % 10;
n /= 10;
}
dfs(len - 1, 0);
cout << ans << endl;
return 0;
}
```
主要思路是从高位到低位进行DFS,每次记录当前位数和当前拼接的数字,并判断剩余的数字能否拼接成小于等于k的和。时间复杂度为O(logn * k)。
相关问题
给一个整数n, n<10^18,拆成若干段,每段加起来求和。输出所有和中 <= k 的个数。k<10^18。c++代码
这道题可以使用数位 DP 来解决。
定义状态 $f(i,j,s)$ 表示在第 $i$ 位上,已经拆出了 $j$ 个数,并且当前的和为 $s$ 的方案数。
转移时,枚举当前这一段数的结束位置 $k$,则当前这一段的和为 $\sum_{p=i}^k d_p$,其中 $d_p$ 表示第 $p$ 位上的数字。我们可以直接计算出当前这一段的和,如果当前这一段的和小于等于 $k$,则可以转移到 $f(k+1,j+1,s+\sum_{p=i}^k d_p)$,即在下一位继续拆出一个数,并且更新当前的和。
最后,答案就是 $\sum_{i=1}^{18} f(1,0,i)$,即从第一位开始,拆出若干个数,使得所有拆出的数的和小于等于 $k$ 的方案数之和。
时间复杂度为 $O(\log n \cdot k^2)$。
参考代码如下:
输入数据有多组,每组为一行,包括若干个32位整数。对每组输入,在单独的行中输出结果。
你可以使用以下代码来获取输入中的多组数据,并逐组处理并输出结果:
```python
# 获取输入数据
while True:
try:
# 逐行读取输入
line = input().strip()
# 检查是否为空行
if line == '':
continue
# 将一行数据拆分成多个整数
data = list(map(int, line.split()))
# 处理该组数据并输出结果
# 在这里你可以根据需求进行相应的处理逻辑
result = sum(data) # 这里只是一个示例,将列表中的整数求和
# 输出结果
print(result)
except EOFError:
break
```
这段代码会循环读取输入的每一行数据,并将每行数据拆分成整数列表。然后你可以根据需要对列表进行相应的处理逻辑,例如求和、最大值、排序等。最后,将处理结果输出到单独的行中。
请注意,该代码在遇到输入结束(即文件末尾)时会终止循环。在使用交互式输入时,你可以通过键盘输入`CTRL + Z`(Windows)或`CTRL + D`(Unix/Linux)来表示输入结束。