ZROI#957
ZROI#957
难吗?倒不是很难.
为啥考场上没做出来?菜!
为啥菜?不知道…(知道了就不这么菜了)
(灵魂三问.jpg)
那怎么做呢?我们先考虑怎么去找一个好的下标序列.
很简单,贪心即可.那么怎么去找优秀的下标序列呢?
我们发现,贪心得到的下标序列是所有好的序列中字典序最小的那一个.
所以我们想要得到答案,必须考虑把某些下标向后调整.
那么我们发现,如果存在答案,那么这个答案对于原串中的每一个位置$i(s_i\not ={s_{i-1}})$
一定有一个是处在答案序列中的.所以我们就只需要向这些位置调整就行了.
由于我们只有两种字符,且$s_i\not ={s_{i-1}}$所以我们一定能匹配上其中一位.
贪心得到的序列一定是单调递增且字典序最小的,而我们每一个需要调整到的位置$i$.
所以只有$ans_j < i$的这些前缀才能有机会调整.
我们每次调整能调整的里面最大的那一个,一定不会变劣.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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 ;
}