用python做洛谷p1217

洛谷 P1217 题目描述：

给定一个整数 N (1 ≤ N ≤ 10^18)，求出所有小于等于 N 的正整数中，十进制表示下各个数位上出现次数的总和。

例如，N=15 时，小于等于 15 的正整数中，数位 1 出现了 8 次，数位 2 出现了 1 次，数位 3 出现了 2 次，数位 4 出现了 1 次，数位 5 出现了 2 次，总和为 14。

思路：

对于每一位数，我们都可以计算出它在所有数中出现的次数，然后将结果相加即可。首先我们需要知道一个数的位数，可以使用字符串的长度来求得。然后我们可以考虑每一位数单独计算，这里我们需要判断当前位的数字是多少，分三种情况：

1. 如果当前位数的数字大于目标数，则该数字不会出现在所有数中，直接跳到下一位数。

2. 如果当前位数的数字小于目标数，则该数字会出现在所有数中。我们可以将目标数分为两部分，高位和低位。高位部分不变，低位部分从 0 到 10^k-1，其中 k 是当前位数右边的位数，也就是 10 的 k 次方。

3. 如果当前位数的数字等于目标数，则需要分别计算高位和低位的数值。高位的数值为目标数除以当前位数的进制，低位的数值为目标数对当前位数的进制取模。

代码实现：

相关问题

用python做洛谷p1996

洛谷P1996是一道经典的背包问题，可以使用动态规划算法来解决。以下是Python代码实现：

N, V = map(int, input().split())
w = [0] * (N + 1)
v = [0] * (N + 1)
dp = [[0] * (V + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    w[i], v[i] = map(int, input().split())

for i in range(1, N + 1):
    for j in range(1, V + 1):
        if j >= w[i]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[N][V])

这段代码首先读入背包的容量 `V` 和物品的数量 `N`，然后使用两个数组 `w` 和 `v` 分别存储物品的重量和价值。接着使用一个二维数组 `dp` 来存储每个子问题的最优解，其中 `dp[i][j]` 表示前 `i` 个物品装入容量为 `j` 的背包中所能获得的最大价值。

最后，通过动态规划的递推公式来计算每个子问题的最优解，最终输出 `dp[N][V]` 即为问题的解。

用python实现洛谷P1036

洛谷P1036是一道求解组合数问题的题目，可以使用回溯算法进行求解。以下是Python实现的代码示例：

n, k = map(int, input().split())
nums = list(map(int, input().split()))

count = 0

def backtrack(start, target, path):
    global count
    if len(path) == k:
        if sum(path) == target:
            count += 1
        return
    for i in range(start, n):
        if sum(path) + nums[i] <= target:
            path.append(nums[i])
            backtrack(i+1, target, path)
            path.pop()

backtrack(0, 0, [])
print(count)

以上代码中，首先读入输入的n、k和n个数字，然后定义了一个全局变量count来记录符合条件的组合数个数。接着定义了一个回溯函数backtrack，其中start表示从哪个位置开始搜索，target表示目标和，path表示当前已选的数字。在回溯过程中，如果已选数字个数等于k且它们的和等于目标和，则count加1。最后调用回溯函数并输出count即可。