a610: D. 茴芠數回文數
標籤 :
通過比率 : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-06-03 21:52

內容

茴芠是個回文愛好者,常常會收集一些字串,裡面有著各式各樣的回文。

有一天他在大掃除,想把收藏的字串整理一下,看看這些收藏的字串中有多少回文

但由於字串實在太長了,茴芠一個人數不完而現在茴芠想請你幫忙,

茴芠給你一個字串 $s$,每次問你裡面有幾個長度為 $k$ 的回文

以便茴芠統計他所蒐集的回文數量,讓他計算完之後好跟朋友炫耀

 

回文,亦稱迴文回環,是正讀反讀都能讀通的句子

輸入說明

多筆測資

第一行有一個正整數 $T(T\le 2 \cdot 10^4)$,代表總共 $T$ 筆測資

每筆測資共 $4$ 行

第一行有一個正整數 $n(1\le n\le 2 \cdot 10^5)$ ,代表字串 $s$ 的長度

第二行有一個長度為 $n$ 的字串 $s$ ,保證裡面只有小寫字母

第三行有一個正整數 $q(1\le q \le 2 \cdot 10^5)$,代表詢問數

第四行有 $q$ 個正整數 $k_i (1 \le k_i \le n)$ 代表詢問長度為 $k_i$ 的回文有幾個

 

* 保證所有 $n, q$ 加起來分別不超過 $2 \cdot 10^5$

輸出說明

共 $T$ 行,

每行分別依序輸出每筆測資的答案

範例輸入
2
2
bb
2
1 2
5
ababa
3
1 3 5
範例輸出
2 1
5 3 1
測資資訊:
記憶體限制: 256 MB
不公開 測資點#0 (10%): 1.0s , <10M
不公開 測資點#1 (10%): 1.0s , <10M
不公開 測資點#2 (10%): 1.0s , <10M
不公開 測資點#3 (10%): 1.0s , <1M
不公開 測資點#4 (10%): 1.0s , <1M
不公開 測資點#5 (10%): 1.0s , <10M
不公開 測資點#6 (10%): 1.0s , <10M
不公開 測資點#7 (10%): 1.0s , <10M
不公開 測資點#8 (10%): 1.0s , <10M
不公開 測資點#9 (10%): 1.0s , <10M
提示 :
標籤:
出處:
DDJ Regular ContestRound#3 [管理者:
fdhs105285 (jakao)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」