上传到ftp网站模板,佛山市做网站,外网如何查看局域网建设的网站,公司网站建设基本流程Queries for Number of Palindromes - 洛谷
# Queries for Number of Palindromes
## 题面翻译
题目描述
给你一个字符串s由小写字母组成#xff0c;有q组询问#xff0c;每组询问给你两个数#xff0c;l和r#xff0c;问在字符串区间l到r的字串中#xff0c;包含多少…Queries for Number of Palindromes - 洛谷
# Queries for Number of Palindromes
## 题面翻译
题目描述
给你一个字符串s由小写字母组成有q组询问每组询问给你两个数l和r问在字符串区间l到r的字串中包含多少回文串。
输入格式
第1行给出ss的长度小于5000 第2行给出q(1q10^6) 第2至2q行 给出每组询问的l和r
输出格式
输出每组询问所问的数量。
## 题目描述
Youve got a string $ ss_{1}s_{2}...\ s_{|s|} $ of length $ |s| $ , consisting of lowercase English letters. There also are $ q $ queries, each query is described by two integers $ l_{i},r_{i} $ $ (1l_{i}r_{i}|s|) $ . The answer to the query is the number of substrings of string $ s[l_{i}...\ r_{i}] $ , which are palindromes.
String $ s[l...\ r]s_{l}s_{l1}...\ s_{r} $ $ (1lr|s|) $ is a substring of string $ ss_{1}s_{2}...\ s_{|s|} $ .
String $ t $ is called a palindrome, if it reads the same from left to right and from right to left. Formally, if $ tt_{1}t_{2}...\ t_{|t|}t_{|t|}t_{|t|-1}...\ t_{1} $ .
## 输入格式
The first line contains string $ s $ $ (1|s|5000) $ . The second line contains a single integer $ q $ $ (1q10^{6}) $ — the number of queries. Next $ q $ lines contain the queries. The $ i $ -th of these lines contains two space-separated integers $ l_{i},r_{i} $ $ (1l_{i}r_{i}|s|) $ — the description of the $ i $ -th query.
It is guaranteed that the given string consists only of lowercase English letters.
## 输出格式
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.
## 样例 #1
### 样例输入 #1 caaaba 5 1 1 1 4 2 3 4 6 4 5
### 样例输出 #1 1 7 3 4 2
## 提示
Consider the fourth query in the first test case. String $ s[4...\ 6] $ «aba». Its palindrome substrings are: «a», «b», «a», «aba».
核心思路
类似容斥dp
f[l][r]表示答案 f[l][r-1] [l1][r] -f[l1][r-1]pd[l][r]
AC代码
#includebits/stdc.h
using namespace std;
const int maxn 5050;
int tot;
string a;
int n;
bool pd[5050][5050];
long long f[5050][5050];
int main(){ios::sync_with_stdio(0);cin.tie(0);cina;n a.size();a a;for(int i 1;i n;i)pd[i][i] 1;for(int i 1;i n-1;i)if(a[i] a[i1])pd[i][i1] 1;for(int i 3;i n;i){for(int l 1,r li-1;r n;l,r){pd[l][r] (pd[l1][r-1] 1a[l] a[r]?1:0);}}for(int i 1;i n;i){f[i][i] 1;} for(int i 2;i n;i){for(int l 1,r li-1;r n;l,r){f[l][r] f[l][r-1]f[l1][r]-f[l1][r-1]pd[l][r];}}int q;cinq;while(q--){int l,r;cinlr;coutf[l][r]\n;}return 0;
}
