社区讨论
求调
P2602[ZJOI2010] 数字计数参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mkmhw2te
- 此快照首次捕获于
- 2026/01/20 19:12 4 周前
- 此快照最后确认于
- 2026/01/24 10:26 4 周前
rt,还有,请问数位DP为什么要用dfs写?具体怎么写?
CPP#include<bits/stdc++.h>
using namespace std;
long long l,r,x,top,num[13],mi[13],ans[2][10];
int main(){
mi[0]=1;
for(int i=1;i<=13;i++) mi[i]=mi[i-1]*10;
cin >> l >> r;
x=r;
top=0;
while(x){
top++;
x/=10;
}
x=r;
for(int i=top;i>=1;i--){
num[i]=x%10;
x/=10;
}
for(int i=1;i<=top;i++){
long long p=0,q=0,f=0;
for(int j=1;j<i;j++) p=p*10+num[j];
for(int j=i+1;j<=top;j++) q=q*10+num[j];
if(p==0) p=1,f=1;
if(i>1) for(int j=0;j<num[i];j++) ans[0][j]+=(p+1)*mi[top-i];
else for(int j=1;j<num[i];j++) ans[0][j]+=p*mi[top-i];
for(int j=num[i]+1;j<=9;j++) ans[0][j]+=(p-1)*mi[top-i];
if(f) ans[0][num[i]]+=q+1;
else ans[0][num[i]]+=p*mi[top-i]+q+1;
/*
for(int i=0;i<=9;i++) cout << ans[0][i] << " ";
cout << "\n";
*/
}
x=l-1;
top=0;
while(x){
top++;
x/=10;
}
x=l-1;
for(int i=top;i>=1;i--){
num[i]=x%10;
x/=10;
}
if(l==1){
ans[1][0]=1;
}
for(int i=1;i<=top;i++){
long long p=0,q=0,f=0;
for(int j=1;j<i;j++) p=p*10+num[j];
for(int j=i+1;j<=top;j++) q=q*10+num[j];
if(p==0) p=1,f=1;
if(i>1) for(int j=0;j<num[i];j++) ans[1][j]+=(p+1)*mi[top-i];
else for(int j=1;j<num[i];j++) ans[1][j]+=p*mi[top-i];
for(int j=num[i]+1;j<=9;j++) ans[1][j]+=(p-1)*mi[top-i];
if(f) ans[1][num[i]]+=q+1;
else ans[1][num[i]]+=p*mi[top-i]+q+1;
/*
for(int i=0;i<=9;i++) cout << ans[1][i] << " ";
cout << "\n";
*/
}
/*
cout << "\n";
for(int i=0;i<=9;i++) cout << ans[0][i] << " ";
cout << "\n";
for(int i=0;i<=9;i++) cout << ans[1][i] << " ";
cout << "\n";
*/
for(int i=0;i<=9;i++) cout << ans[0][i]-ans[1][i] << " ";
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...