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

思路

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

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

实现

实现实际上也没有什么难度，按照思路简单的写一下即可。不过需要注意的是下表的处理，注意不要越界和重复即可。判重的话，我个人用的是 map，可以轻松的通过，不过闲着没事干的也可以手写哈希，应该能快很多。

#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;
}