列表

详情

NC51605. subsequence 2

描述

There is a hidden string of length n composed of the first m lowercase English letters. For any two different English letters, we will tell you a subsequence of the hidden string constructed by removing all other letters from the hidden string.

For example, if the hidden string is "apple" and the chosen letters are 'e' and 'p', the resulting subsequence would be "ppe"; if the chosen letters are 'a' and 'x', the resulting subsequence would be "a".

Now, please recover the hidden string. Output -1 if there are no possible hidden string. Output any one if there are multiple possible hidden strings.

输入描述

The first line contains two integers n and m.

Following are  groups of two lines. The first line in each group contains a two-letter string composed of c1, c2, and an integer LEN. The second line contains a string composed of letters c1, c2 with length LEN, indicates the resulting subsequence by removing all other letters except c1 and c2 from the hidden string.

* 

* 

* 

* all unordered pairs of letters in first m small English letters will occur exactly once.

输出描述

If there is at least one possible hidden string, please output any. Otherwise, output -1.

示例1

输入: 

3 3
ab 2
ab
bc 2
bc
ca 2
ac

输出: 

abc

说明:

First group tells us that there is one 'a' and one 'b' where 'a' is before 'b', the second group tells us there is one 'b' and one 'c' where 'b' is before 'c'. So the only possible answer is "abc" which satisfies the last group as well.

示例2

输入: 

3 3
cb 3
bbc
ca 2
ac
ab 3
abb

输出: 

-1

示例3

输入: 

4 3
ac 4
cccc
ba 0

cb 4
cccc

输出: 

cccc

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 1528K, 提交时间: 2019-08-02 00:48:26 

#include <bits/stdc++.h>

using namespace std;

char ch[20];
int n,m,len[207],st[207];
char ss[200][20002],Ans[20002];
int pos[20][202],cnt[20];

bool check(int u){
	for(int i=1;i<m;i++){
		int id=pos[u][i];
		if(st[id]>len[id]||ss[id][st[id]]!=u+'a') return 0;
	}
	return 1;
}

void Solve(int u){
	for(int i=1;i<m;i++){
		int id=pos[u][i];
		st[id]++;
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=(m-1)*m/2;i++){
		scanf("%s",ch);
		int c=ch[0]-'a',d=ch[1]-'a';
		pos[c][++cnt[c]]=i;
		pos[d][++cnt[d]]=i;
		cin>>len[i],st[i]=1;
		if(len[i]) scanf("%s",ss[i]+1);
	}

	for(int i=1;i<=n;i++){
		int t=-1;
		for(int j=0;j<m;j++)if(check(j)){t=j;break;}
		if(t==-1) printf("-1\n"),exit(0);
		Ans[i]=t+'a';
		Solve(t);
	}
	for(int i=1;i<=(m-1)*m/2;i++){
		if(st[i]<=len[i]) printf("-1\n"),exit(0);
	}
	cout<<Ans+1<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 7ms, 内存消耗: 1000K, 提交时间: 2019-08-01 12:48:49 

#include<bits/stdc++.h>
using namespace std;
char ch[20];
int n,m,len[202],st[202];
char ss[200][20002],ans[20002];
int pos[20][202],cnt[20];
bool check(int u)
{
	for(int i=1;i<m;i++)
	{
		int id=pos[u][i];
		if(st[id]>len[id]||ss[id][st[id]]!=u+'a')return false;
	}
	return true;
}
void work(int u)
{
	for(int i=1;i<m;i++)
	{
		int id=pos[u][i];
		st[id]++;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m*(m-1)/2;i++)
	{
		scanf("%s",ch);
		int c=ch[0]-'a',d=ch[1]-'a';
		pos[c][++cnt[c]]=i;
		pos[d][++cnt[d]]=i;
		cin>>len[i],st[i]=1;
		if(len[i])scanf("%s",ss[i]+1);
	}
	for(int i=1;i<=n;i++)
	{
		int t=-1;
		for(int j=0;j<m;j++)if(check(j)){t=j;break;}
		if(t==-1){puts("-1");return 0;}
		ans[i]=t+'a';
		work(t);
	}
    for(int i=1;i<=m*(m-1)/2;i++)if(st[i]<=len[i]){puts("-1");return 0;}
	cout<<ans+1<<endl;
}

上一题

© 2025 nowcoder.com