洛谷 P10170 [DTCPC 2024] 小方和小立方 题解

洛谷 P10170 [DTCPC 2024] 小方和小立方 题解

思路

一眼看上去,这题非常非常的难,对吧???好吧,我的第一反应就是 DP,但是 DP 似乎并不能非常优雅的解决问题。然后我就想到了马拉车,但是马拉车+特判实现起来实在是有些繁琐。

突然,我猛地发现,如果每个字母的出现次数不超过 \(2\) 次的话,回文串的长度最多就是 \(52\)。也就是说,暴力的时间大约是 \(O(52n)\),很显然,这是可以非常轻松通过的。那么我们只需要枚举回文串的中心,然后逐步向两边扩展,直到不能扩展为止。对于这种暴力的思路都能通过的题目,我只能说文字游戏一点都不好完(赛时浪费了接近 \(1.5h\))。

实现

实现实际上也没有什么难度,按照思路简单的写一下即可。不过需要注意的是下表的处理,注意不要越界和重复即可。判重的话,我个人用的是 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <map>
#include <algorithm>
#include <cstring>

using namespace std;

string s;
char ch;
int a[30];
map<pair<int, int>, bool> mp;

int check(string ss) {
// cout << ss << endl;
memset(a, 0, sizeof a);
for (char i: ss) {
a[i - 'a'] += 1;
if (a[i - 'a'] > 2) {
return -1;
}
}
string sp = ss;
reverse(sp.begin(), sp.end());
return ss == sp;
}

signed main() {
cin >> s;
int ans = 0;
for (int i = 0; i < s.size(); i++) {
int l = i, r = i;
ans += 1;
while (true) {
int p = -1;
if (r != s.size() - 1) {
r += 1;
if (!mp[{l, r}]) {
p = check(s.substr(l, r - l + 1));
if (p == 1) {
mp[{l, r}] = true;
ans += 1;
}
}
}
if (l != 0) {
l -= 1;
if (!mp[{l, r}]) {
p = check(s.substr(l, r - l + 1));
if (p == 1) {
mp[{l, r}] = true;
ans += 1;
}
}
}
if (r != s.size() - 1 && l != 0) {
if (!mp[{l, r}]) {
p = check(s.substr(l, r - l + 1));
if (p == 1) {
mp[{l, r}] = true;
ans += 1;
}
}
}
if (p == -1) {
break;
}
}
}
cout << ans;
}

洛谷 P10170 [DTCPC 2024] 小方和小立方 题解
https://lixuannan.github.io/posts/14032.html
作者
CodingCow Lee
发布于
2024年2月17日
许可协议