专栏文章

题解：B4323 [科大国创杯小学组 2025] 改写

XXZhuRen
B4323题解参与者 4已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@mipjf6zi
此快照首次捕获于
2025/12/03 12:59
3 个月前
此快照最后确认于
2025/12/03 12:59
3 个月前
查看原文
@JHPOTATO 大神出的题目，快去膜拜她 qwq。
考虑乱搞。
发现同段一定是回文取不到，两段接一起必然不回文可以取，把段长缩小到 min⁡(len,2)\min(len,2)。
长度由 O(∑len)\mathcal{O}(\sum len) 压缩到了 O(m)\mathcal{O}(m)。
直接写出串，感性理解，回文长度一定不超过 55，DP 一个最大值 fif_i 表示压缩后的串前 ii 个字符的答案，暴力往前做 44 次转移即可。
官方题解划分等价类严谨证明，下面感性证一下：
已经将长度缩到了 22 以内，连续两段长度和不超过 44，转移最优下不会多取。
注意到 m=3m=3 的情况可能需要特判第一段长度等于第二段，这个取决于实现。
代码：
CPP
int n,m;
int a[400005];
int dp[400005];

bool checkpl(int l,int r) {
    for(int i=l;i<r+l-i;++i) {
        if(a[i]!=a[r+l-i]) return false;
    }
    return true;
}

void wk() {
    read(m);n=0;
    if(m==3){
        char x[4];
        int y[4];
        for(int i=1;i<=m;i++){
            cin>>x[i]>>y[i];
        }
        if(x[1]==x[3]&&y[1]==y[3]&&y[2]==1)printf("-1\n");
        else if(y[2]==1)printf("1\n");
        else printf("2\n");
        return;
    }
    char x;int y;
    for(int i=1;i<=m;++i) {
        cin>>x>>y;
        (x-='a')+=1;
        y=min(y,2);
        while(y--) a[++n]=x;
    }
    for(int i=1;i<=n;++i) dp[i]=-1e9;
    for(int i=1;i<=n;++i) {
        for(int j=i;i-j<=4 && j>=1;--j) {
            if(!checkpl(j,i)) dp[i]=max(dp[i],dp[j-1]+1);
        }
    }
    if(!checkpl(1,n)) dp[n]=max(dp[n],1);
    writeln(dp[n]<0?-1:dp[n]);
}

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...