luoguP2657 [SCOI2009]windy数

旧城等待， 2021-11-02 01:02 266阅读 0赞

和诸位巨佬不同，蒟蒻如我，只能想到怎么统计不满足windy数条件的数

就是个爆搜

定义c\[i\]\[j\]\[k\]表示第i位且前一位为j，k表示是否满足条件

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int maxn=1e5+5;
     4 int tot,e[20];
     5 long long c[20][20][2]; 
     6 int a,b;
     7 template<class t>void red(t &x)
     8 {
     9     int w=1;
    10     x=0;
    11     char ch=getchar();
    12     while(ch>'9'||ch<'0')
    13     {
    14         if(ch=='-')
    15             w=-1;
    16         ch=getchar(); 
    17     }
    18     while(ch>='0'&&ch<='9')
    19     {
    20         x=(x<<3)+(x<<1)+ch-'0';
    21         ch=getchar();
    22     } 
    23     x*=w;
    24 } 
    25 void input()
    26 {
    27     freopen("input.txt","r",stdin);
    28 }
    29 void dv(int x)
    30 {
    31     tot=0;
    32     while(x)
    33     {
    34         e[++tot]=x%10;
    35         x/=10;
    36     }
    37     e[tot+1]=0;
    38 }
    39 long long dfs(int pos,bool limit,bool zero,bool dc,int pre)
    40 {
    41     if(pos==0)
    42         return dc;
    43     if(!limit&&c[pos][pre][dc]!=-1)
    44         return c[pos][pre][dc];
    45     int up=limit?e[pos]:9;
    46     long long ans=0;
    47     for(int i=0;i<=up;++i)
    48         ans+=dfs(pos-1,limit&&(i==up),zero||i,dc||(abs(i-pre)<2&&zero),i);
    49     if(!limit&&zero)
    50         c[pos][pre][dc]=ans;
    51     return ans;
    52 }
    53 long long solve(int x)
    54 {
    55     dv(x);
    56     memset(c,-1,sizeof(c));
    57     return dfs(tot,1,0,0,-1);
    58 }
    59 void read()
    60 {
    61     red(a);
    62     red(b);
    63 }
    64 void work()
    65 {
    66     printf("%lld",b-a+1-solve(b)+solve(a-1));
    67 }
    68 int main()
    69 {
    70     input();
    71     read();
    72     work();
    73     return 0;
    74 }

转载于:https://www.cnblogs.com/Achensy/p/11002152.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/893dd0b6ad544450b00a16acd1ca13b9.png