luoguP6754 [BalticOI 2013 Day1] Palindrome-Free Numbers

luoguP6754 [BalticOI 2013 Day1] Palindrome-Free Numbers

简述题意：

定义回文串为正着读反着读都一样的数字串，如果一个数字串的一个长度大于 \(1\) 的子串也为回文串的话，那么我们也定义这个数字串为回文串。

所以不是回文串的数字为 非回文串 ，求区间 \([l, r]\) 内有多少个 非回文串 ,数据范围： \(0 \le l \le r \le 10^{18}\)

Solution:

设 \(f[i][j][k]\) 表示长度为 \(i\) 最高位为 \(j\) 次高位为 \(k\) 的非回文串的个数

因为只要满足子串是回文数它就是回文串，所以判断比较的时候只需要与前两位数比较就好啦

转移方程：

实际意义：表示区间 \([jk000\cdots,jk999\cdots]\) 的非回文数的和

对于求 \(ans_{l, r}\) 可以转化为 \(ans_{1, r} - ans_{1, l - 1}\)

求 \(ans_{l,r}\) 时的策略：

设 \(len\) 为 \(r\) 的位数，\(a[len]\) 中存 \(r\) 的每一位

1、对于所有长度小于 \(len\) 的 \(f\) ， \(ans += \sum_{1 \le j \le 9}^{2 \le i \le len - 1} f[i][j][k](0 \le k \le 9)\)

2、对于长度小于等于 \(len\) 位且最高位小于 \(a[i]\) 的 \(f\)，\(ans += f[i][j][k] (0 \le k \le 9)\) ，加的过程中注意判断此时是否是非回文串

3、因为 \(2\) 枚举不到最后的个位数，所以要在最后单独判断一遍

本人在理解上的一个很傻逼的误区：

主函数最后的那个 \(for\) 循环是判断 \(l\) 是否是非回文串，因为前面已经求了 \(ans_{1, r}\) 和 \(ans_{1, l}\) ,两者相减所求区间是 \(ans_{l + 1, r}\) 并没有取到 \(l\) ，按理说执行 \(solve(l - 1)\) 是可以解决的，但因为这里用的字符数组读入，所以难免有锅（我为这理解了一下午）

Code

/*

Work by: Suzt_ilymics

Knowledge: ??

Time: O(??)

*/

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#define LL long long

using namespace std;

const int MAXN = 1010;

LL read(){

	LL s = 0, w = 1;

	char ch = getchar();

	while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar();	}

	while(ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + ch - '0', ch = getchar();

	return s * w;

} 

char l[MAXN], r[MAXN];

LL f[MAXN][13][13];

LL a[MAXN];

void init(){

	for(int i = 2; i <= 1001; ++i){

		for(int j = 0; j <= 9; ++j){

			for(int k = 0; k <= 9; ++k){

				if(j == k) continue;//如果相邻两个元素一样，那么一定是回文串，直接跳过

				for(int a = 0; a <= 9; ++a){

					if(j != a && a != k)//如果不是2回文也不是3回文

						f[i][j][k] += f[i - 1][k][a];

				}

				if(i == 2) f[i][j][k]++;//如果长度为2，一定不是

			}

		}

	}

}

LL solve(char s[]){

	memset(a, 0, sizeof(a));

	LL tot = 0;

	bool t = 1;

	int len = strlen(s);

	LL ans = 0, last1 = -1, last2 = -1, sum = 0;

	for(int i = len; i >= 1; --i){

		a[i] = s[len - i] - '0';//把个位放前面

		sum = (sum << 1) + (sum << 3) + a[i];//

	}

	if(len == 1) return sum + 1;//如果长度为1，那么不用判断了

	ans += 10;//算上长度为1的那10个数

	for(int i = 2; i < len; ++i){//老套路把满着的先加上

		for(int j = 1; j <= 9; ++j){

			for(int k = 0; k <= 9; ++k){

				ans = ans + f[i][j][k];

			}

		}

	}

	for(int i = len; i >= 2; i--){

		for(int j = 0; j < a[i]; ++j){

			if(i == len && j == 0) continue;//首位是0就跳过

			for(int k = 0; k <= 9; ++k){

				if(last1 != j && last2 != j && j != k && last1 != k){

					ans = ans + f[i][j][k];

				}

			}

		}

		if(last1 == a[i] || last2 == a[i]) {//上一位和上两位

			t = 0; break;

		}

		last2 = last1, last1 = a[i];//更新

	}

	if(t) {//如果没有中途退出

		for(int i = 0; i <= a[1]; ++i){//最后一位剩下的那一点

			if(i != last1 && i != last2) ans++;

		}

	}

	return ans;

}

int main()

{

	init();

	cin >> l >> r;

	LL ans = solve(r) - solve(l);

	int t = strlen(l), flag = 0;

	for(int i = 1; i < t; ++i){

		if(l[i] == l[i - 1] || (l[i] == l[i - 2] && i > 1)) {

			flag = 1;

			break;

		}

	}

	if(!flag) ans++;

	printf("%lld", ans);

	return 0;

}