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

news/2025/2/21 7:38:57/

字符串思维题练习 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 ( ∑ i = 1 Q ( r i − l i ) ) O(\sum_{i=1}^{Q}(r_i-l_i) ) O(i=1∑Q​(ri​−li​))

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

a n s [ i ] [ j ] 为 [ l , r ] 的答案 ans[i][j] ~为[l , r]的答案 ans[i][j] 为[l,r]的答案

考虑转移

a n s [ l ] [ r ] = a n s [ l ] [ r − 1 ] + p r e [ l ] [ r ] ans[l][r]=ans[l][r-1]+pre[l][r] ans[l][r]=ans[l][r−1]+pre[l][r]

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

p r e [ l ] [ r ] = p r e [ l ] [ r − 1 ] + d p [ l ] [ r ] pre[l][r] = pre[l][r-1]+dp[l][r] pre[l][r]=pre[l][r−1]+dp[l][r]

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

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

第一种 : 区间dp

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

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

转移方程： d p [ l ] [ r ] ∣ = ( d p [ l + 1 ] [ r − 1 ] & & ( s [ l ] = = s [ r ] ) ) 转移方程：dp[l][r] |= (dp[l + 1][r - 1] ~~\&\&~~ (s[l] == s[r])) 转移方程：dp[l][r]∣=(dp[l+1][r−1]  &&  (s[l]==s[r]))

#include<bits/stdc++.h>
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(){IOScin >> 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);

第二种：马拉车

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

#include<bits/stdc++.h>
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(){IOScin >> 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);

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<bits/stdc++.h>
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);

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

Problem - C - Codeforces

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

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

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

复杂度 O ( n n ) 复杂度O(n\sqrt n) 复杂度O(nn ​)

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

#include<bits/stdc++.h>
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(){IOScin >> 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);

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<bits/stdc++.h>
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);

http://www.ppmy.cn/news/1156135.html

相关文章

简单谈谈我参加计算机二级C语言的考试感受

简单谈谈我参加计算机二级C语言的考试感受

简单谈谈我参加计算机二级C语言的考试感受 概要考试感受小结 概要 计算机二级c语言主要内容是熟练掌握C语言基础语法&#xff0c;了解常用数据结构和算法&#xff0c;能够使用C语言进行程序设计&#xff0c;编写简单的应用程序。 计算机二级C语言试卷类型&#xff1a; 选择题…
阅读更多...
机器学习 | Python实现GA-XGBoost遗传算法优化极限梯度提升树特征分类模型调参

机器学习 | Python实现GA-XGBoost遗传算法优化极限梯度提升树特征分类模型调参

机器学习 | Python实现GA-XGBoost遗传算法优化极限梯度提升树特征分类 目录 机器学习 | Python实现GA-XGBoost遗传算法优化极限梯度提升树特征分类基本介绍模型描述程序设计参考资料基本介绍 XGBoost的核心算法思想基本就是： 不断地添加树，不断地进行特征分裂来生长一棵树，每…
阅读更多...
密码学二: md5 网站服务器与用户通信过程 ca原理 签名原理 Flame 病毒原理

密码学二: md5 网站服务器与用户通信过程 ca原理 签名原理 Flame 病毒原理

md5被破解? MD5&#xff08;Message Digest Algorithm 5&#xff09;是一个较早的哈希函数&#xff0c;但由于其弱点和漏洞&#xff0c;它已经被认为不再适合用于安全性要求较高的应用。MD5的一些安全性问题包括&#xff1a; 碰撞攻击&#xff1a; MD5已经被证明容易受到碰撞攻…
阅读更多...
SpringSecurity源码学习二：异常处理

SpringSecurity源码学习二：异常处理

目录 1. 原理2. 组件3. ExceptionTranslationFilter3.1 默认过滤器顺序3.2 ExceptionTranslationFilter源码3.2.1 AuthenticationException异常3.2.2 AccessDeniedException异常 总结 1. 原理 Spring Security 异常处理的原理是通过一系列的异常处理器来处理在安全验证和授权过…
阅读更多...
华为---企业WLAN组网基本配置示例---AC+AP组网

华为---企业WLAN组网基本配置示例---AC+AP组网

ACAP组网所需的物理条件 1、无线AP---收发无线信号&#xff1b; 2、无线控制器(AC)---用来控制管理多个AP&#xff1b; 3、PoE交换机---能给AP实现网络连接和供电的交换机&#xff1b; 4、授权&#xff1a;默认AC管理的AP数量有限&#xff0c;买授权才能管控更多AP。 WLAN创建…
阅读更多...
Ubuntu22常用软件

Ubuntu22常用软件

别存太多重要东西在Ubuntu &#xff0c;硬盘损坏就麻烦 Tweaks自定义UI sudo apt intall gnome-tweaks为了方便管理和添加&#xff0c;还需添加&#xff1a; sudo apt install gnome-shell-extension-prefs gnome-shell-extension-manager -y1.打开Extension应用&#xff0c;添…
阅读更多...
vue3后台管理框架之集成sass

vue3后台管理框架之集成sass

我们目前在组件内部已经可以使用scss样式,因为在配置styleLint工具的时候，项目当中已经安装过sass sass-loader,因此我们再组件内可以使用scss语法！！！需要加上lang="scss" <style scoped lang="scss"></style> 接下来我们为项目添加一些…
阅读更多...
Qt 布局(QSplitter 类QDockWidget 类) 总结

Qt 布局(QSplitter 类QDockWidget 类) 总结

一、QSplitter 类(窗口分割) QSplitter类是一个Qt框架提供的基础窗口控件类&#xff0c;用于分割窗口&#xff0c;使得用户可以通过拖动分隔条来调节子窗口的大小。QSplitter在用户界面设计中非常常见&#xff0c;经常用于划分窗口区域&#xff0c;使得程序可以同时显示多个子…
阅读更多...
最新文章

Copyright @ 2022~2023