Codeforces Round #659 (Div. 2) A 、C

目次

A Common Prefixes

題意

解題構想

コード

C String Transformation 1

題意

解題構想

コード

A Common Prefixes
に言及

リンク:Common Prefixes

は長さnの配列を与え、ここでa[i]は文字列s[i-1]とs[i]の最長共通接頭辞の長さを表し、文字列配列(任意解)

を求める.
問題を解く構想.

a[i]の最大値は、すべての文字列の長さ

である.

0番目の文字列は任意で、便宜上「aaa......aa」

に設定します.

のi番目の文字列は、前の文字列のa[i]位置++でよい文字列は小文字の母で構成されていることに注意し、zを超える場合

を処理する.
コード#コード#

#include
#include
using namespace std;
int t,x,n,a[202],maxn;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		maxn=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			maxn=max(a[i],maxn);
		}
		char s[202];
		maxn++;
		for(int i=0;i<maxn;i++)s[i]='a';
		s[maxn]='\0';
		printf("%s
",s);
		for(int i=1;i<=n;i++)
		{
			s[a[i]]++;
			if(s[a[i]]>'z')s[a[i]]='a';
			printf("%s
",s);
		}
	}
	return 0;
}

C String Transformation 1
に言及

リンク:String Transformation 1

a-tからなる2つの文字列AとBを与えて、列Aを列Bに変える最小回数を求めて、毎回Aの中の1つ以上の同じ文字をそれより大きいものに変えることができて、もしB出力"-1"

にならないならば
問題を解く構想.

aabがbccになるのは、1文字1文字が3回変わるのではなく、1:aabがbbbになり、2:bbbがbccになる

であることに注意してください.

暴力:a-tの20文字を列挙し、Aの同じ文字を探し出し、すべてBの対応する最小文字

になる.
コード#コード#

#include
#include
using namespace std;
const int INF=0x7f7f7f7f;
const int N=1e5+5;
int t,n;
char a[N],b[N];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d
",&n);
		scanf("%s
%s
",a,b);
		int flag=0;
		for(int i=0;i<n;i++)
			if(a[i]>b[i])
			{
				printf("-1
");
				flag=1;
				break;
			}
		if(!flag) 
		{
			int ans=0;
			for(int j=0;j<20;j++)//       
			{
				int tmp=INF;
				for(int i=0;i<n;i++)	
				{
					if(a[i]=='a'+j&&a[i]!=b[i])tmp=min(tmp,b[i]-'a');//  b         
				}
				if(tmp==INF)continue;
				for(int i=0;i<n;i++)	
				{
					if(a[i]=='a'+j&&a[i]!=b[i])a[i]=tmp+'a';//           b         
				}
				ans++;
			}
			printf("%d
",ans);
		}
	}
	return 0;
}