简单数位DP

情况数很多，细节很多

记忆化搜索设DP[pos][sum1][sum2][Max1][Max2][flag]
表示dfs到第i位数，奇数位和为sum1，偶数位和为sum2,sum1-sum2差的最大减小值为Max2,sum2-sum1差的最大减小值为Max1，有无前导0为flag.
然后就是细节处理，处理成功就可以AC了。
当然别忘记题目中奇偶等和数的位数为偶数，所以几乎奇偶等合数位数也为偶数。
详细见代码

#include<iostream>
#include<cstring>
#include<cstdio>
//#include<stdafx.h>VS2017自带头文件，请无视
using namespace std;
int len[11];
int dp[11][100][100][10][10][2];
int max(int a, int b)
{
    return a > b ? a : b;
}
int dfs(int pos, int sum1, int sum2, int Max1, int Max2, int limit, int flag)
{
    if (pos == 0)
    {
        if (sum1 == sum2)return 0;
        if (sum1 > sum2)return sum1 - sum2 <= Max2;
        else return sum2 - sum1 <= Max1;
    }
    if (!limit&&dp[pos][sum1][sum2][Max1][Max2][flag] != -1)return dp[pos][sum1][sum2][Max1][Max2][flag];
    int temp = 0;
    for (int i = 0; i <= 9; i++)
    {
        if (limit&&i > len[pos])break;
        if ((pos & 1) && i > 0 && flag)continue;
        if (pos & 1)temp += dfs(pos - 1, sum1 + i, sum2, flag &&i == 0 ? Max1 : max(Max1, 9 - i), flag? max(Max2, i-1): max(Max2, i), limit&&i == len[pos], flag&&i == 0);
        else temp += dfs(pos - 1, sum1, sum2 + i, flag?max(Max1, i-1):max(Max1,i), flag&&i == 0 ? Max2 : max(Max2, 9 - i), limit&&i == len[pos], flag&&i == 0);
    }
    if (!limit)return dp[pos][sum1][sum2][Max1][Max2][flag] = temp;
    return temp;

}
int calc(int n)
{
    if (n == -1 || n == 0)return 0;
    int cnt=0;
    while (n)
    {
        len[++cnt] = n % 10;
        n = n / 10;
    }
    return dfs(cnt, 0, 0, 0, 0, 1, 1);
}
int main()
{
    memset(dp, -1, sizeof(dp));
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d", calc(r) - calc(l-1));
  return 0;
}