感谢@似水流年 翻译

题意:

如果某个数x修改任意一位就是回文的,那么我们称之为"几乎回文的"

求1~n中有多少个几乎回文的数

PS:回文数也是几乎回文的,因为它们可以将某一位修改为其本身

解法:

dp....数位dp....

不知道为啥cf评测机为啥要耗30ms..很有趣..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[25];
long long dp[25][2][2];
long long dp2[25][2];
long long sum=0;
long long dp_any(int flag,int x,int y=0)
{
    if (dp[x][y][flag]!=-1) return dp[x][y][flag];
    if (x==0)
    {
        dp[x][y][flag]=1;
        return 1;
    }
    long long ans=0;
    if (y==0)
    {
        if (flag)
        {
            if (x==1)
            {
                ans=9;
                dp[x][y][flag]=ans;
                return ans;
            }
            ans+=9*dp_any(0,x-2,0);
            ans+=81*dp_any(0,x-2,1);
        }
        else
        {
            if (x==1)
            {
                ans=10;
                dp[x][y][flag]=ans;
                return ans;
            }
            ans+=10*dp_any(0,x-2,0);
            ans+=90*dp_any(0,x-2,1);
        }
    }
    else
    {
        if (x==1)
        {
            ans=10;
            dp[x][y][flag]=ans;
            return ans;
        }
        ans=10*dp_any(0,x-2,1);
    }
    dp[x][y][flag]=ans;
    return ans;
}
char b[25];
int n;
bool checks()
{
    int i;
    for (i=0;i<n;i++)
    {
        if (a[i]<b[i]) return false;
        if (a[i]>b[i]) return true;
    }
    return true;
}
long long dp_not_any(int flag,int now,int visit=0)
{
    if (dp2[now][visit]!=-1) return dp2[now][visit];
    dp2[now][visit]=0;
    if ((now==0)&&(visit==0))
    {
        int i;
        for (i=0;i<(n+1)/2;i++)
        {
            b[i]=a[i];
            b[n-i-1]=a[i];
        }
        dp2[now][visit]=checks();
        return dp2[now][visit];
    }
    if ((now==0)&&(visit==1)) return 0;
    if (visit==0)
    {
        if (now==1)
        {
            if (flag)
            {
                dp2[now][visit]=a[0]-'0';
                return dp2[now][visit];
            }
            else
            {
                int i;
                for (i=0;i<(n+1)/2;i++)
                {
                    b[i]=a[i];
                    b[n-i-1]=a[i];
                }
                dp2[now][visit]=a[n/2]-'0'+checks();
                return dp2[now][visit];
            }
        }
        else
        {
            dp2[now][visit]=dp_not_any(0,now-2,0);
            dp2[now][visit]+=dp_not_any(0,now-2,1)*9;
            int i;
            for (i=0;i<(n+1)/2;i++)
            {
                b[i]=a[i];
                b[n-i-1]=a[i];
            }
            int t=n-1-(n-now)/2;
            for (i=0;i<10;i++)
            {
                b[t]='0'+i;
                if (b[t]==b[(n-now)/2]) continue;
                dp2[now][visit]+=checks();
            }
            i=(n-now)/2;
            if (flag)
            {
                dp2[now][visit]+=dp_any(0,now-2,0)*(a[i]-'1');
                dp2[now][visit]+=dp_any(0,now-2,1)*(a[i]-'1')*9;
            }
            else
            {
                dp2[now][visit]+=dp_any(0,now-2,0)*(a[i]-'0');
                dp2[now][visit]+=dp_any(0,now-2,1)*(a[i]-'0')*9;
            }
        }
    }
    else
    {
        int i=(n-now)/2;
        if (now==1)
        {
            dp2[now][visit]=a[i]-'0';
            return dp2[now][visit];
        }
        else
        {
            dp2[now][visit]=dp_any(0,now-2,1)*(a[i]-'0');
            dp2[now][visit]+=dp_not_any(0,now-2,1);
        }
    }
    return dp2[now][visit];
}
int main()
{
    freopen("almost.in","r",stdin);
    freopen("almost.out","w",stdout);
    ios::sync_with_stdio(false);
    for (;;)
    {
        scanf("%s",a);
        if (a[0]=='0') break;
        memset(dp,-1,sizeof(dp));
        memset(dp2,-1,sizeof(dp2));
        int i;
        sum=0;
        n=strlen(a);
        for (i=1;i<n;i++)
        {
            sum+=dp_any(1,i);
        }
        sum+=dp_not_any(1,n);
        cout<<sum<<'\n';
    }
    return 0;
}