ZROI#957

爱被打了一巴掌 2023-06-02 11:59 61阅读 0赞

# ZROI\#957 #

[ZROI\#957][ZROI_957]  
难吗?倒不是很难.  
为啥考场上没做出来?菜!  
为啥菜?不知道...(知道了就不这么菜了)  
(灵魂三问.jpg)  
那怎么做呢?我们先考虑怎么去找一个好的下标序列.  
很简单,贪心即可.那么怎么去找优秀的下标序列呢?  
我们发现,贪心得到的下标序列是所有好的序列中字典序最小的那一个.  
所以我们想要得到答案,必须考虑把某些下标向后调整.  
那么我们发现,如果存在答案,那么这个答案对于原串中的每一个位置\\(i(s\_i\\not =\{s\_\{i-1\}\})\\)  
一定有一个是处在答案序列中的.所以我们就只需要向这些位置调整就行了.  
由于我们只有两种字符,且\\(s\_i\\not =\{s\_\{i-1\}\}\\)所以我们一定能匹配上其中一位.  
贪心得到的序列一定是单调递增且字典序最小的,而我们每一个需要调整到的位置\\(i\\).  
所以只有\\(ans\_j < i\\)的这些前缀才能有机会调整.  
我们每次调整能调整的里面最大的那一个,一定不会变劣.

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = a ; i <= b ; ++ i) #define per(i,a,b) for (int i = a ; i >= b ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 3e5 + 100 ; int n , m , ans[N] , cnt ; char s[N] , t[N] ; signed main (int argc , char * argv[]) { n = rint () ; m = rint () ; scanf ("%s%s" , s + 1 , t + 1 ) ; for (int i = 1 , cur = 1 ; i <= m ; ++ i) { while ( s[cur] != t[i] && cur <= n ) ++ cur ; if ( cur >= n + 1 ) return puts ("-1") , 0 ; ans[++cnt] = cur ; ++ cur ; } int j = cnt ; per ( i , n , 2 ) if ( s[i] != s[i-1] ) { while ( ans[j] > i && j ) -- j ; if ( ! j ) return puts ("-1") , 0 ; if ( s[ans[j]] == s[i] ) ans[j] = i ; else ans[j] = i - 1 ; } rep ( i , 1 , cnt ) printf ("%lld " , ans[i] ) ; return 0 ; }

转载于:https://www.cnblogs.com/Equinox-Flower/p/11497937.html

[ZROI_957]: http://www.zhengruioi.com/problem/957