题解：CF1789F Serval and Brain Power

kkxacj · 2025-07-07 20:15:57 · 题解

神秘的通过了，记录一下。

思路

首先我想到了如果 k 是偶数等同于 k=2，然后就解决了 k 为偶数的情况，具体的就是枚举分界点 L，然后左边和右边匹配，f_{i,j} 表示左边匹配到了 i，右边匹配到了 j 最长匹配长度能到多少，然后预处理一个 nxt_{i,j} 表示从 i 开始第一次遇到字符是 j 的下标是多少，没有就设为 n+1，显然转移就是枚举下一个匹配字符看是否满足 nxt_{i,z} \le L,nxt_{j,z} \le n，可以就尝试更新即可，初值就是若 a_i=a_j 则 f_{i,j} = 1。复杂度 \operatorname{O}\left(n^3\times V\right)，V 是字符集大小。

然后剩下 k 为奇数的，我们发现如果 k 比较大的时候可以枚举那个字符串长什么样子的，注意到分为 k 段的话总有一段所占长度是 \le \frac{n}{k} 的，不然每一段都大于那不超了，那么对于 k=5 复杂度大概是 \operatorname{O}\left(2^{16}\times n^2\right) 的，更大的话也不会超过这个，有了这个字符串，我们从第一个开始一直跳 nxt_{i,s_j} 就好了，不过要注意如果字符串只匹配了一次是不能算的，这是因为题目要求至少匹配 2 次。

分析发现只剩下 k=3 未解决了，那么套路的学习第一个，我们也套路的枚举两个分界点即可，具体做法参考第一个，复杂度 \operatorname{O}\left(n^5\times V\right)，然后就没了，不用太担心这个复杂度，应为带小常数的，实际跑出来会快很多。

code

#include<bits/stdc++.h>
using namespace std;
namespace IO
{
    template<typename T>
    void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}
    template<typename T,typename... Args>
    void read(T &_x,Args&...others){Read(_x);Read(others...);}
    const int BUF=20000000;char buf[BUF],to,stk[32];int plen;
    #define pc(x) buf[plen++]=x
    #define flush(); fwrite(buf,1,plen,stdout),plen=0;
    template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++to]=48+x%10;while(to) pc(stk[to--]);}
}
using namespace IO;
const int N = 100,M = 26;
int n,a[N],b[N],cnt,x,y,z,nxt[N][30],f[N][N],g[N][N][N],ans,sum,o,O;
string s;
inline int solve(int len)
{
    x = sum = 0;
    while(1)
    {
        for(int i = 1;i <= len;i++)
        {
            x = nxt[x+1][b[i]];
            if(x > n) return sum;
        }
        sum += len;
    }
    return sum;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    cin >> s; n = s.size(); s = ' '+s;
    for(int i = 1;i <= n;i++) a[i] = s[i]-'a';
    for(int i = 0;i < M;i++) nxt[n+1][i] = n+1;
    for(int i = n;i >= 1;i--)
    {
        for(int j = 0;j < M;j++) nxt[i][j] = nxt[i+1][j];
        nxt[i][a[i]] = i;
    }
    for(int r = 2;r <= n;r++)
    {
        for(int i = 1;i < r;i++)
            for(int j = r;j <= n;j++)
                f[i][j] = 0;
        for(int l = 1;l <= r;l++)
            if(a[l] == a[r])
                f[l][r] = 2;
        for(int i = 1;i < r;i++)
            for(int j = r;j <= n;j++)
                if(f[i][j]) 
                    for(int z = 0;z < 26;z++)
                    {
                        if(nxt[i+1][z] < r && nxt[j+1][z] <= n)
                            f[nxt[i+1][z]][nxt[j+1][z]] = max(f[nxt[i+1][z]][nxt[j+1][z]],f[i][j]+2);
                    }
        for(int i = 1;i < r;i++)
            for(int j = r;j <= n;j++)
                ans = max(ans,f[i][j]);
    }
    for(int r = 2;r <= n;r++)
        for(int m = r+1;m <= n;m++)
        {
            for(int i = 1;i < r;i++)
                for(int j = r;j < m;j++)
                    for(int z = m;z <= n;z++)
                        g[i][j][z] = 0;
            for(int l = 1;l <= r;l++)
                if(a[l] == a[r] && a[r] == a[m]) g[l][r][m] = 3;
            for(int i = 1;i < r;i++)
                for(int j = r;j < m;j++)
                    for(int z = m;z <= n;z++)
                        if(g[i][j][z]) 
                            for(int k = 0;k < 26;k++)
                            {
                                if(nxt[i+1][k] < r && nxt[j+1][k] < m && nxt[z+1][k] <= n)
                                    g[nxt[i+1][k]][nxt[j+1][k]][nxt[z+1][k]] = max(g[nxt[i+1][k]][nxt[j+1][k]][nxt[z+1][k]],g[i][j][z]+3);
                            }
            for(int i = 1;i < r;i++)
                for(int j = r;j < m;j++)
                    for(int z = m;z <= n;z++)
                    ans = max(ans,g[i][j][z]);
        }
    for(int i = 1;;i++)
    {
        O = (1<<min(n-i+1,16));
        for(int j = 1;j < O;j++)
        {
            cnt = 0;
            for(int z = 0;z < 16 && z+i <= n;z++)
                if(((1<<z)&j)) b[++cnt] = a[z+i];
            o = solve(cnt);
            if(o >= cnt*2) ans = max(ans,o);
        }
        if(i+15 >= n) break;
    }
    print(ans); flush();
    return 0;
}
/*
其实可以这样,f_{l,r,i,j}表示开始左右端点是(l,r)，然后目前匹配到(i,j)了的最大长度是多少
首先是初值，显然可以就是a_l=a_r，那么f_{l,r,l,r}
枚举l,r然后g_{i,j}
然后转移就是枚举一个字符然后转移过去
复杂度，emm，当然系n^3*26的 
注意到k%2可能等于1，这里只解决了k%2=0的
k==3可以暴力枚举三个点跑转移，复杂度也就n^6*26（跑不满，应该很小才对） 
然后我们可以枚举集合了，注意到我们选的一段序列总有一段跨度不超过n/k，否则每个都大于那你长度不就超标了
考虑枚举i，然后状压16个位置看是否选，然后求出序列，我们显然贪心的看匹配出最大的就好了，复杂度2^16*n^2 
*/