思路:每位枚举1,0,8,然后对于小于了的情况可以直接计算出答案,对于等于的就搜下去,这样等于只需要在等于的一条路径上搜索,效率还是很高的
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int d[3] = {0, 1, 8}; char a[50], b[50]; ll pow3[45]; int bit[45], bn; void get(char *x) { bn = strlen(x); for (int i = 0; i < bn; i++) bit[i] = x[i] - '0'; } ll dfs(int l, int r, int s, int flag) { if (l > r) return !flag; ll ans = 0; for (int i = s; i < 3; i++) { if (d[i] < bit[l]) ans += pow3[(max(0, r - l - 1) + 1) / 2]; else if (d[i] == bit[l]) { if (bit[r] < d[i]) flag = 1; else if (bit[r] > d[i]) flag = 0; ans += dfs(l + 1, r - 1, 0, flag); } else break; } return ans; } ll check() { int n = strlen(a); for (int i = 0; i <= n / 2; i++) { if (a[i] != '0' && a[i] != '1' && a[i] != '8') return 0; if (a[i] != a[n - i - 1]) return 0; } return 1; } ll solve(char *x) { get(x); ll ans = dfs(0, bn - 1, 1, 0); ans++; for (int i = bn - 1; i >= 1; i--) ans += pow3[(i + 1) / 2] / 3 * 2; return ans; } int cas; int main() { pow3[0] = 1; for (int i = 1; i < 45; i++) pow3[i] = pow3[i - 1] * 3; scanf("%d", &cas); while (cas--) { scanf("%s%s", a, b); printf("%lld\n", solve(b) - solve(a) + check()); } return 0; }