Codeforces #427 Div2 D
2024-10-20 07:37:08
#427 Div2 D
题意
给出一个字符串,求它的子串中为 \(k-palindrome\) 的个数。
\(1-palindrome\) 要求是一个回文串。
\(k-palindrome (k > 1)\)满足以下条件:
- 是一个回文串
- 它的左右两边是一个不为空的 \((k - 1)-palindromes\) 。
分析
求字符串回文子串个数是一个很经典的题目了,这题变化也不大。
\(dp[i]\) 表示以当前字符结尾的长度为 \(i\) 的字符串 \(k\) 的最大值。
注意 \(2-palindrome\) 同时也是 \(1-palindrome\) 。
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[5005];
int dp[5005];
int ans[5005];
int main() {
scanf("%s", s + 1);
int len = strlen(s + 1);
int sum = 0;
vector<int> v1, v2;
for(int i = 1; i <= len; i++) {
ans[1]++; ans[2]--;
v2.push_back(1);
dp[1] = 1;
if(s[i] == s[i - 1]) {
v2.push_back(2);
ans[1]++; ans[2]--;
ans[2]++; ans[3]--;
dp[2] = 2;
}
for(int j = 0; j < v1.size(); j++) {
int l = v1[j];
if(s[i - l - 1] == s[i]) {
v2.push_back(l + 2);
dp[l + 2] += dp[l / 2 + 1] + 1;
ans[1]++; ans[dp[l + 2] + 1]--;
}
}
memset(dp, 0, sizeof dp);
v1 = v2;
v2.clear();
}
for(int i = 1; i <= len; i++) {
ans[i] += ans[i - 1];
}
for(int i = 1; i <= len; i++) {
printf("%d%c", ans[i], " \n"[i == len]);
}
return 0;
}
最新文章
- xamarin.Android 标记1
- Python中MySQLdb模块的安装
- 添加Mysql到Windows系统服务
- vi基本命令
- JAVA的Random类[转]
- nodejs socket
- work6
- tk资料
- 工作无聊,闲来无事,自己学习 android入门
- 如何在BIOS里设置定时关机?
- Thrift 入门教程
- 系统重启后,mr程序不生成当前时间段的MRx文件问题
- raise ValueError(";Cannot convert {0!r} to Excel";.format(value))
- 学习笔记——在vue中如何配置Jest(一)
- easyui中对数据的判断来显示,formatter控制
- 什么是java OOM?如何分析及解决oom问题?
- bzoj1503 Splay 维护名次数,支持删除
- 冲刺ing-6
- C#修改系统环境变量,调用批处理bat
- 存储器的保护(三)——《x86汇编语言:从实模式到保护模式》读书笔记20