ZR#957 痛定思痛。 2024-04-20 10:34 87阅读 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
相关 ZR#997 ZR\997 解法: > 找找规律就出来了,全场最简单的一道题。 CODE: include<iostream> include<cstdi... 怼烎@/ 2024年04月20日 10:34/ 0 赞/ 89 阅读
相关 ZR#957 ZR\957 解法: > 首先 $ T $ 必须得要是 $ S $ 的子序列,不然不存在好的下标序列,因此一定无解。 > 考虑判断一个串 $ T $ 是... 痛定思痛。/ 2024年04月20日 10:34/ 0 赞/ 88 阅读
相关 ZR#998 ZR\998 解法: > 先把所有物品按照拿走的时间从小到大排序,拿走的时间相同就按照放上去的时间从大到小。那么一件物品上方的物品就一定会在它的前面。 ... 柔光的暖阳◎/ 2024年04月20日 10:33/ 0 赞/ 100 阅读
相关 ZR#712 消灭砖块 题意: > 很多块砖分布在一个 $ m \\times m $ 的矩阵中,他可以消掉以他为左上角顶点的一个 $ n \\times n $ 的矩阵... 朱雀/ 2024年04月20日 10:24/ 0 赞/ 76 阅读
相关 ZR#710 雷劈数 题意: > 现在给出两个整数,求出位于两个整数之间的所有的“雷劈数。 解法: > 因为雷劈数特殊的性质,所以在数据范围中的雷劈数实际很少,直... ゝ一纸荒年。/ 2024年04月20日 10:24/ 0 赞/ 96 阅读
相关 ZROI#957 ZROI\957 [ZROI\957][ZROI_957] 难吗?倒不是很难. 为啥考场上没做出来?菜! 为啥菜?不知道...(知道了就不这么菜了) (灵 爱被打了一巴掌/ 2023年06月02日 11:59/ 0 赞/ 18 阅读
相关 957E 题意: Arkady在一个有n架飞机的机场做交管员。飞机的移动可以看做是在一维坐标系上,Arkady的站台位于原点(0坐标)。第i架飞机位于xi x i 坐标,以速度v Bertha 。/ 2022年05月28日 02:39/ 0 赞/ 129 阅读
相关 957D 题意: Arkady对一条河进行了n天的观察,每天的水平面高度是个数值。Arkady每天将水平面的高度在海岸上做上记号(如果原先这个位置没有记号的话),记号不会消失。Ar 向右看齐/ 2022年05月28日 02:39/ 0 赞/ 120 阅读
相关 957C 题意: 给你一个数列E,保证E1<E2<E3<...<En。 E , 保 证 E 1 < E 2 < E 3 < . . . < E n 。 请你选出3个数Ei< 悠悠/ 2022年05月28日 02:39/ 0 赞/ 97 阅读
相关 957B 题意: 有一张初始全是白色的N\M的格子图 Arkady可以进行一系列的操作,第i个操作包含一个非空行号集合Ri R i ,以及一个非空列号集合Ci C i 。对 迷南。/ 2022年05月28日 02:38/ 0 赞/ 99 阅读
还没有评论,来说两句吧...