AT2173 Shik and Copying String [思维题]

$S h i k <mtext> </mtext> a n d <mtext> </mtext> C o p y i n g <mtext> </mtext> S t r i n g$

题目描述请点击题目链接 .

$<mstyle mathcolor="blue"> 最初想法 </mstyle>$

先检查无解情况 ~~骗点分~~ .
因为只有前面才会对后面造成影响, 所以 从后向前处理,
分情况讨论

$S_{i} = T_{i}$ , 无覆盖, 跳过 .
$S_{i} = T_{i}$ , 有相应覆盖, 跳过 .
$S_{i} = T_{i}$ , 无相应覆盖, 查找 $(1, M i n_L)$ 内 $S_{t} = T_{i}$ 的 $t$ , 从 $t$ 向后覆盖, 若找不到, 无解. 若有其他覆盖, $A n s + +$ .
$S_{i} \neq T_{i}$ , 有相应覆盖, 跳过 .
$S_{i} \neq T_{i}$ , 无相应覆盖, 同 $3.$

对影响的消除部分有细节 .
栈不要开 $1 e 6 <mtext> </mtext>!!!$ , 会 $M L E$ .

$<mstyle mathcolor="red"> 正解部分 </mstyle>$

大体思路跟上方差不多, 我怎么就没想到画二维图?!

将过程图画出来, 发现字母之间覆盖关系马上就清楚了许多 .

字母覆盖折线不能相交.
覆盖折线要尽量 $" 贴 "$ 着走 .

考虑一个折线的产生对以后的折线有什么影响,
看到图中红色箭头部分, 是 $c$ 产生的折线使得 $a$ 产生的折线不得不弯曲一次,

这也可以看成是 $c$ 的折线拐点传递到了 $a$ , 使得 $a$ 产生第 $2$ 个拐点 .
假设又有新的折线加入, 可能又会接着 $a$ 的第二个拐点继续传, 进而产生第 $3$ 个拐点, 同时 $a$ 的第一个拐点又会传递产生新折线的第 $2$ 个拐点 , 以此类推 .

$设$ 当前从后往前遍历到了 $i$ , 且在 $(1, 最后的覆盖起点)$ 中满足 $S_{t} = T_{i}$ 的最大的编号为 $t$ ,

前方某个折线的 $覆盖起点$ 为 $b g$ , 传递了 $l e n$ 次,

则当且仅当 $b g - l e n + 1 \leq i$ 的时候那个折线才会对现在造成影响,

于是使用队列维护从后往前的操作中产生的折线, 每次弹出无用的折线, 剩下的折线对当前 $i$ 造成影响,
设队列大小为 $q_s i z e$ , 则会多产生 $q_s i z e$ 个拐点 , 加上当前折线产生的 $1$ 个拐点, 总共有 $q_s i z e + 1$ 个拐点 .

$E N D$ .

$<mstyle mathcolor="red"> 实现部分 </mstyle>$

使用队列维护 .
注意当 $i = M i n_l$ 时折线只有一个转折点 .

#include<bits/stdc++.h>
#define reg register

const int maxn = 1000005;

int N;

char S[maxn];
char T[maxn];

int main(){
        scanf("%d", &N);
        scanf("%s%s", S+1, T+1);
        int flag = 1;
        for(reg int i = 1; i <= N; i ++)
                if(S[i] != T[i]){ flag = 0; break ; }
        if(flag){ printf("0\n"); return 0; }
        int Min_l = N, Ans = 1;
        std::queue <int> Q;
        for(reg int i = N; i >= 1; i --){
                Min_l = std::min(i, Min_l);
                if(T[i] == T[i-1]) continue ;
                while(Min_l && S[Min_l] != T[i]) Min_l --;
                if(!Min_l){ printf("-1\n"); return 0; }
                while(!Q.empty()){
                        if(Q.front()-Q.size()+1 > i) Q.pop();
                        else break ;
                }
                Q.push(Min_l);
                if(Min_l != i) Ans = std::max(Ans, (int)Q.size() + 1);
        }
        printf("%d\n", Ans);
        return 0;
}