题目
首先我们可以非常轻松地预处理出\(f_{i,j}\)表示一个最高位为\(i\)位且该位为\(j\)的windy数的个数。
然后我们可以利用经典容斥把答案变成求\([1,x]\)的windy数个数。
设\(x\)有\(len\)位，从低到高位分别是\(a_1,\cdots,a_{len}\)
首先我们把位数小于\(len\)的答案求出。
然后求出位数等于\(len\)且首位小于\(a_{len}\)的答案。
然后我们从大到小枚举\(len\sim i-1\)位相等，\(i\)位不等，枚举第\(i\)位从\(1\)到\(a_{i}-1\)，如果第\(i\)位的数\(j\)与\(a_{i+1}\)差的绝对值\(\ge2\)，那么这里的答案就是\(f_{i,j}\)。
#include<bits/stdc++.h>
using namespace std;
int f[11][11],a[11];
int abs(int a){return a<0? -a:a;}
void init()
{
for(int i=0;i<=9;++i) f[1][i]=1;
for(int i=2,j,k;i<=10;++i) for(j=0;j<=9;++j) for(k=0;k<=9;++k) if(abs(j-k)>=2) f[i][j]+=f[i-1][k];
}
int cal(int x)
{
int i,j,len=0,ans=0;
while(x) a[++len]=x%10,x/=10;
for(i=1;i<len;++i) for(j=1;j<=9;++j) ans+=f[i][j];
for(i=1;i<a[len];++i) ans+=f[len][i];
for(i=len-1;i;--i)
{
for(j=0;j<a[i];++j) if(abs(j-a[i+1])>=2) ans+=f[i][j];
if(abs(a[i+1]-a[i])<2) break;
}
return ans;
}
int main(){int a,b;init();cin>>a>>b;cout<<cal(b+1)-cal(a);}
Luogu P2657 [SCOI2009]windy数
标签：
原文地址：https://www.cnblogs.com/cjoierShiina-Mashiro/p/11729087.html
