gpt4 book ai didi

Minlexes题解

转载 作者:撒哈拉 更新时间:2024-03-31 18:40:21 55 4
gpt4 key购买 nike

\(\texttt{Problem Link}\) 。

简要题意

在一个字符串 \(s\) 中,对于每个后缀,任意删掉一些相邻的相同的字符,使得字符串字典序最小.

注意:删掉之后拼起来再出现的相邻相同字符不能够删除.

思路

倍增好题.

发现存在局部最优解(最优子结构),并且可以转移到其它结点,可以考虑使用 dp.

那就设 \(f _ i\) 表示 \([i , n]\) 经过一些操作,达成的字典序最小的字符串(求后缀最优解,从后往前遍历).

可以得到状态转移:

\[ f_i = \begin{cases} f_{i+1} + s_i, & s_i \neq s_{i+1},\\ \min \{f_{i+1} + s_i , f_{i+2}\} & s_i = s_{i+1}. \\ \end{cases} \]

\(s_i\) 表示第 \(i\) 个字符,\(\min\) 表示字典序更小的那个.

边界条件:\(f_n = s_n\).

但是这样做的复杂度是 \(\mathcal{O}(n^2)\).

字典序比较优化

瓶颈在于比较字典序.

考虑对字典序比较进行优化.

回顾字典序比较的过程, 。

过程是对于两个字符串,从头到尾一个个字符进行比较,遇到第一个字符不同时,就返回答案.

那么就可以有一个想法通过一些操作,快速找到第一个不同的字符.

可以考虑使用倍增优化,把两个串比较时,通过倍增找到 hash 值第一个不同的地方,这样字符串比较就能优化到 \(\mathcal{O}(\log n)\).

输出优化

接下来的问题就是输出, 。

因为输出长字符只要输出前 \(5\) 个和最后 \(2\) 个.

所以可以对于前面的字符直接输出,后面的字符也可以写个倍增往后跳到需要的.

最后总的复杂度就是 \(\mathcal{O}(n \log n)\).

Code

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

using i64 = long long ;
using ui64 = unsigned long long ;

const int N = 1e5 + 5 ;
const int base = 131 ;

char s[N];
int f[N] , g[N] , h[N];
ui64 Pow[100];
ui64 Hash[20][N];//自然溢出
int nxt[20][N];
int n;

void updata(int u, int v){
    v = h[v];
    h[u] = u;
    g[u] = g[v] + 1;//记录当前的长度
    nxt[0][u] = v;
    Hash[0][u] = s[u] - 'a';

    for(int i = 1; i <= 19; i++)
        nxt[i][u] = nxt[i-1][nxt[i-1][u]] , Hash[i][u] = Hash[i-1][u] * Pow[i - 1] + Hash[i-1][nxt[i-1][u]]; //处理hash倍增
// nxt是方便向后跳2^k的
}

int min(int x, int y){
    int tx = x , ty = y;
    
    x = h[x] , y = h[y];

    for(int i = 19; i >= 0; i--)
        if(nxt[i][x] && nxt[i][y] && Hash[i][x] == Hash[i][y])
            x = nxt[i][x] , y = nxt[i][y];//找到第一个不同的字符
        
    return Hash[0][x] < Hash[0][y]? tx: ty;//小细节不能写 <= 写 <= 会导致部分少删除
}

int main(){

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

    n = strlen(s+1);

    Pow[0] = base;
    for(int i = 1; i <= 90; i++)
        Pow[i] = Pow[i - 1] * Pow[i - 1];//预处理 base 的 2^i 次方,方便将hash值拼起来

    for(int i = n; i >= 1; i--) {
        updata(i,i+1);//默认是接上字符

        if(i < n && s[i] == s[i+1] && min(i,i + 2) == i + 2) {//删除更优
            h[i] = h[h[i + 2]];
            g[i] = g[h[i + 2]];
        }
    }

    for(int i = 1; i <= n; i++) {
        printf("%d ",g[i]);

        int id = h[i];
        if(g[i] <= 10) {
            for(int j = id; j && j <= n; j = nxt[0][j])
                putchar(s[j]);
        } else {
            for(int j = 1; j <= 5; j++ , id = nxt[0][id])//前5个字符直接暴力找
                putchar(s[id]);
            
            printf("...");

            id = h[i];
            int len = g[i] - 2 ;

            for(int i = 19; i >= 0; i--)
                if(nxt[i][id] && (1<<i) <= len) len -= 1<<i , id = nxt[i][id];//倍增找最后两个字符
            
            for(int j = 1; j <= 2; j++ , id = nxt[0][id])
                putchar(s[id]);
        }

        puts("");
    }
    return 0;
}

牢骚

本来思路是完全正确的,但是我用了一个 Trie 树和递归找字符串,导致常数太大,真的气死人了.

最后此篇关于Minlexes题解的文章就讲到这里了,如果你想了解更多关于Minlexes题解的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

55 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com