P3551 题解

xkcdjerry · 2021-12-20 22:00:56 · 题解

更差的阅读体验

一道好题，刚开始正着想死活想不出来，最后想到正难则反，考虑最后一段一定是连续的（否则一定不合法），而假如最后一段被删除了倒数第二段也是连续的，所以结构应该类似一棵树，以样例为例，也可以这么划分：

10 11 12 
1 8 9 
2 6 7 
3 4 5 

对应的是：

[c[c[bcb]bb]bb][bcb]

联系如何构造树的结构和删除后前后需要连接上可以想到使用栈来维护，每次将一个字符压入栈中，如果最后 k+1 个中恰好有一个 c，那么弹出这 k+1 个（对应在原串中删除）并且记录弹出了哪些位置。由于连续段是最后一个选的却是最先被扫处来的，所以弹出的顺序应该倒过来。

正确性证明：
假如有解，那么这么构造能够找到这个解的一个合法最后一步，而去除最后一步以及其相关的字母之后会变成一个一模一样而且规模更小的问题，可以对其使用相同的论证直到问题规模降为 0。所以显然保证正确性。

时间复杂度：
每个字母共 n 个会恰好被插入 1 次，弹出 1 次，总时间为 O(n)。
且每弹出 k 个点会花 O(k) 的时间重新计算 c 的数目，由于保证有解会恰好弹出 \frac{n}{k+1} 次，总时间为 O(k \times \frac{n}{k+1})=O(n)。
所以整个程序的复杂度为 O(n)。

上代码（为截至 2021 年 12 月 20 日的最优解）：

#include <cstdio>
#define N 1000010
int n,k;
int f[N],g[N];
char s[N];
//top：栈顶
//black：最近k+1个中有几个c
//kk：一维数组模拟二维数组的辅助变量
int top,black,kk;
int main()
{
    scanf("%d%d%s",&n,&k,s+1);
    for(int i=1;i<=n;i++)
    {
        f[++top]=i;
        //维护最近k+1个中的c数目
        black+=(s[i]=='c');
        if(top>k+1) black-=(s[f[top-k-1]]=='c');
        //处理匹配
        if(top>k&&black==1)
        {
            //弹出k个并记录
            for(int j=0;j<=k;j++) g[kk+j]=f[top-j];
            kk+=k+1;
            top-=k+1;
            //重新维护c的数目
            black=0;
            for(int j=0;j<top&&j<=k;j++) black+=(s[f[top-j]]=='c');
        }
    }

    for(int i=kk-k-1;i>=0;i-=k+1)
    {
        //记得输出编号的时候反向
        for(int j=k;j>=0;j--) printf("%d ",g[i+j]);
        putchar('\n');
    }
}

评测记录

注意点：

• 题目只保证 k<n，所以不能开 k \times k 的矩阵，本人是使用了一个一维数组来模拟二维矩阵，实际上也可以动态分配 \frac{n}{k+1} \times k 的矩阵但是会慢一些
• 由于栈是按字符串顺序压入的所以从顶向下弹出的时候会反向，由于题目要求升序输出输出的时候还需要再反向一遍

说句闲话，看到这段代码跑的时间我感觉数据范围开到 10^7 甚至 1.5 \times 10^7 都行，还是出题人太仁慈了（雾）