当前位置:网站首页>洛谷P1836 数页码 题解
洛谷P1836 数页码 题解
2022-07-06 07:23:00 【q779】
洛谷P1836 数页码 题解
题目链接:P1836 数页码
题意:
一本书的页码是从 1 ∼ n 1\sim n 1∼n 编号的连续整数: 1 , 2 , 3 , ⋯ , n 1,2,3,\cdots,n 1,2,3,⋯,n。请你求出全部页码中所有单个数字的和,例如第 123 123 123 页,它的和就是 1 + 2 + 3 = 6 1+2+3=6 1+2+3=6。
1 ≤ n ≤ 1 0 9 1\le n\le 10^9 1≤n≤109
容易发现这个东西可以转化为
1 ∼ n 1 \sim n 1∼n 中每个数字有多少个
考虑数位dp,详见link
然后把每个数字乘一乘就好了
代码:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()
int x,mi[25],cnt[25],num[25],f[25];
void solve(int x,int *cnt)
{
int len=0;
memset(num,0,sizeof(num));
while(x)
{
num[++len]=x%10;
x/=10;
}
for(int i=len; i>=1; i--)
{
for(int j=0; j<=9; j++)
cnt[j]+=f[i-1]*num[i];
for(int j=0; j<num[i]; j++)
cnt[j]+=mi[i-1];
int res=0;
for(int j=i-1; j>=1; j--)
{
res = res * 10 + num[j];
}
cnt[num[i]]+=res+1;
cnt[0]-=mi[i-1];
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
mi[0]=1;
for(int i=1; i<=18; i++)
{
f[i]=f[i-1]*10+mi[i-1];
mi[i]=10*mi[i-1];
}
cin >> x;
solve(x,cnt);
int res=0;
for(int i=0; i<=9; i++)
res+=cnt[i]*i;
cout << res << '\n';
return 0;
}
转载请说明出处
边栏推荐
- 【mysql学习笔记30】锁(非教程)
- Wechat official account infinite callback authorization system source code, launched in the whole network
- 变量的命名规则十二条
- Set picture annotation in markdown
- qt颜色与字符串、uint相互转换
- OpenJudge NOI 2.1 1749:数字方格
- Typescript interface and the use of generics
- leetcode1020. Number of enclaves (medium)
- Related operations of Excel
- TypeScript接口与泛型的使用
猜你喜欢
Ble of Jerry [chapter]
数字IC设计笔试题汇总(一)
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
qt颜色与字符串、uint相互转换
Ali's redis interview question is too difficult, isn't it? I was pressed on the ground and rubbed
Leetcode35. search the insertion position (simple, find the insertion position, different writing methods)
(4) Web security | penetration testing | network security web site source code and related analysis
If Jerry needs to send a large package, he needs to modify the MTU on the mobile terminal [article]
Leecode-c language implementation -15 Sum of three ----- ideas to be improved
Raspberry pie 3B update VIM
随机推荐
Jerry's general penetration test - do data transmission with app Communication [article]
【线上问题处理】因代码造成mysql表死锁的问题,如何杀掉对应的进程
word怎么只删除英语保留汉语或删除汉语保留英文
Méthode d'obtention des propriétés de l'objet JS (.Et [] méthodes)
C - Inheritance - hidden method
SSM learning
Go learning -- implementing generics based on reflection and empty interfaces
qt颜色与字符串、uint相互转换
2022年Instagram运营小技巧简单讲解
软件测试界的三无简历,企业拿什么来招聘你,石沉大海的简历
Cookie Technology & session Technology & ServletContext object
Summary of Digital IC design written examination questions (I)
If Jerry needs to send a large package, he needs to modify the MTU on the mobile terminal [article]
Internal and external troubles of "boring ape" bayc
Memory error during variable parameter overload
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
NiO programming introduction
TypeScript void 基础类型
Project GFS data download
Scala语言学习-08-抽象类