社区讨论

求调

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 条回复,欢迎继续交流。

正在加载回复...