p2657 windy数

分析

首先这是一个询问一段区间内的个数的问题，所以我们可以用差分的思想用sum(R)-sum(L-1)。然后我们考虑如何求出sum(n)，我们用dp[i][j][k][t]表示考虑到第i位，最后一个数是j，是否已经小于n和是否已经考虑完前导零。至于转移和一般的套路一样，详见代码。注意最后记得考虑n自己。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

long long a[],dp[][][][];

inline long long go(long long n){

      if(!n)return ;

      long long m=n,i,j,k,cnt=;

      long long h=,lo=;

      while(){

          if(m<h&&m>=lo)break;

          h*=,lo*=;

      }

      while(lo){

          a[++cnt]=m/lo;

          m%=lo;

          lo/=;

      }

      memset(dp,,sizeof(dp));

      dp[][][][]=;

      a[]=;

      for(i=;i<=cnt;i++){

          for(j=;j<=a[i];j++){

            k=a[i-];

            if(abs(j-k)>=){

              if(j<a[i])dp[i][j][][]+=dp[i-][k][][];

                else dp[i][j][][]+=dp[i-][k][][];

            }

            if(!k){

              if(j<a[i]&&j)dp[i][j][][]+=dp[i-][][][];

                else if(j<a[i]&&!j)dp[i][j][][]+=dp[i-][][][];

                else if(!j)dp[i][j][][]+=dp[i-][][][];

                else dp[i][j][][]+=dp[i-][][][];

            }

          }

          for(j=;j<=;j++){

            for(k=;k<=;k++){

              if(abs(j-k)>=){

                dp[i][j][][]+=dp[i-][k][][];

              }

            if(!k){

                if(j)dp[i][j][][]+=dp[i-][k][][];

                  else dp[i][j][][]+=dp[i-][k][][];

              }

            }

          }

      }

      long long ans=dp[cnt][a[cnt]][][];

      for(i=;i<=;i++)

        ans+=dp[cnt][i][][];

      return ans;

}

int main(){

      long long a,b;

      scanf("%lld%lld",&a,&b);

      cout<<go(b)-go(a-)<<endl;

      return ;

}

巴特西

p2657 windy数

最新文章

热门文章