题目链接

题意

给定一个字符串（长度$\leq 2e5$），将其划分成尽量少的段，使得每段内重新排列后可以成为一个回文串。

题解

分析

每段内重新排列后是一个回文串$\rightarrow$该段内至多只有一个字符出现过奇数次

考虑哈希到一个$26$位的$01$串，出现过奇数次的元素位置上的值为$1$，否则为$0$.

于是可以继续往下推：$\rightarrow$该段的哈希值为$0$或者是$2$的幂次。

转化

于是问题转化为：将字符串切割成尽量少的若干段，使得每段的哈希值均满足为$0$或者是$2$的幂次。

预处理异或前缀和可以$O(1)$算得每段的哈希值。

问题至此一个很显然的做法就是$O(n^2)$的$dp$，然而显然是无法承受的。

对dp形式的思考

我们来考虑一下原先想写的$dp$的形式：

\[dp[i]=min_{j<i,ok(j+1,i)}\{dp[j]\}+1
\]

这里的$ok(j+1,i)$指的是$s[j+1..i]$一段的哈希值满足要求。

仔细思考一下，这里有两个约束条件，

$j<i$
$ok(j+1,i)$

我们常规的思路是拿第一个条件去循环，然后判断第二个条件是否被满足。

然而在这里，对于给定的$i$，有$i-1$个$j$满足第一个条件，而只有$\leq 27$个$j$满足第二个条件。

故更优的考虑是拿第二个条件去循环。

O(n)-dp

什么叫做拿第二个条件去循环呢？

意思是我们直接找到那个$h[j]$，它和$h[i]$异或起来的值满足条件。

由异或的性质，$h[i]\oplus h[j]=power\leftrightarrow h[i]\oplus power=h[j]$

所以，我们应该存的信息有：

$dp[x]$代表哈希值为$x$的最少切割次数
$opt[i]$代表$[1..i]$段最少的切割次数

则显然转移有$$opt[i]=min{dp[h[i]\oplus mask]}+1$$$$dp[x]=min(dp[x],opt[i])$$

官方题解

Code

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define maxn 200010

using namespace std;

typedef long long LL;

char s[maxn];

int opt[maxn], h[maxn];

int main() {

    scanf("%s", s+1);

    int len = strlen(s+1);

    for (int i = 1; i <= len; ++i) h[i] = h[i-1] ^ (1<<(s[i]-'a'));

    map<int, int> dp;

    for (int i = 1; i <= len; ++i) {

        opt[i] = (!h[i] || dp[h[i]]) ? dp[h[i]] : inf;

        int mask = 1;

        for (int j = 0; j < 26; ++j) {

            if ((h[i]^mask) == 0 || dp[h[i]^mask]) opt[i] = min(opt[i], dp[h[i]^mask]);

            mask <<= 1;

        }

        ++opt[i];

        if (!dp[h[i]] && h[i]) dp[h[i]] = opt[i];

        else dp[h[i]] = min(dp[h[i]], opt[i]);

    }

    printf("%d\n", opt[len]);

    return 0;

}

巴特西

Atcoder CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning 回文串划分

题目链接

题意

题解

分析

转化

对dp形式的思考

O(n)-dp

官方题解

Code

最新文章

热门文章