CF1213E Two Small Strings

问题分析

由于三个字母是等价的，所以大致可以分为如下几种情况：

aa, ab

ab, ac

ab, ba

ab, bc

不难发现，第\(3\)中情况可能造成无解（\(n>1\)时），而剩下的情况都可以由\(aaabbbccc\)或\(abcabcabc\)这样的串解决。所以直接枚举\(3\)个字母的全排列，然后拓展成上面两种情况分别判断一下即可。

参考程序

#include <bits/stdc++.h>

using namespace std;

int n;

char A[ 10 ], B[ 10 ];

int Map[ 10 ][ 10 ];

int Ans[ 10 ];

bool Check1() {

	return Map[ Ans[ 1 ] ][ Ans[ 2 ] ] || Map[ Ans[ 2 ] ][ Ans[ 3 ] ] || Map[ 1 ][ 1 ] || Map[ 2 ][ 2 ]|| Map[ 3 ][ 3 ];

}

bool Check2() {

	return Map[ Ans[ 1 ] ][ Ans[ 2 ] ] || Map[ Ans[ 2 ] ][ Ans[ 3 ] ] || Map[ Ans[ 3 ] ][ Ans[ 1 ] ];

}

int main() {

	scanf( "%d", &n );

	scanf( "%s%s", A + 1, B + 1 );

	Map[ A[ 1 ] - 'a' + 1 ][ A[ 2 ] - 'a' + 1 ] = 1;

	Map[ B[ 1 ] - 'a' + 1 ][ B[ 2 ] - 'a' + 1 ] = 1;

	Ans[ 1 ] = 1; Ans[ 2 ] = 2; Ans[ 3 ] = 3;

	if( n == 1 ) {

		while( Map[ Ans[ 1 ] ][ Ans[ 2 ] ] || Map[ Ans[ 2 ] ][ Ans[ 3 ] ] )

			if( !next_permutation( Ans + 1, Ans + 4 ) ) {

				printf( "NO\n" );

				return 0;

			}

		printf( "YES\n" );

		printf( "%c%c%c\n", Ans[ 1 ] + 'a' - 1, Ans[ 2 ] + 'a' - 1, Ans[ 3 ] + 'a' - 1 );

		return 0;

	}

	while( true ) {

		if( !Check1() ) {

			printf( "YES\n" );

			for( int i = 1; i <= n; ++i ) printf( "%c", Ans[ 1 ] + 'a' - 1 );

			for( int i = 1; i <= n; ++i ) printf( "%c", Ans[ 2 ] + 'a' - 1 );

			for( int i = 1; i <= n; ++i ) printf( "%c", Ans[ 3 ] + 'a' - 1 );

			printf( "\n" );

			return 0;

		}

		if( !Check2() ) {

			printf( "YES\n" );

			for( int i = 1; i <= n; ++i )

				printf( "%c%c%c", Ans[ 1 ] + 'a' - 1, Ans[ 2 ] + 'a' - 1, Ans[ 3 ] + 'a' - 1 ) ;

			printf( "\n" );

			return 0;

		}

		if( !next_permutation( Ans + 1, Ans + 4 ) ) {

			printf( "NO\n" );

			return 0;

		}

	}

	return 0;

}

巴特西

CF1213E Two Small Strings

问题分析

参考程序

最新文章

热门文章