列表

详情

NC17863. Rikka with Nickname

描述

Sometimes you may want to write a sentence into your nickname like "lubenwei niubi". But how to change it into a single word? Connect them one by one like "lubenweiniubi" looks stupid.

To generate a better nickname, Rikka designs a non-trivial algorithm to merge a string sequence s1...sn into a single string. The algorithm starts with s=s1 and merges s2...sn into s one by one. The result of merging t into s is the shortest string r which satisfies s is a prefix of r and t is a subsequence of r.(If there are still multiple candidates, take the lexicographic order smallest one.)

String s is a prefix of r if and only if |s| ≤ |r| and for all index i ∈ [1, |s|], si = ri.

String s is a subsequence of r if and only if there is an index sequence which satisfies .

For example, if we want to generate a nickname from "lubenwei niubi", we will merge "niubi" into "lubenwei", and the result is "lubenweiubi".

Now, given a sentence s1...sn with n words, Rikka wants you to calculate the resulting nickname generated by this algorithm.

输入描述

The first line contains a single number t(1 ≤ t ≤ 3), the number of testcases.

For each testcase, the first line contains one single integer n(1 ≤ n ≤ 106).

Then n lines follow, each line contains a lowercase string .

输出描述

For each testcase, output a single line with a single string, the result nickname.

示例1

输入: 

2
2
lubenwei
niubi
3
aa
ab
abb

输出: 

lubenweiubi
aabb

原站题解

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

C++ 解法, 执行用时: 191ms, 内存消耗: 2780K, 提交时间: 2022-02-17 19:27:56 

#include<bits/stdc++.h>
using namespace std;
int n;

int main()
{
	int t;
	cin>>t;
	while(t--){
		cin>>n;
		string s1;
		cin>>s1;
		for(int i=1;i<n;i++){
			int j=0,k=0;
			string s2;
			cin>>s2;
			while(s1[j]&&s2[k]){
				if(s1[j]==s2[k]) k++;
				j++;
			}
			while(s2[k]){
				s1+=s2[k];
				k++;
			}
		}
		cout<<s1<<'\n';
	}
}

C++14(g++5.4) 解法, 执行用时: 184ms, 内存消耗: 3292K, 提交时间: 2018-08-19 16:00:51 

#include<bits/stdc++.h>
#define r(a,b,c) for(a=b;a<c;a++)
using namespace std;char x[1000005],a[1000005];int n,t,f,c,k,i,j,l,g;int main(){cin>>t;while(t--){c=0;cin>>n;r(k,0,n){cin>>a;l=strlen(a);f=0;r(i,0,l){g=0;while(f<c){if(x[f]==a[i]){f++;g=1;break;}f++;}if(f==c&&!g){r(j,i,l)x[c++]=a[j];i=l;f=0;}}}x[c]='\0';puts(x);}return 0;}

上一题

© 2024 nowcoder.com