HDU - 2018杭电ACM集训队单人排位赛 - 2 - Problem D. Team Name

简介: HDU - 2018杭电ACM集训队单人排位赛 - 2 - Problem D. Team Name

Problem D Team Name

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 129    Accepted Submission(s): 68


Problem Description

After all the teams have been matched, what to do next is of course to think about a nice team name. Now it is known that there are n teams taking part in the Guangxi Province Collegiate Programming Contest. And the name of every team is a string consists of English lower characters. Now Luras needs to get her team name, she doesn’t want the name be any consecutive substring of any other teams. And she prefers shorter names. If there are many choices with the shortest length, she would prefer the one which is the smallest lexicographically. Now could you decide the team name for her? We regard string a is lexicographically smaller than string b if there exists such index j that a[i] == b[i] for all i < j and a[j] < b[j].

Input

The first line is an integer T which indicates the case number.

And as for each case,  there will be n + 1 lines.

In the first line, there is one integer n, which indicates the number of teams.

Then there will be n strings of the next n lines, indicate the name of every team in each line.

It is guaranteed that——

T is about 100.

for 100% cases, 1 <= n <= 100, 1 <= |s|(the length of s)<= 30.

Output

As for each case, you need to output a single line.

There should be one string in the line which means the name Luras will give to her team.

Sample Input

2

3

a

b

c

2

abcdefghijklmnopqrstuvwxyz

aa

Sample Output

d

ac

解题思路:不是 n 个队名中的子串 && 队名字典序尽可能小。


AC 代码


/

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
char a[110][110], ans[110];
bool ok;
int n;
void dfs(int dep,int len)
{
    if(len==dep)
    {
        ans[len++]='\0';
        for(int i=0;i<n;i++)
            if(strstr(a[i],ans)) return;
        ok=true;
        return;
    }
    for(int i=0;i<26;i++)
    {
        ans[dep]=i+'a';
        dfs(dep+1,len);
        if(ok) return;
    }
    return;
}
int main()
{
    int T; scanf("%d",&T);
    while(T-- && ~scanf("%d",&n))
    {
        for(int i=0;i<n;i++) scanf("%s",a[i]);
        ok=false;
        for(int len=1;;len++)
        {
            if(ok) break;
            dfs(0,len);
        }
        printf("%s\n",ans);
    }
    return 0;
}
目录
相关文章
|
3月前
|
Shell
[SWPUCTF 2021 新生赛]gift_pwn-入土为安的第十五天
[SWPUCTF 2021 新生赛]gift_pwn-入土为安的第十五天
127 0
|
C++ 网络架构
【PAT甲级 - C++题解】1013 Battle Over Cities
【PAT甲级 - C++题解】1013 Battle Over Cities
62 1
2022天梯赛三月冲刺——PAT (Advanced Level)1013 Battle Over Cities (并查集找连通块)
2022天梯赛三月冲刺——PAT (Advanced Level)1013 Battle Over Cities (并查集找连通块)
105 0
|
C++
【PAT甲级 - C++题解】1061 Dating
【PAT甲级 - C++题解】1061 Dating
70 0
upc2021秋组队训练赛第一场 ICPC North Central NA Contest 2020
upc2021秋组队训练赛第一场 ICPC North Central NA Contest 2020
90 0
upc2021秋组队训练赛第一场 ICPC North Central NA Contest 2020
UPC组队赛第三场——G: The Famous ICPC Team Again (主席树)
UPC组队赛第三场——G: The Famous ICPC Team Again (主席树)
100 0
|
人工智能
upc 2021秋组队训练赛第三场 2020 Rocky Mountain Regional Contest
upc 2021秋组队训练赛第三场 2020 Rocky Mountain Regional Contest
95 0
[SDUT 2414] | 山东省第三届省赛 An interesting game | 最小费用最大流
题目描述 Xiao Ming recently designs a little game, in front of player there are N small hillsides put in order, now Xiao Ming wants to increase some hillsides to block the player, so he prepared another M hillsides, but he does not hope it will be too difficult,
164 0
[SDUT 2414] | 山东省第三届省赛 An interesting game | 最小费用最大流
|
Java Go
HDU - 2018杭电ACM集训队单人排位赛 - 2 - Problem E. Travel
HDU - 2018杭电ACM集训队单人排位赛 - 2 - Problem E. Travel
125 0
|
机器学习/深度学习 算法 Java
HDU - 2018杭电ACM集训队单人排位赛 - 3 - Problem B. Bullet
HDU - 2018杭电ACM集训队单人排位赛 - 3 - Problem B. Bullet
168 0