题目背景：
给定一个正整数 N ,然后将 N 分解成 3 个正整数之和。用 C++ 计算出共有多少种符合要求的分解方法。
要求：
1 .分解的3个正整数各不相同;
2 .分解的3个正整数中都不含数字3和7.
如：N为8，可分解为1,1,6 1,2,5 1,3,4 2,2,4 2,3,3等5种。其中满足要求的分解方法有1种，为(1,2,5)。
输入格式：
输入一个正整数N (5 < N < 501),表示需要分解的正整数
输出格式
输出一个整数，表示共有多少种符合要求的分解方法
输入输出样例
输入样例
8
输出样例
1
因数：因数是指整数a除以整数b(b≠0)的商正好是整数而设没有余数，我们就说b是a的因数。 公因数：给定若干个整数，如果有一个（些）数是它们共同的因数，那么这个（些）数就叫做它们的公因数。 互质数：公因数只有1的两个非零自然数，叫做互质数：例如：2和3，公因数只有1，为互质数。
分享
关注题目：
问题：
给定一个由n行数字组成的数字三角形，如下图所示：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大（每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数）。
输入：
第一行是数字三角形的行数，接下来 n 行是数字三角形中的数字。
比如：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出：
输出这个最大值。
这里只给出代码，步骤分析看链接：步骤详解
代码实现：
代码注释的部分构成方法二
#include<stdio.h>
#include<math.h>
#include <windows.h>
#define N 5
int a[6][6];
int sum[6][6];
int sum_two[6];
int main()
{
int i,j;
for (i=1;i<=5;i++)
for (j=1;j<=i;j++)
scanf("%d",&a[i][j]);
for (i=1;i<6;i++)
{
sum[5][i] = a[5][i];
// sum_two[i] = a[5][i];
}
for (i=5-1;i>=1;i--)
for (j=1;j<=i;j++)
{
sum[i][j] = max(sum[i+1][j],sum[i+1][j+1]) + a[i][j];
//sum_two[j] = a[i][j] + max(sum_two[j],sum_two[j+1]);
}
for (i=1;i<6;i++)
{
for (j=1;j<=i;j++)
printf("%3d",sum[i][j]);
printf("\n");
}
//printf("%d",sum_two[1]);
return 0;
}
我需要计算给定正整数N（大于5小于501），将其分解成3个正整数之和的可能方案数。其中，要求这3个正整数各不相同，且它们不能包含数字3和7。请问共有多少种符合要求的分解方法？（例如，对于N为8，可分解为1,1,6、1,2,5、1,3,4、2,2,4、2,3,3等共5种，其中满足要求的分解方法只有1种：1,2,5。）
我们考虑使用三重循环分别枚举每一个数字，然后统计符合条件的和的数量。
比如我们尝试枚举 $x+y+z=7$ 的情况：
for x in range(1, 8):
for y in range(x + 1, 8):
for z in range(y + 1, 8):
if x != y and y != z and x != z:
print(x, y, z)
这样，对于每一个 $x+y+z=n$ 的情况都会使用上述三重循环计算出所有的答案。
但是这样复杂度过高，我们需要优化。那么该怎么办呢？我们可以把思路反一下：即，对于每一个 $x+y=a$ 的情况，统计出 a 有多少种情况满足 $x+y=a$，然后再枚举 $a+z=n$ 的情况，利用前面的结果即可计算出答案。
我们首先假设它非常大，统计出每一个 $x+y=i$ 的答案：
# origin 表示未去掉 3 和 7 的方案数，after 表示已去掉 3 和 7 的方案数
origin_ans = [-1 for i in range(N + 1)]
after_ans = [-1 for i in range(N + 1)]
for i in range(1, N + 1):
cnt = 0
for x in range(1, i):
y = i - x
cnt += min(x, y - 1) # 注意指定边界条件，avoid 3 and 7
origin_ans[i] = cnt
after_ans[i] = cnt - (1 if i not in [3, 7] else 0)
这样，我们就计算出了 $1$ 到 $N$ 之间去掉 3 和 7 的拆分方案数目了。接下来，我们再枚举 $a + z = n$ 这个等式，统计满足条件的方案数即可。
ans = 0
for a in range(1, n): # 枚举所有的 a
z = n - a
if z < 2 * a: # 防重复
break
ans += after_ans[a] * after_ans[z] # 乘法原理计算需要的答案
print(ans)
至此，我们就完成了问题的求解过程。
N = 501
# origin 表示未去掉 3 和 7 的方案数，after 表示已去掉 3 和 7 的方案数
origin_ans = [-1 for i in range(N + 1)]
after_ans = [-1 for i in range(N + 1)]
for i in range(1, N + 1):
cnt = 0
for x in range(1, i):
y = i - x
cnt += min(x, y - 1) # 注意指定边界条件，avoid 3 and 7
origin_ans[i] = cnt
after_ans[i] = cnt - (1 if i not in [3, 7] else 0)
def solve(n):
ans = 0
for a in range(1, n): # 枚举所有的 a
z = n - a
if z < 2 * a: # 防重复
break
ans += after_ans[a] * after_ans[z] # 乘法原理计算需要的答案
return ans
print(solve(8)) # expect 1
输入正整数n，判断从1到n之中，数字1一共要出现几次。例如1123这个数，则出现了两次1。例如15，那么从1到15之中，一共出现了8个1。
对于这道题，我们不能直接枚举每一个数中的 1 的数量，因为对于 $n$ 的范围 [1, 30000]，数据规模过大，枚举的时间复杂度无法接受。
那么，如何优化呢？我们考虑统计出 $1, 2, 3, \cdots, 9, 11, 12, \cdots, 19, 21, 22$ 中出现了多少个 $1$， $10, 20, \cdots, 90$ 中出现了多少个 $1$。比如，对于 $1$ 至 $9$ 的数，显然只有单个的数（1, 2, $\cdots$, 9）中才会出现 1，所以这些数字中一共会出现 $9$ 次 1。而对于 1 至 19 的数，它们中一共会出现 $11$ 次 1（除去 11 外，其余的都会出现一个 1；而在十位为 1 的数字中，又会出现 10 次 1）。那么这样的做法是否可行呢？
答案是可以的，我们统计 1 至 9，1 至 99，1 至 999 中一共出现了多少个 1，然后根据 $n$ 所在的区间来计算答案即可。
def c10(n): # 计算 n 之前的数字中统计到的次数
return n // 10 + (1 if (n % 10) >= 1 else 0)
# calc 1 number from 1 to 9, 1 to 99, 1 to 999
sum1 = 0
for i in range(1, 10):
sum1 += c10(3000 + i * 100 - 1) - c10(i * 100 - 1) + (i * 100)
ans = sum1 // 10
print(ans)
注意，这里我们采用了比较巧妙的方式，先计算出所有的结果（用变量 sum1 记录），最后再做一次除法。
比如，对于数字 1，它一共统计到了 301 次（出现了 10 次 1），类似的，对于数字 2，它一共统计到了 302 次（20 次 1）。这样计算出来的答案肯定是不正确的，但我们已经计算出了 1-9，1-99，1-999 范围内的所有结果，所以我们只需要将范围缩小到 $1001$ 至 $n$ 即可，计算答案时，再除以 10 即可。
def solve(n):
sum1 = 0
for i in range(1, 10):
sum1 += c10(1000 + i * 100 - 1) - c10(i * 100 - 1) + (i * 100)
return (sum1 + c10(n) - 1) // 10 + (1 if n % 10 >= 1 else 0)
print(solve(15)) # expect 8
创建了问题
5月15日
