ZR#957

痛定思痛。 2024-04-20 10:34 82阅读 0赞

##  ##

ZR\#957

### 解法： ###

> 首先 $ T $ 必须得要是 $ S $ 的子序列，不然不存在好的下标序列，因此一定无解。  
> 考虑判断一个串 $ T $ 是不是 $ S $ 子序列的贪心做法：每次从没有匹配的位置中，选择第一个和 $ T\_i $ 一样的与 $ T\_i $ 进行匹配。设这样得到的下标序列是 $ p\_1, p\_2, \\cdots , p\_m $ ，则显然这是一个好的下标序列。  
> 从刚刚贪心的过程中，我们可以发现，$ p\_1 $ 是所有可能的位置中最小的，$ p\_2 $ 是在满足 $ p\_1 $ 最小的情况下最小的，$ p\_3 $ 是在满足 $ p\_1, p\_2 $ 都最小的情况下最小的 $ \\cdots \\cdots $ 则这样得到的序列是所有好的下标序列中，字典序最小的那个。  
> 我们接下来考虑调整这个好的下标序列，使它变成优秀的。我们按照从后往前的顺序依次考虑 S 中所有满足相邻两个字母不同的位置，设为 $ i $ 和 $ i + 1 $ 。根据题意，我们要求 $ i $ 和 $ i + 1 $ 中至少有一个在这样的下标序列中，这样的下标序列才会是优秀的。  
> 容易证明，对于所有这样的 $ i $ ，都满足 $ i $ 和 $ i + 1 $ 中的至少一个在序列中的好的下标序列一定是优秀的。  
> 如果 $ i $ 或者 $ i + 1 $ 已经在序列 $ p $ 中了，那么已经符合条件了。否则，我们考虑调整：因为 $ p $ 已经是字典序最小的序列了，所以我们无法把某个 $ p\_j $ 变得更小。因此，我们可以移动的位置一定是满足 $ p\_j < i $ 的一段前缀。  
> 因为 $ S\_i \\neq S\_i+1 $，所以 $ T\_j = S\_i $ 或 $ T\_j = S\_i+1 $ 之一一定满足。于是，我们一定可以把 $ p\_j $ 调整为 $ i $ 或 $ i + 1 $ 之一，从而使得 $ i $ 满足条件。如果有多个 $ j $ 满足这一条件，则我们应当选择最大的那个，容易证明这样一定不劣。如果不存在这样的 $ j $，根据 $ p $ 是字典序最小的好的序列，其他序列一定也不存在这样的 $ j $，因此一定无解。

### CODE: ###

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define LL long long const int N = 3e5 + 100; int m,n,p[N]; char a[N],b[N]; int main(){ scanf("%d%d",&n,&m); scanf("%s%s",a + 1,b + 1); for(int i = 1,j = 1 ; i <= m ; ++i) { while(j <= n && a[j] != b[i]) ++j; if(j > n) { puts("-1"); return 0; } p[i] = j++; } a[0] = a[1]; for(int i = n,j = m ; i >= 1 ; --i) { if(a[i] == a[i-1]) continue; while(j >= 1 && p[j] > i) j--; if(j <= 0) { puts("-1"); return 0; } if(p[j] >= i-1) continue; p[j] = a[i] == b[j] ? i : i-1; } for(int i = 1 ; i <= m ; i++) printf("%d ",p[i]); //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11508906.html