题目链接 问题分析 题目实际上是一堆大于等于的约束。观察这 \(2n-2\) 个约束。第一组可以将要求的排成一个不降的序列,然后第二组就是在第一组的基础上再添加条件。 不妨设第一组
题目链接
问题分析
题目实际上是一堆大于等于的约束。观察这\(2n-2\)个约束。第一组可以将要求的排成一个不降的序列,然后第二组就是在第一组的基础上再添加条件。
不妨设第一组生成的不降序列是\(\{a_i\}\),然后添加的条件是\(a_i\leqslant a_j\)。那么显然,\(i<j\)的时候这个条件是没有用的。而如果\(i>j\),就代表着\(i\)到\(j\)这一整个区间都要相等。这个用差分数组标记一下,最后统计即可。
需要注意的是可能可以生成超过\(k\)种字母,也可能大于\(26\)种,所以最后输出的时候对\(k\)取min即可。
参考程序
#include <bits/stdc++.h> using namespace std; const int Maxn = 200010; int n, k, P[ Maxn ], Q[ Maxn ], Ref[ Maxn ]; int A[ Maxn ], Ans[ Maxn ]; int main() { scanf( "%d%d", &n, &k ); for( int i = 1; i <= n; ++i ) scanf( "%d", &P[ i ] ); for( int i = 1; i <= n; ++i ) scanf( "%d", &Q[ i ] ); for( int i = 1; i <= n; ++i ) Ref[ P[ i ] ] = i; for( int i = 1; i < n; ++i ) if( Ref[ Q[ i + 1 ] ] < Ref[ Q[ i ] ] ) ++A[ Ref[ Q[ i + 1 ] ] ], --A[ Ref[ Q[ i ] ] ]; int Sum = 0; for( int i = 1; i <= n; ++i ) { if( Sum ) Ans[ i ] = Ans[ i - 1 ]; else Ans[ i ] = Ans[ i - 1 ] + 1; Sum += A[ i ]; } if( Ans[ n ] < k ) printf( "NO\n" ); else { printf( "YES\n" ); for( int i = 1; i <= n; ++i ) printf( "%c", min( Ans[ Ref[ i ] ], k ) + 'a' - 1 ); printf( "\n" ); } return 0; }