今天去牛客网看了看 包含一 这道题，一开始没看清，以为它要统计 1~n 所有数中数字 '1' 出现的总次数，也就是说，若 n == 11，则 ans = 4；而按照题目的原意 ans 应该为 3。看错题意后还是挣扎了好久，具体的调试过程也不想回忆叙述了，先贴上按照我一开始理解的意思的代码吧，虽然没有题目让我测，但我和自己写的暴力法对拍过，应该没问题的。
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL; LL C[][], p9[] = {,};
// C 数组为组合数，p9 是 9 的幂数组
inline void initC(const int &n = ) {
for(int i = ; i <= n; ++i)
C[i][] = ;
for(int i = ; i <= n; ++i)
for(int j = ; j <= n; ++j)
C[i][j] = C[i-][j-] + C[i-][j];
for(int i = ; i <= n; ++i)
p9[i] = p9[i-] * ;
} LL all[], num0[], num1[];
// all[i] 表示 i 位数的个数，num0[i] 表示不含数字 1 的 i 位数的个数
// num1[i] 表示 i 位数中含有数字 1 出现的总次数，注意是 '1' 出现的总次数！求法有点麻烦
inline void init(const int &k = ) {
all[] = ;
num0[] = ;
for(int i = ; i <= k; ++i) {
all[i] = all[i-] * ;
num0[i] = num0[i-] * ;
}
initC();
for(int n = ; n <= k; ++n) {
LL &sum = num1[n];
sum = ;
for(int i = ; i <= n; ++i)
sum += i * C[n][i] * p9[n-i];
}
} // 和数位 dp 的分析步骤有点类似
inline LL solve(const LL &n) {
LL digit[], len = , x = n;
while(x) {
digit[++len] = x % ;
x /= ;
}
int count = ; // 统计前 i 位数字 1 的个数
LL sum = ;
// 核心计数部分（结合曾经做过的数位 dp 的思路来考虑）
for(LL i = len; i > ; --i) {
sum += digit[i] * num1[i-]; // 先加上当第 i 位取 0~digit[i]-1 时，i-1 位数的数字 1 的总个数
if(count) sum += count * digit[i] * all[i-]; // 统计前面的 1 的个数（第 i 位后取任何数字都没所谓）
if(digit[i] == ) ++count; // 计数器加 1
if(digit[i] > ) sum += all[i-]; // 统计若当前位取 1 时的个数（同理后面是什么都没所谓）
}
// 好好体会下这个数位 dp 的思路，要做到不重不漏真不容易~
return sum;
} // 分解统计 '1' 的个数
inline LL caclu(LL x) {
LL res = ;
while(x) {
if(x % == ) ++res;
x /= ;
}
return res;
} // 暴力枚举统计
inline LL test(const LL &x) {
LL sum = ;
for(LL i = ; i <= x; ++i)
sum += caclu(i);
return sum;
} int main() {
LL n;
init();
while(~scanf("%I64d",&n))
printf("solve = %I64d test = %I64d\n\n",solve(n+),test(n));
return ;
}
统计 1~n 中数字'1'出现的总次数
后来，按照题目的意思我又重做了一遍：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int dp[][];
// dp[0][i] 表示包含 1 的 i 位数的个数
// dp[1][i] 表示以 1 开头的不包含 1 的 i 位数的个数
// dp[2][i] 表示不包含 1 的 i 位数的个数
// 其实 dp[1][i] 和 dp[2][i] 实质是一样的，合并成一个就行了，所以空间和时间都能提升一点；为了让它更直观，我就不改了
inline void init(int n = ) {
dp[][] = ;
for(int i = ; i <= n; ++i) {
dp[][i] = * dp[][i-] + dp[][i-];
dp[][i] = dp[][i-];
dp[][i] = dp[][i-] * ;
}
} inline int solve(int x) {
int digit[], len = ;
while(x) {
digit[++len] = x % ;
x /= ;
}
bool flag = ;
int sum = ;
for(int i = len; i; --i) {
sum += digit[i] * dp[][i-];
if(flag) sum += digit[i] * dp[][i-];
else if(digit[i] > ) sum += dp[][i];
if(digit[i] == ) flag = ;
}
return sum;
} const int inf = 0x7fffffff; int main() {
int n;
init();
while(~scanf("%d",&n)) { // 有符号 int 的上限，要注意处理好
if(n == inf) printf("%d\n",solve(n) + );
else printf("%d\n",solve(n+));
}
return ;
}
统计包含'1'的数字的个数
耗费了一个中午和下午时间写完这两个代码后，我发觉我对于数位 dp 已经感到无爱了，再给我来一道这样的题的话就真的要挂了~
---------------------------------------------来填一下坑先---------------------------------------------------
后来发现，原来还有这样的一道题 统计一，把我第一个代码的 I64d 改为 lld 以及输出修改一下就能过，果然我的做法是对哦~