"蔚来杯"2022牛客暑期多校训练营5补题 B, C, F, G, H, K
2022/8/3 23:25:28
本文主要是介绍"蔚来杯"2022牛客暑期多校训练营5补题 B, C, F, G, H, K,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
G KFC Crazy Thursday 马拉车算法
题意:
给定一个字符串,问有多少个以K或者F或者C结尾的回文子串。
思路:
马拉车算法,求出len。
利用区间加法获得总和即可。
也就是(直接看代码更容易理解)对于新串在i处“+1”,在i+len[i]+1处“-1”。因为这个区间内的字符都有某个以他为结尾的回文串。
代码:
#include <bits/stdc++.h> #define endl '\n' #define int long long #define pii pair<int, int> #define pll pair<int, int> #define ull unsigned long long using namespace std; const int N = 2e7 + 10; char a[N], b[N]; int p[N]; int n; void init() { int k = 0; b[k++] = '$', b[k++] = '#'; for (int i = 0; i < n; i++) b[k++] = a[i], b[k++] = '#'; b[k++] = '^'; n = k; } void manacher() { int mr = 0, mid; for (int i = 0; i < n; i++) { if (i < mr) p[i] = min(p[mid * 2 - i], mr - i); else p[i] = 1; while (b[i - p[i]] == b[i + p[i]]) p[i]++; if (i + p[i] > mr) { mr = i + p[i]; mid = i; } } } int d[N]; int cnt[128]; void solve() { cin>>n; cin >> a; init(); manacher(); for (int i = 0; i < n; i++) { int L = i, R = i + p[i] - 1; d[L]++; d[R + 1]--; } int pre = 0; for (int i = 0; i <n; i++) { pre += d[i]; cnt[b[i]] += pre; } cout << cnt['k'] << " " << cnt['f'] << " " << cnt['c'] << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) solve(); return 0; }
这篇关于"蔚来杯"2022牛客暑期多校训练营5补题 B, C, F, G, H, K的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享