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\) 出现了多少次
那么对于一个开头一个结尾,我们怎么办呢?
我们举个例子,结尾是 123456789
很容易想到,先直接 DP 到 \(f[\ 8\ ]\),然后从 100000000 开始考虑
第一位都是 \(1\),没有什么参考,进入第二位;
第二位应该是 \(2\),但是 \(2\) 又不是都能取得到啊,不过以 \(1\) 开头是直接加所有的 \(7\) 位数;
第三位应该是 \(3\),同样,\(1\) 和 \(2\) 开头可以加上所有 \(6\) 位数,可是对于 \(3\) 开头的怎么办呢?
先实现简单的部分吧,说不定就想出来了。
那么我实在是想不出来了,只能看看题解怎么说,太菜了。QAQ
其实不考虑 \(0\),\(1\) ~ \(9\) 对于每一位出现的数量是相同的,所以省去第二维状态。
我一直迷着两头处理,但是其实不用。这道题只需要数 \(0\) ~ \(a - 1\) 和 \(0\) ~ \(b\) 的再相减就好了。
考虑答案是 \(ans[\ x\ ]\):
从高位向低位遍历,对于第 \(i\) 位数字为 y,
如果 \(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];}
}