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[20],dp[20][11][2][2]; inline long long go(long long n){if(!n)return 0;long long m=n,i,j,k,cnt=0;long long h=10,lo=1;while(1){if(m<h&&m>=lo)break;h*=10,lo*=10;}while(lo){a[++cnt]=m/lo;m%=lo;lo/=10;}memset(dp,0,sizeof(dp));dp[0][0][0][0]=1;a[0]=0;for(i=1;i<=cnt;i++){for(j=0;j<=a[i];j++){k=a[i-1];if(abs(j-k)>=2){if(j<a[i])dp[i][j][1][1]+=dp[i-1][k][0][1];else dp[i][j][0][1]+=dp[i-1][k][0][1];}if(!k){if(j<a[i]&&j)dp[i][j][1][1]+=dp[i-1][0][0][0];else if(j<a[i]&&!j)dp[i][j][1][0]+=dp[i-1][0][0][0];else if(!j)dp[i][j][0][0]+=dp[i-1][0][0][0];else dp[i][j][0][1]+=dp[i-1][0][0][0];}}for(j=0;j<=9;j++){for(k=0;k<=9;k++){if(abs(j-k)>=2){dp[i][j][1][1]+=dp[i-1][k][1][1];}if(!k){if(j)dp[i][j][1][1]+=dp[i-1][k][1][0];else dp[i][j][1][0]+=dp[i-1][k][1][0];}}}}long long ans=dp[cnt][a[cnt]][0][1];for(i=0;i<=9;i++)ans+=dp[cnt][i][1][1];return ans; } int main(){long long a,b;scanf("%lld%lld",&a,&b);cout<<go(b)-go(a-1)<<endl;return 0; }

转载于:https://www.cnblogs.com/yzxverygood/p/9491662.html

总结

以上是生活随笔为你收集整理的p2657 windy数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。