裸数位 dp 评蓝有问题吗。
by Neutralized @ 2022-08-22 15:47:56
有问题吗？
by EastPorridge @ 2022-08-22 15:50:45
@[YuRuochen](/user/658786) 看完数据范围在来说难度吧
by NightTide @ 2022-08-22 15:59:54
@[YuRuochen](/user/658786) 看完数据范围在来说难度吧
by LuoTianyi_Official @ 2022-08-22 16:02:13
@[Hoshino_kaede](/user/547908) 虽然但是 $1239$ 数据范围 $10^9$ 
by Dr_Gilbert @ 2022-08-22 16:02:21
@[Hoshino_kaede](/user/547908) 这题1e9和1e12没有区别吧
by Larry0101 @ 2022-08-22 16:02:49
都是数位dp啊，1e9暴力同样过不了
by YuRuochen @ 2022-08-22 16:07:36
@[__Ultimium__](/user/424089)
@[Dr_Gilbert](/user/574568)
by YuRuochen @ 2022-08-22 16:11:01
```
#include<bits/stdc++.h>
using namespace std;
char c[10],q[0];
int dp[10][10][10];
void init(){
for(int i=0;i<10;i++) dp[1][i][i]=1;
for(int i=2;i<=9;i++){
for(int j=0;j<10;j++){
for(int k=0;k<10;k++){
if(j==k) dp[i][j][k]=pow(10,i-1);
for(int z=0;z<10;z++) dp[i][j][k]+=dp[i-1][z][k];
}
}
}
}
long long work(char *c,int u){
if(strlen(c)==0) return 0;
int last=0;
long long ans=0;
int len=strlen(c);
for(int i=len-1;i>=0;i--){
int x=c[i]-'0';
for(int j=(i==len-1);j<x;j++) ans+=dp[i+1][j][u];
ans+=x*last*pow(10,i);
if(x==u) last++;
if(!i) ans+=last;
}
for(int i=1;i<len;i++){
for(int j=(i!=1);j<10;j++) ans+=dp[i][j][u];
}
return ans;
}
int main(){
scanf("%s",c);
int len=strlen(c);
for(int i=0;i<len/2;i++) swap(c[i],c[len-i-1]);
init();
for(int i=0;i<10;i++){
if(len==1) printf("%lld\n",work(c,i));
else printf("%lld\n",work(c,i)-!i);
}
return 0;
}
by YuRuochen @ 2022-08-23 12:31:16
以上是1239的代码
by YuRuochen @ 2022-08-23 12:42:39