T6 散落の字符：Manacher算法、大模拟

题意说明

本次题目比较复杂，需要我们计算以下问题的答案。

1. 通过迷宫的最小花费 $sum$。
2. 转换 $sum$ 并拼接到 $s$ 后面，转换 $s$ 为 01 字符串。
3. 计算转换为偶回文串最小花费 $f$ 的值。
4. 连接 $t$ 和 $s$，计算最长回文串 $l$ 的值。

走迷宫

这一部分采用任何搜索算法均可。期待大家给出出题组没做出来的 dp 的办法。以下是 dijkstra 的做法：

struct Node {
    int x, y, cost;
    bool operator<(const Node& other) const {
        return cost > other.cost; // 最小堆
    }
};

void dijkstra() {
    priority_queue<Node> pq;
    pq.push({1, 1, migong[1][1]});
    vis[1][1] = true;

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        int x = current.x, y = current.y, cost = current.cost;

        if (x == n && y == m) {
            ret = cost;
            return;
        }

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny]) {
                continue;
            }
            vis[nx][ny] = true;
            pq.push({nx, ny, cost + migong[nx][ny]});
        }
    }
}

转换与拼接

这一部分直接采用模拟即可。一个字符的ASCII码值为偶数是 $\bmod2$ 的结果为 $0$，否则为 $1$。

a=to_string(ret);
cin>>b;
d+=b;
for (int i = 0;i < a.size();++i){
	if (a[i]=='0'){
		d+=d[d.size()-1];
	}else{
		d+=monib[a[i]-'0'];
	}
}
for (int i = 0;i < d.size();++i){
	d[i]=((int)d[i])%2+'0';
}
t=d;
cin>>c;
c+=d;

计算 f 的值

在这一步中，我们需要推理一下。数据保证 $s$ 可以转化为偶回文串，说明 $s + min_a$ 的结果是偶数或者拼接后的 $s$ 的中间值为 $0$。如果是第二种可能，就只需要保证其它部分是偶回文串即可。

因此无论如何，只要保证拼接后的 $s$ 是一个回文串即可保证是偶回文串。我们只需要从 $i=0$ 一直到 $i=|s|\div2$ 遍历一遍，找到改变成偶回文串的最小花费。对于每个第 $i$ 项，我们只需考虑是改变成 0 还是 1 的花费更小。

for(int i = 0;i < d.size() / 2;i++){
  if(d[i] == d[d.size() - i - 1]) continue;
  else ans1 += min(w[i],w[d.size() - i - 1]);
}

计算 l 的值

暴力做法：枚举每一段 l 中的子串。代码如下：

for(int i = 0;i < l.size();i++){
    for(int j = i + 1;j < l.size();j++){
        if(hw(l.substr(i,j + 1))) maxx = max(maxx,j - i + 1);
    }
}

时间复杂度：$O(|l|^2)$

预计得分：$50pts$

我们可以使用 Manacher 算法来解决 $l$ 的计算。回文自动机的 Manacher 算法可以在 $O(N)$ 时间中解决最长回文子串问题。

下面就是模板的 Manacher 算法了（这里使用 % 避免边界问题，若有想要深入学习的请见：这里）：

int alen=c.size(),len=2;
s[0]='%';
s[1]='#';
for (int i=0;i<alen;++i){
    s[len++]=c[i];
    s[len++]='#';
}
s[len]='#';
int mid=1,r=1,ans1=-1;
for (int i=1;i<=len;++i){
    maxs[i]=0;
}
for (int i=1;i<=len;++i){
    if (i<r){
        maxs[i]=min(r-i,maxs[mid*2-i]);
    }else{
        maxs[i]=1;
    }
    while (s[i-maxs[i]]==s[i+maxs[i]]){
        maxs[i]+=1;
    }
    if (r<i+maxs[i]){
        mid=i;
        r=i+maxs[i];
    }
    ans1=max(maxs[i]-1,ans1);
}

时间复杂度：$O(|l|)$

预计得分：$200pts$

正解

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int hmod = 1e9 + 7, base = 31;
int n, m, migong[333][333], dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
long long w[200025], dp[200010], ret = 1e13;
bool vis[333][333];
char monib[30] = {'0', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'};
string a, b, c, d, t;
char s[13000000];
int maxs[13000000];

struct Node {
    int x, y, cost;
    bool operator<(const Node& other) const {
        return cost > other.cost; // 最小堆
    }
};

void dijkstra() {
    priority_queue<Node> pq;
    pq.push({1, 1, migong[1][1]});
    vis[1][1] = true;

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        int x = current.x, y = current.y, cost = current.cost;

        if (x == n && y == m) {
            ret = cost;
            return;
        }

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny]) {
                continue;
            }
            vis[nx][ny] = true;
            pq.push({nx, ny, cost + migong[nx][ny]});
        }
    }
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> migong[i][j];
        }
    }

    dijkstra();
    a = to_string(ret);
    cin >> b;
    d += b;
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] == '0') {
            d += d[d.size() - 1];
        } else {
            d += monib[a[i] - '0'];
        }
    }
    for (int i = 0; i < d.size(); ++i) {
        d[i] = ((int)d[i]) % 2 + '0';
    }
    t = d;
    cin >> c;
    c += d;
    int alen = c.size(), len = 2;
    s[0] = '%';
    s[1] = '#';
    for (int i = 0; i < alen; ++i) {
        s[len++] = c[i];
        s[len++] = '#';
    }
    s[len] = '#';
    int mid = 1, r = 1, ans1 = -1;
    for (int i = 1; i <= len; ++i) {
        maxs[i] = 0;
    }
    for (int i = 1; i <= len; ++i) {
        if (i < r) {
            maxs[i] = min(r - i, maxs[mid * 2 - i]);
        } else {
            maxs[i] = 1;
        }
        while (s[i - maxs[i]] == s[i + maxs[i]]) {
            maxs[i] += 1;
        }
        if (r < i + maxs[i]) {
            mid = i;
            r = i + maxs[i];
        }
        ans1 = max(maxs[i] - 1, ans1);
    }
    for (int i = 0; i < t.size(); ++i) {
        cin >> w[i];
    }
    n = t.size();
    for (int i = 0; i < d.size() / 2; ++i) {
        if (d[i] == d[d.size() - i - 1]) continue;
        else ans1 += min(w[i], w[d.size() - i - 1]);
    }
    cout << ans1 << "\n";
    return 0;
}

时间复杂度：$O(n\times m\times \log{n\times m}))$

预计得分：$200pts$