2017年10月25日提高組T3 數字問題

NO IMAGE

Description


給出a,b求區間a,b內有多少個數該數的所有子串均不是一個長度大於1的迴文串,比如說123是滿足條件的224則不滿足

Input


第一行:兩個整數a,b

Output


一個整數,表示答案

Hint


【資料規模和約定】
對於20% 的資料,b – a <= 200。
對於40% 的資料,b – a <= 10^5。
對於60% 的資料,b – a <= 10^6。
對於100% 的資料,0 <= a <= b <= 10^18

Solution


最近做題做傻了

這裡很容易想到數位dp,當然可以記憶化搜尋。設f[i][j][k][0/1]為前i位最後一位為k倒數第二位為j,當前這位能不能取到9的答案。對於前導零的情況我們暴力列舉起點就可以了

Code


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define rep(i, st, ed) for (int i = st; i <= ed; i  = 1)
#define drp(i, st, ed) for (int i = st; i >= ed; i -= 1)
#define erg(i, st) for (int i = ls[st]; i; i = e[i].next)
#define fill(x, t) memset(x, t, sizeof(x))
#define min(x, y) ((x)<(y)?(x):(y))
#define ll long long
#define INF 0x3f3f3f3f
#define N 51
#define E 1001
#define L 1001
ll f[N][12][12][2];
inline int read() {
int x = 0, v = 1;
char ch = getchar();
for (; ch < '0' || ch > '9'; v *= (ch == '-')?(-1):(1), ch = getchar());
for (; ch <= '9' && ch >= '0'; (x *= 10)  = ch - '0', ch = getchar());
return x * v;
}
inline void dfs(int dep, int last[], char s[], int len, int lim) {
if (dep == len) {
f[dep][last[0]][last[1]][lim] = 1;
return ;
}
if (f[dep][last[0]][last[1]][lim]) {
return ;
}
int mx = 9;
if (lim) {
mx = s[dep] - '0';
}
rep(i, 0, mx) {
if (i != last[0] && i != last[1]) {
int tar[2] = {last[1], i};
dfs(dep   1, tar, s, len, lim & (i == s[dep] - '0'));
f[dep][last[0]][last[1]][lim]  = f[dep   1][last[1]][i][lim & (i == s[dep] - '0')];
}
}
}
char a[L], b[L];
int main(void) {
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
scanf("%s", a);
scanf("%s", b);
ll ans1 = 0;
ll ans2 = 0;
rep(i, 1, a[0] - '0') {
int last[2] = {11, i};
dfs(1, last, a, strlen(a), (i == (a[0] - '0')));
ans1  = f[1][11][i][(i == a[0] - '0')];
}
rep(st, 1, strlen(a) - 1) {
fill(f, 0);
rep(i, 1, 9) {
int last[2] = {11, i};
dfs(st   1, last, a, strlen(a), 0);
ans1  = f[st   1][11][i][0];
}
}
int flag = false;
rep(i, 1, strlen(a) - 1) {
if (i > 1) {
if (a[i] == a[i - 2]) {
flag = true;
break;
}
}
if (a[i] == a[i - 1]) {
flag = true;
break;
}
}
if (!flag) {
ans1 -= 1;
}
fill(f, 0);
rep(i, 1, b[0] - '0') {
int last[2] = {11, i};
dfs(1, last, b, strlen(b), (i == (b[0] - '0')));
ans2  = f[1][11][i][(i == b[0] - '0')];
}
rep(st, 1, strlen(b) - 1) {
fill(f, 0);
rep(i, 1, 9) {
int last[2] = {11, i};
dfs(st   1, last, b, strlen(b), 0);
ans2  = f[st   1][11][i][0];
}
}
std:: cout << ans2 - ans1 << std:: endl;
return 0;
}