当前位置: 首页 > news >正文

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];} 
}
http://www.hskmm.com/?act=detail&tid=13442

相关文章:

  • eslint
  • 视频调色神器!CyberLink ColorDirector:从入门到专业的视频色彩魔法工具
  • Leveraging Context-Aware Prompting for Commit Message Generation 论文笔记
  • P4951 [USACO01OPEN] Earthquake 题解
  • 用ida插件快速审计函数调用
  • 【ACM独立出版|往届已EI、Scopus检索|合作SSCI】第二届数字经济与计算机科学国际学术会议(DECS 2025)
  • schematool -initSchema -dbType mysql
  • PostgreSQL 全表 count 优化实践:从 SeqScan 痛点分析到 heapam 改进与性能突破
  • 第二章习题
  • Lightroom Classic 2025:精细调控,呈现完美画质,专业级数字照片管理与后期处理全解析
  • langfuse从v2.70.1升级到V3.110(异机升级+数据迁移)
  • 20250518_信安一把梭_医院抓取流量
  • tsx 图论选讲
  • OTP绕过漏洞:当后端过度信任前端时的安全灾难
  • 2MHz 8-bit 微控制器 with 64 Pins,M38049FFLKP ADR5040ARTZ TMS320F28062PZT K4AAG165WA-BCTD存储器
  • 实用指南:【Kubernetes】(六)Service
  • 校u圈校园外卖众包任务课表交友CPS社区:一站式校园生态服务系统
  • .NET Polly 全面指南:从5W2H维度深度解析
  • 撒钱岛小游戏管理系统:私域流量变现新选择,趣味与收益双赢
  • Day19构造器详解
  • 多商户的在线客服系统,直接在小程序的商家中嵌入我们的商家聊天链接
  • 【院士报告|EI检索稳定|大连理工大学主办】第四届能源与动力工程国际学术会议(EPE 2025)
  • 多客云 Ai 短视频批量剪辑矩阵系统:高效创作与智能管理的一体化解决方案
  • [ABC077D] Small Multiple 同余最短路
  • 20250509_信安一把梭_黑客
  • c# 保存文件 - 先保存到临时文件,保存成功后修改文件名
  • 达芬奇标记测量线文字标题动画预设(Tracked Measuring Lines)使用指南
  • 20250427_信安一把梭_No11
  • 运营商数据分类分级:最佳实践、典型案例与智能化方案
  • AT_abc413_g [ABC413G] Big Banned Grid