【CF245H】【Queries for Number of Palindromes】

2024-08-31 16:58

本文主要是介绍【CF245H】【Queries for Number of Palindromes】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

H. Queries for Number of Palindromes
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You've got a string s = s1s2... s|s| of length |s|, consisting of lowercase English letters. There also are q queries, each query is described by two integers li, ri (1 ≤ li ≤ ri ≤ |s|). The answer to the query is the number of substrings of string s[li... ri], which are palindromes.

String s[l... r] = slsl + 1... sr (1 ≤ l ≤ r ≤ |s|) is a substring of string s = s1s2... s|s|.

String t is called a palindrome, if it reads the same from left to right and from right to left. Formally, if t = t1t2... t|t| = t|t|t|t| - 1... t1.

Input

The first line contains string s (1 ≤ |s| ≤ 5000). The second line contains a single integer q (1 ≤ q ≤ 106) — the number of queries. Next q lines contain the queries. The i-th of these lines contains two space-separated integers li, ri (1 ≤ li ≤ ri ≤ |s|) — the description of the i-th query.

It is guaranteed that the given string consists only of lowercase English letters.

Output

Print q integers — the answers to the queries. Print the answers in the order, in which the queries are given in the input. Separate the printed numbers by whitespaces.

Sample test(s)
input
caaaba
5
1 1
1 4
2 3
4 6
4 5
output
1
7
3
4
2


注意当s[i] == s[j] 时候不能直接 +1  要判断这个是个回文串才可以,, 因为必需用s[i] 和 s[j]  abca 就是个例子



#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;int T;
typedef long long ll;
char s[5002];
ll dp[5002][5002];
int main()
{memset(s,0,sizeof(s));scanf("%s",s);int len =strlen(s);for(int i=1;i<=len;i++){dp[i][i]  = 1;if(i - 1 >= 1)dp[i-1][i] = ((s[i-1] == s[i-1-1]) ? 1 : 0);}for(int j=2;j<=len;j++){for(int i=j-2;i>=1;i--){if(s[i-1] == s[j-1])dp[i][j] += dp[i+1][j-1];}}for(int j=2;j<=len;j++){for(int i=j-1;i>=1;i--){dp[i][j] = (dp[i][j] + dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]);}}scanf("%d",&T);int l,r;while(T --){scanf("%d%d",&l,&r);printf("%I64d\n",dp[l][r]);}return 0;
}

这篇关于【CF245H】【Queries for Number of Palindromes】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1124470

相关文章

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

Jenkins 通过 Version Number Plugin 自动生成和管理构建的版本号

步骤 1:安装 Version Number Plugin 登录 Jenkins 的管理界面。进入 “Manage Jenkins” -> “Manage Plugins”。在 “Available” 选项卡中搜索 “Version Number Plugin”。选中并安装插件,完成后可能需要重启 Jenkins。 步骤 2:配置版本号生成 打开项目配置页面。在下方找到 “Build Env

【UVA】11584-Partitioning by Palindromes(动态规划)

动态规划。 如果 j + 1 ~ i是回文,那么 dp[i] = min=(dp[j] + 1);  判断j + 1~ i是不是回文可以进行预处理,方法是枚举中心,之后向两边伸张,(需要枚举2次,一次是偶数回文,一次是奇数回文) 13993253 11584 Partitioning by Palindromes Accepted C++ 0.132 2014-08-05 08:2

【Hdu】Minimum Inversion Number(逆序,线段树)

利用线段树在nlogn的时间复杂度内求一段数的逆序。 由于给的序列是由0 ~ n -1组成的,求出初始的逆序之后可以递推出移动之后的逆序数。 #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const in

【JavaScript】基本数据类型与引用数据类型区别(及为什么String、Boolean、Number基本数据类型会有属性和方法?)

基本数据类型   JavaScript基本数据类型包括:undefined、null、number、boolean、string。基本数据类型是按值访问的,就是说我们可以操作保存在变量中的实际的值。 1)基本数据类型的值是不可变的 任何方法都无法改变一个基本类型的值,比如一个字符串: var name = "change";name.substr();//hangconsole.log

ORA-24067: exceeded maximum number of subscribers for queue ADMIN.SMS_MT_QUEUE

临时处理办法: delete from aq$_ss_MT_tab_D;delete from aq$_ss_MT_tab_g;delete from aq$_ss_MT_tab_h;delete from aq$_ss_MT_tab_i;delete from aq$_ss_MT_tab_p;delete from aq$_ss_MT_tab_s;delete from aq$

SQLSERVER排名函数RANK,DENSE_RANK,NTILE,ROW_NUMBER

SQL SERVER排名函数RANK,DENSE_RANK,NTILE,ROW_NUMBER 前言 本文意于用实例数据帮助理解SQL SERVER排名函数RANK,DENSE_RANK,NTILE,ROW_NUMBER。 准备工作 创建测试表:   ? 1 2 3 4 5 create table test( id int identity(1,1)

[LeetCode] 137. Single Number II

题:https://leetcode.com/problems/single-number-ii/ 题目大意 给定array,其中有一个元素只出现了1次,其他元素都出现了3次。 思路 求和 减去 (set(array)*3 - array)/2 作为答案。 class Solution {public int singleNumber(int[] nums) {Set<Long> se

Oracle - ORA-01789: Query block has incorrect number of result columns

一、原因     这个错误一般是在执行表之间的相加(union),相减(minus)等SQL语句时,两个个查询块具有不一致的结果列数所导致的。 二、方案     只要将两段SQL语句的列数调整为一致就可以解决。使用union时,要注意数据库字段的格式要一致,如varchar和nvarchar是不一样的。