字符串思维题练习 DAY6 (CF 245H , CF 559B , CF 1731C ， CF1109B）

字符串思维题练习 DAY6 (CF 245H , CF 559B , CF 1731C ， CF1109B)

CF 245 H. Queries for Number of Palindromes（字符串 + dp）

Problem - H - Codeforces

大意：给出一个字符串S (|S| ≤ 5000) , 给出 Q 次询问 ， 每次询问 S 的一个区间 [l , r] , 求区间字符串的回文子串个数。

思路：一开始考虑了 马拉车 ，求出每个位置作为回文中心的最大回文半径 ， 但是这样的话每次询问都要遍历区间[l , r] 去更新每一个回文中心所对应的回文半径 ， 复杂度

$$O(\sum _{i=1}^Q(r_i-l_i))$$

显然是不能接受的 ， 考虑 O(N^2) 预处理 ， O(1) 回答询问

$$ans[i][j]为[l,r]的答案$$

考虑转移

$$ans[l][r]=ans[l][r-1]+pre[l][r]$$

pre[l][r] 是右边界为 r ， 左边界 ≥ l 所有字符串中回文串的个数

$$pre[l][r]=pre[l][r-1]+dp[l][r]$$

dp[l][r] 为 [l , r] 这个区间的字符串是否为回文串

所以显而易见问题就变成了就 dp[l][r] , 有两种求法

第一种 : 区间dp

不难看出我们要求的是一个个区间 ， 且区间之间存在转移关系 ， 所以可以使用区间 dp 进行转移。

初始化：初始化奇回文和偶回文 ， 显然所有长度为一的区间都为回文区间 ， 长度为二的区间判断是否回文即可。

$$转移方程：dp[l][r]|=(dp[l+1][r-1]\&\&(s[l]==s[r]))$$

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define int long long
const int INF = 9e18;
const int N = 5e3 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int ans[N][N] , pre[N][N];
bool dp[N][N];
int n , q;
string s;

signed main(){

	IOS
	cin >> s;
	
	n = s.size();
	
	s = '?' + s;
	
	for(int i = 1 ; i <= n ; i ++) dp[i][i] = 1;
	for(int i = 1 ; i < n ; i ++) dp[i][i + 1] = (s[i] == s[i + 1]);
	
	for(int len = 3 ; len <= n ; len ++) {
		for(int l = 1 ; l <= n ; l ++) {
			int r = l + len - 1;
			dp[l][r] |= (dp[l + 1][r - 1] && (s[l] == s[r]));
		}
	}
	
	for(int r = 1 ; r <= n ; r ++) {
		for(int l = r ; l >= 1 ; l --){
			pre[l][r] = pre[l + 1][r] + dp[l][r];
		}
	}
	
	for(int l = 1 ; l <= n ; l ++) {
		for(int r = l ; r <= n ; r ++) {
			ans[l][r] = ans[l][r - 1] + pre[l][r];
		}
	}
	
	cin >> q;
	
	while(q --) {
		int l , r;
		cin >> l >> r;
		cout << ans[l][r] << "\n";
	}
	
	

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

第二种：马拉车

马拉车的思路比较直接 ， 求出每个回文中心对应的回文半径的长度 ， 以当前回文中心更新即可。

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define int long long
//const int INF = 9e18;
const int N = 5e3 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int ans[N][N] , pre[N][N];
bool dp[N][N];
int n , q , m;
string s , t;

int d[N * 2 + 1];
//给出一个字符串求d[i]数组并返回马拉车串
string manacher(string s){
	
	string now = "#$";
	int n = s.size();
	for(int i = 0 ; i < n ; i ++) now += s[i] , now += '$';
	n = now.size();
	d[1] = 1;
	for(int i = 2 , l , r = 1; i < n ; i ++){
		if(i <= r) d[i] = min(d[r - i + l] , r - i + 1);
		else d[i] = 1;
		while(now[i - d[i]] == now[i + d[i]]) d[i] += 1;
		if(i + d[i] - 1 > r) l = i - d[i] + 1 , r = i + d[i] - 1; 
	}
	return now;	
}

void watch(string s){
	int n = s.size();
	for(int i = 0 ; i < n ; i ++) cout << s[i] << " ";
	cout << "\n"; 
	for(int i = 0 ; i < n ; i ++) cout << d[i] << " ";
	cout << "\n";
}

signed main(){

	IOS
	cin >> s;
	
	n = s.size();
	t = manacher(s);
	m = t.size();
//	watch(s);	
	
	int len = 0 , l = 0 , r = 0;
	
	for(int i = 1 ; i <= m ; i ++) {
		if(i & 1) {//偶回文中心
			len = (d[i] - 1) / 2;
			l = (i - 1) / 2;
			r = (i + 1) / 2;
		} else {
			len = d[i] / 2;
			l = r = i / 2;
		}
		for(int i = 1 ; i <= len ; i ++ , l -= 1 , r += 1) {
			dp[l][r] = 1;
		}
	}
		
	for(int r = 1 ; r <= n ; r ++) {
		for(int l = r ; l >= 1 ; l --){
			pre[l][r] = pre[l + 1][r] + dp[l][r];
		}
	}
	
	for(int l = 1 ; l <= n ; l ++) {
		for(int r = l ; r <= n ; r ++) {
			ans[l][r] = ans[l][r - 1] + pre[l][r];
		}
	}
	
	cin >> q;
	
	while(q --) {
		int l , r;
		cin >> l >> r;
		cout << ans[l][r] << "\n";
	}
	
	

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

CF 559 B. Equivalent Strings（哈希+搜索剪枝）

Problem - B - Codeforces

大意：两个等长的字符串 a , b（条件相等）需要满足以下两个条件其一：

1 : 两个字符串相等

2: 字符串 a 可以分为等长的 a1 , a2 , 字符串 b 可以分为等长的 b1 b2 。满足 a1 与 b1（条件相等）a2 与 b2（条件相等）或者 a1 与 b2 （条件相等） a2 与 b1 （条件相等）。

给出两个登场字符串判断是否条件相等。

思路：不难看出这个条件相等是一个递归的定义 ， 考虑递归搜索，哈希比较区间字符串。不妨计算一下递归搜索的复杂度。

首先考虑搜索的深度 ， 由于每次往下走一层区间的长度减半 ， 所以最多搜索 log(2e5) = 18 层 ， 每次搜索 ， 每个状态会分裂为四个状态即比较(a1 , b1) (a2 , b2) (a1 , b2) (a2 , b1) , 比较的次数为 4^18 = 6e15 , 非常恐怖的复杂度。

考虑搜索剪枝：

剪枝1 ： 两个条件相等的区间字符的种类数和每种的个数相等 ， 考虑前缀和处理 ， O(1) 查询区间的字符个数 ， 每次搜索之前判断一下是否相等。

剪枝2：对于每一层 ， 满足两个条件其中一个当前区间的字符串即为条件相等 ， 不用再去搜另外一颗子树。

加上两个剪枝后实测能跑 900ms ， 时限 2s

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int INF = 9e18;
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

#define ull unsigned long long
const int Base = 131;
ull base[N] , hx[N] , hy[N];
string x , y;
int n;
int cntx[N][2] , cnty[N][2];
//-------------------------------------------------------------
//求[l , r) 的散列值 (从 0 开始) 
inline ull get_x(int l,int r){
	return hx[r] - hx[l] * base[r - l];
}
inline ull get_y(int l,int r){
	return hy[r] - hy[l] * base[r - l];
}

bool ask(int lx , int rx , int ly , int ry) {
	lx += 1;ly += 1;rx += 1;ry += 1;
	return (cntx[rx][0] - cntx[lx - 1][0] != cnty[ry][0] - cnty[ly - 1][0]) || (cntx[rx][1] - cntx[lx - 1][1] != cnty[ry][1] - cnty[ly - 1][1]);
}

/*
哈希 + 递归搜索剪枝
两次剪枝
*/

bool judge(int lx , int rx , int ly , int ry) {
	
	if(get_x(lx , rx + 1) == get_y(ly , ry + 1)) return 1;
	else {
		int len = rx - lx + 1;
		if(len & 1) {
			return 0;
		} else {
			int mid = len / 2;
			bool tag1 = 0 ,  tag2 = 0;
			if(ask(lx , lx + mid - 1 , ly , ly + mid - 1) || ask(lx + mid , rx , ly + mid , ry)) tag1 = 0;
			else tag1 = (judge(lx , lx + mid - 1 , ly , ly + mid - 1) && judge(lx + mid , rx , ly + mid , ry));
			if(tag1) return 1;
			if(ask(lx , lx + mid - 1 , ly + mid , ry) || ask(lx + mid , rx , ly , ly + mid - 1)) tag2 = 0;
			else tag2 = (judge(lx , lx + mid - 1 , ly + mid , ry) && judge(lx + mid , rx , ly , ly + mid - 1));
			if(tag2) return 1;
			return 0;
		}
	}
}

signed main(){

	cin >> x >> y;
	n = x.size();
	base[0] = 1;
	for(int i = 1 ; i <= n ; i ++) base[i] = base[i - 1] * Base;
	
	hx[0] = 0;
	for(int i = 1 ; i <= n ; i ++) {
		hx[i] = hx[i - 1] * Base + x[i - 1];
		cntx[i][0] = cntx[i - 1][0] + (x[i - 1] == 'a');
		cntx[i][1] = cntx[i - 1][1] + (x[i - 1] == 'b');
	}
	
	hy[0] = 0;
	for(int i = 1 ; i <= n ; i ++) {
		hy[i] = hy[i - 1] * Base + y[i - 1];
		cnty[i][0] = cnty[i - 1][0] + (y[i - 1] == 'a');
		cnty[i][1] = cnty[i - 1][1] + (y[i - 1] == 'b');
	}

	if(judge(0 , n - 1 , 0 , n - 1)) {
		cout << "YES\n";
	} else {
		cout << "NO\n";
	}
		
	
	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

CF 1731 C. Even Subarrays（枚举剪枝）

Problem - C - Codeforces

大意：给出一个序列 ， 求有多少个子区间异或和不为平方数。

转化问题 ， 原题 = 总子区间个数 - 异或和为平方数的子区间个数 ， 所以要求异或和为平方数的子区间个数。

思路：显然区间异或和能组成的平方数是有限的 ， 最多有 根号个的 ， 所以我们不妨对于每一个右边界记录合法的左边界的个数 ， 合法的左边界即枚举每一个可能组成的平方数 ，根据 pre[l - 1] = pre[r] ^ x , 求出合法的左边界的前缀状态 ， 计数即可。

$$复杂度O(n\sqrt{n})$$

注意：坑点在于异或和能表示的范围和状态记录的范围数组开的大小 ， 要注意。

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int INF = 9e18;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

/*
ans = all - 区间异或值为平方数的区间个数
*/

int n , t , a[N];
int v[N] , cnt;

signed main(){

	IOS
	cin >> t;
	
	while(t --) {
		cin >> n;
		for(int i = 1 ; i <= n ; i ++) {
			cin >> a[i];
		}
		
		cnt = 0;
		v[++cnt] = 0;
		for(int i = 1 ; i * i <= 2 * n ; i ++) v[++cnt] = i * i;
		
		//注意思考这里的空间为什么开四倍
		vector<int>pre(4 * n + 1);
		int res = 0 , ans = (n + 1) * n / 2 , now = 0;
		pre[0] = 1;
		for(int i = 1 ; i <= n ; i ++) {
			now ^= a[i];
			for(int j = 1 ; j <= cnt ; j ++) {
				res += pre[now ^ v[j]];
			}			
			pre[now] += 1;
		}
		cout << ans - res << "\n";
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

CF 1109 B. Sasha and One More Name（思维）

Problem - B - Codeforces

大意：给出一个回文字符串 ， 求最小的分割次数 k ， 将当前回文串分割为 k + 1 部分 ， 然后重排这 k + 1 部分 ， 能得到一个新的回文字符串。

思路：考虑当前字符串是否存在的一个长度 ≤ len / 2 的前缀位置不是当前字符串的border ， 如果存在 ， 显然 k = 2 的花费就能解决 ， 如果不存在 ， 手模一下发现不可能存在答案。

对于比 k = 2 更优的答案即 k = 1 的情况 ， 考虑暴力枚举分割位置 ， 检验方案是否合理 ， 复杂度O(n^2);

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int INF = 9e18;
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int nex[N];

void init(string s){
	int len = s.size();
	nex[1] = 0;
	for(int i = 2 ; i <= len ; i ++){
		nex[i] = nex[i-1];
		while(nex[i] && s[nex[i]] != s[i-1]) nex[i] = nex[nex[i]];
		nex[i] += (s[i-1] == s[nex[i]]);
	}
}

string s;
int n;

signed main(){

	cin >> s;
	n = s.size();
	init(s);
	
	bool ok = 0;
	int ans = -1;
	
	vector<bool>tag(n + 1);
	int now = nex[n];
	while(now) {
		tag[now] = 1;
		now = nex[now];
	}
	
	string now_s , now_k;
	
	for(int i = 1 ; i < n ; i ++) {
		now_s = s.substr(i) + s.substr(0 , i);
		if(now_s == s) continue;
		now_k = now_s;
		reverse(now_k.begin() , now_k.end());
		if(now_s != now_k) continue;
		ok = 1; 
	}
	
	if(ok == 1) {
		ans = 1;
	} else {
		for(int i = 1 ; i <= n / 2 ; i ++) if(!tag[i]) ans = 2;
	}
	
	
	if(ans == -1) {
		cout << "Impossible\n";
	} else {
		cout << ans << "\n";
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70