ZROI#957

难吗?倒不是很难.

为啥考场上没做出来?菜!

为啥菜?不知道...(知道了就不这么菜了)

(灵魂三问.jpg)

那怎么做呢?我们先考虑怎么去找一个好的下标序列.

很简单,贪心即可.那么怎么去找优秀的下标序列呢?

我们发现,贪心得到的下标序列是所有好的序列中字典序最小的那一个.

所以我们想要得到答案,必须考虑把某些下标向后调整.

那么我们发现,如果存在答案,那么这个答案对于原串中的每一个位置$i(s_i\not ={s_{i-1}})$

一定有一个是处在答案序列中的.所以我们就只需要向这些位置调整就行了.

由于我们只有两种字符,且$s_i\not ={s_{i-1}}$所以我们一定能匹配上其中一位.

贪心得到的序列一定是单调递增且字典序最小的,而我们每一个需要调整到的位置$i$.

所以只有$ans_j < i$的这些前缀才能有机会调整.

我们每次调整能调整的里面最大的那一个,一定不会变劣.

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #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
                
                 #define int long long#define pb push_backusing 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 ;}