题解：CF1886C Decreasing String

Jerrycyx · 2024-11-19 11:38:41 · 题解

前置知识：链表

首先，每次删除的一定是比后一个字符大且位置最靠前的字符，例如 cadb 下一次删除的是第一个 c。

证明：

• 如果当前字符比后面字符大，删掉这个字符并让后面向前移动一位一定会使字典序变小（这个位置被更小的后一个字符替代）；
• 如果有多个字符满足上述条件，那么删掉最前面的一个可以使字典序减小的位置最靠前（比如 cadb 删 c 是在第一个位置减小字典序，删 d 是在第三个位置减小字典序），而根据字典序的定义，小字符越靠前，字典序越小。

综上所述，每次删除第一个比后一个字符大的字符是最优的。

有了这个结论，我们就可以求字符串中各个字符被删除的顺序了，但是直接求是 O(N^2) 的，考虑如何优化。

观察下面的删字符过程：

abandon
a_andon
a_a_don
a_a_d_n

a_a_d__
a_a____
a______

可以发现，删字符的过程是从前往后删掉所有的逆序，字符串变成不下降以后再从后往前依次删除。

其实把 s_{n+1} 看作 0 的话，上面的两步可以合并成一步，都是在删逆序。

再来看一个例子：

acdcbb
ac_cbb
ac__bb
a___bb
a___b_
a_____

这个就稍微有所不同了，在第 3 步和第 4 步之间，很明显是往前删了的，不符合“从前往后删除逆序”的结论，所以不能通过单扫一下就找出删除顺序（我做的时候真想这么干）。

但是，有一个结论：当删除字符 x 的时候，它的前面所有字符都一定小于等于 x（否则第一个逆序就不该是 x 了），只有删除了 x 以后，如果前面的字符与 x 相等，接替了 x 的位置与后一个字符形成逆序，才会造成“往前退了一位合并”的情况。

所以，我们在每次删除成功后将位置向前移动一位（只有这一位可能回退形成新的逆序），尝试删除，这样就可以解决删除顺序回退的问题了。

同时，最后从后往前删的问题也能通过这种方式解决，删完最后一个以后回退一位（该字符是末尾字符，所以此时再尝试删除一定成功）即可做到从后往前删除。

然而，直接向前找没被删掉的字符，时间复杂度是 O(N^2) 的，如何快速地找字符串的上一个字符？

回想一下，我们要实现快速删除元素和找前驱后继的操作，而这正是链表干的事情（终于有一道链表题了）。

（不过这个似乎用栈也可以维护，但是用链表要更加直观一些。）

通过上述过程，我们 O(N) 求出来了字符串内字符被删除的顺序。

接下来，直接 O(N) 暴力找出 pos 所在 S 的哪一部分，即找出 pos 所在字符串所删字符数量 part。（其实也可以用二分 O(\log N) 求，不过没必要还容易错）

设 pos 在这个部分中位置为 pos'=pos-\frac{(2n-(part-1)) \times ((part-1)+1)}{2}，在字符串内找还没被删掉的字符（被删除的时间晚于 part 的）的第 pos' 个即为所求。

AC 记录

完整代码：

#include<cstdio>
#include<cstring>
using namespace std;

const int N=1e6+5;
int n; long long pos;
char s[N];
int order[N],oidx;

struct BJ{
    int pre,nxt;
}ls[N];
inline void del(int x)
{
    ls[ls[x].pre].nxt=ls[x].nxt;
    ls[ls[x].nxt].pre=ls[x].pre;
    return;
}

int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%s%lld",s+1,&pos);
        n=strlen(s+1);

        for(int i=1;i<=n;i++)
            ls[i]={i-1,i+1};
        oidx=0;
        for(int i=1;i<=n;)
        {
            if(s[i]>s[ls[i].nxt])
            {
                order[i]=++oidx;
                del(i);
                i=ls[i].pre;
            }
            else i=ls[i].nxt;
        }

        int part=0; long long tot=0;
        for(int i=0;i<=n;i++)
        {
            tot+=n-i;
            if(tot>=pos)
            {
                part=i;
                break;
            }
        }

        int real_pos=pos-1ll*(n*2-(part-1))*((part-1)+1)/2;
        int sidx=0;
        char ans='-';
        for(int i=1;i<=n;i++)
            if(order[i]>part)
            {
                sidx++;
                if(sidx==real_pos)
                {
                    ans=s[i];
                    break;
                }
            }
        putchar(ans);
    }
    return 0;
}