Skip to content

「POI2006」Palindromes

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

Johnny 喜欢玩文字游戏。

他写下了 nn 个回文串,随后将这些串两两组合,合并成一个新串。容易看出,一共会有 n2n^2 个新串。

两个串组合时顺序是任意的,即 ab 可以组合成 abba,另外自己和自己组合也是允许的。

现在他想知道这些新串中有多少个回文串,你能帮帮他吗?

#输入格式

第一行一个整数 nn

接下来 nn 行,第 ii 行包含一个数 aia_i 和一个长度为 aia_i 的回文串。

#输出格式

输出一个整数,代表满足条件的新串的数量。

#输入输出样例

样例输入 #1

6
2 aa
3 aba
3 aaa
6 abaaba
5 aaaaa
4 abba

样例输出 #1

14

#数据范围与约定

保证输入中的所有字符串只包含小写字母,且所有串两两不同,所有回文串的长度和不超过 2×1062 \times 10^6

#思路

有两个回文字符串 A,BA, B,由两个字符串拼接而成的新字符串 ABAB 是回文字符串的条件是 A,BA, B 中较短的串是较长的串的一个循环节。可以考虑枚举每个串的前缀,然后去查询这个前缀是否是另外一个较短的串,再判断组成的新串是否是回文的即可。

可以使用 std::unordered_map 或者 Trie + Hash 维护,下方的代码使用的是 std::unordered_map

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <string>
#include <unordered_map>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2e6 + 5;

int n;
long long ans;
std::string s[N];
std::unordered_map<std::string, int> map;

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n;

for (int i = 1, _; i <= n; i++) {
cin >> _ >> s[i];

map[s[i]]++;
}

for (int i = 1; i <= n; i++) {
std::string str, str1(s[i]); // 卡常
str.reserve(s[i].size());
str1.reserve(s[i].size() << 1);

for (char c : s[i]) {
str.push_back(c);
str1.push_back(c);

if (map.count(str) && str1 == str + s[i]) {
ans += static_cast<long long>(map[str]) * 2;
}
}
}

cout << ans - n << endl;

return 0;
}