当前位置:网站首页>洛谷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;
}
转载请说明出处
边栏推荐
- Méthode d'obtention des propriétés de l'objet JS (.Et [] méthodes)
- How are the open source Netease cloud music API projects implemented?
- Uni app third party package configuration network request
- Leetcode35. search the insertion position (simple, find the insertion position, different writing methods)
- word中把带有某个符号的行全部选中,更改为标题
- 杰理之BLE【篇】
- Related operations of Excel
- [dictionary tree] [trie] p3879 [tjoi2010] reading comprehension
- 【mysql学习笔记30】锁(非教程)
- The differences and advantages and disadvantages between cookies, seeion and token
猜你喜欢
If Jerry's Bluetooth device wants to send data to the mobile phone, the mobile phone needs to open the notify channel first [article]
学go之路(一)go的基本介绍到第一个helloworld
Markdown 中设置图片图注
Detailed explanation | detailed explanation of internal mechanism of industrial robot
First knowledge of OpenGL es learning (1)
Cookie技术&Session技术&ServletContext对象
The author is dead? AI is conquering mankind with art
jmeter性能测试步骤实战教程
When the Jericho development board is powered on, you can open the NRF app with your mobile phone [article]
Ble of Jerry [chapter]
随机推荐
1091: two or three things in childhood (multi instance test)
js對象獲取屬性的方法(.和[]方式)
Full Score composition generator: living on code
chrome查看页面fps
How Navicat imports MySQL scripts
Path analysis model
The first Baidu push plug-in of dream weaving fully automatic collection Optimization SEO collection module
【线上问题处理】因代码造成mysql表死锁的问题,如何杀掉对应的进程
The author is dead? AI is conquering mankind with art
navicat如何导入MySQL脚本
ORACLE列转行--某字段按指定分隔符转多行
Go learning -- implementing generics based on reflection and empty interfaces
Fundamentals of C language 9: Functions
leetcode704. Binary search (find an element, simple, different writing)
Multi attribute object detection on rare aircraft data sets: experimental process using yolov5
Uni app practical project
Twelve rules for naming variables
When the Jericho development board is powered on, you can open the NRF app with your mobile phone [article]
Word delete the contents in brackets
OpenJudge NOI 2.1 1749:数字方格