2 条题解

  • 0
    @ 2025-10-8 17:15:00
    #include<bits/stdc++.h> 
    using namespace std;
    const int N=20;
    int f[N][15], a[N]; //f[i][j]表示位数为i,最高位的数是j的不降数的个数
    int calc(int x){ //计算[0, x]区间内的不降数
        if(x==0) return 1;  //0也是不降数
        int len=0, last=0, ans=0; //last是上一位的数(更高位
        while(x>0) a[++len]=x%10, x/=10;
        for(int i=len; i>=1; i--){
            for(int j=last; j<a[i]; j++) 
            //<a[i]是因为这样才能保证枚举的数不超过x
                ans+=f[i][j];   
            if(last>a[i]) break; //再往后计算的数就不是不降数了
            last=a[i];
            if(i==1) ans++; //x本身就是不降数
        }
        return ans;
    }
    int main(){
        //freopen("a.in", "r", stdin);
        int a, b; 
        memset(f, 0, sizeof(f));
        for(int i=0; i<=9; i++) f[1][i]=1;
        for(int t=2; t<=15; t++){ //枚举位数
            for(int i=0; i<=9; i++){
                for(int j=i; j<=9; j++)
                    f[t][i]+=f[t-1][j]; 
                //当前个位数为i,位数为t加上个位数为j,位数为t-1的不降数
                //(其实相当于接后面
            }
        }
        while(scanf("%d%d", &a, &b)!=EOF){
            printf("%d\n", calc(b)-calc(a-1)); //求区间
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 17:14:52
      #include<bits/stdc++.h> 
      using namespace std;
      const int N=20;
      int f[N][15], a[N]; //f[i][j]表示位数为i,最高位的数是j的不降数的个数
      int calc(int x){ //计算[0, x]区间内的不降数
          if(x==0) return 1;  //0也是不降数
          int len=0, last=0, ans=0; //last是上一位的数(更高位
          while(x>0) a[++len]=x%10, x/=10;
          for(int i=len; i>=1; i--){
              for(int j=last; j<a[i]; j++) 
              //<a[i]是因为这样才能保证枚举的数不超过x
                  ans+=f[i][j];   
              if(last>a[i]) break; //再往后计算的数就不是不降数了
              last=a[i];
              if(i==1) ans++; //x本身就是不降数
          }
          return ans;
      }
      int main(){
          //freopen("a.in", "r", stdin);
          int a, b; 
          memset(f, 0, sizeof(f));
          for(int i=0; i<=9; i++) f[1][i]=1;
          for(int t=2; t<=15; t++){ //枚举位数
              for(int i=0; i<=9; i++){
                  for(int j=i; j<=9; j++)
                      f[t][i]+=f[t-1][j]; 
                  //当前个位数为i,位数为t加上个位数为j,位数为t-1的不降数
                  //(其实相当于接后面
              }
          }
          while(scanf("%d%d", &a, &b)!=EOF){
              printf("%d\n", calc(b)-calc(a-1)); //求区间
          }
          return 0;
      }
      • 1

      信息

      ID
      339
      时间
      1000ms
      内存
      512MiB
      难度
      10
      标签
      递交数
      1
      已通过
      1
      上传者