9.22 机房练习

9.22 机房练习

一、 引子

向 myk 大佬学习，养成写练习笔记的好习惯。
还有大约三十多天就复赛了，我的安排是保持每天一两道首银的题目 + 紫书上的题单，前面的是练习有一定难度的题目冲击高分，后面的是系统复习保持手感。
我会尽量不看题解的，但是实在不会真没办法 QAQ。

二、 首银

1. P2602 [ZJOI2010] 数字计数

这道题首先，强硬模拟是不行的，那么思考怎么得到正确答案呢？
我们使用形如 \(\overline{XYZ}\) 表示 \(X \times 100 + Y \times 10 \times Z\)。比如说，对于 \(\overline{1Y}\) 而言，\(1\) 出现了 \(19\) 次，其他数字各出现 \(1\) 次。
那我们能不能基于这个性质，来考虑考虑呢？
假设 \(f[\ x\ ][\ y\ ]\) 表示 \(x\) 位数中 \(y\) 出现了多少次

\[f[\ x\ ][\ y\ ] = f[\ x-1\ ][\ y\ ] \times 9 + 10 ^ { x - 1 } \]

\[\tiny{\red{这个公式是错误的，放在这里仅仅代表思路}} \]

那么对于一个开头一个结尾，我们怎么办呢？
我们举个例子，结尾是 123456789
很容易想到，先直接 DP 到 \(f[\ 8\ ]\)，然后从 100000000 开始考虑
第一位都是 \(1\)，没有什么参考，进入第二位；
第二位应该是 \(2\)，但是 \(2\) 又不是都能取得到啊，不过以 \(1\) 开头是直接加所有的 \(7\) 位数；
第三位应该是 \(3\)，同样，\(1\) 和 \(2\) 开头可以加上所有 \(6\) 位数，可是对于 \(3\) 开头的怎么办呢？
先实现简单的部分吧，说不定就想出来了。

---

那么我实在是想不出来了，只能看看题解怎么说，太菜了。QAQ
其实不考虑 \(0\)，\(1\) ~ \(9\) 对于每一位出现的数量是相同的，所以省去第二维状态。

\[f[\ i\ ] = f[\ i-1\ ] \times 10 + 10 ^ { i - 1 } \]

我一直迷着两头处理，但是其实不用。这道题只需要数 \(0\) ~ \(a - 1\) 和 \(0\) ~ \(b\) 的再相减就好了。
考虑答案是 \(ans[\ x\ ]\)：
从高位向低位遍历，对于第 \(i\) 位数字为 y，

\[ans[\ x\ ] += f[\ i-1\ ] \times y , x \in [0 , 9] \]

\[ans[\ x\ ] += 10 ^ { i - 1 } , x \in [0 , y - 1] \]

如果 \(x = y\)，那么还有： \(ans[\ y\ ] += num + 1\)，其中 num 是第 i-1 ~ 1 位的数字，但是 \(ans[\ 0\ ] -= 10 ^ { i - 1 }\)。
最后每一位就是 \(ans_b[x] - ans_{a-1}[x]\)。
代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#define int long long 
using namespace std;
const int MAXN=20;
void solve(int,int);
int f[MAXN],fic[MAXN];
int ans[MAXN][2];
int a,b;
signed main(){fic[0]=1;// fic[i] 表示 10 ** i for(int i=1;i<=12;i++){f[i]=f[i-1]*10+fic[i-1];fic[i]=fic[i-1]*10;}cin>>a>>b;solve(a-1,0);solve(b,1);// 尽量不传数组 for(int i=0;i<=9;i++){cout<<ans[i][1]-ans[i][0]<<" ";}return 0;
}
int c[MAXN];// 存储每一位数字 
void solve(int x,int d){// 提取数位 memset(c,0,sizeof(c));int m=0;while(x){c[++m]=x%10;x/=10;}// DPfor(int i=m;i>=1;i--){for(int j=0;j<=9;j++){ans[j][d]+=f[i-1]*c[i];}for(int j=0;j<c[i];j++){ans[j][d]+=fic[i-1];}int num=0;for(int j=i-1;j>=1;j--){num=num*10+c[j];}ans[c[i]][d]+=num+1;ans[0][d]-=fic[i-1];} 
}