Codeforces 1384A. Common Prefixes

本文主要是介绍Codeforces 1384A. Common Prefixes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

The length of the longest common prefix of two strings 𝑠=𝑠1𝑠2…𝑠𝑛 and 𝑡=𝑡1𝑡2…𝑡𝑚 is defined as the maximum integer 𝑘 (0≤𝑘≤𝑚𝑖𝑛(𝑛,𝑚)) such that 𝑠1𝑠2…𝑠𝑘 equals 𝑡1𝑡2…𝑡𝑘.

Koa the Koala initially has 𝑛+1 strings 𝑠1,𝑠2,…,𝑠𝑛+1.

For each 𝑖 (1≤𝑖≤𝑛) she calculated 𝑎𝑖 — the length of the longest common prefix of 𝑠𝑖 and 𝑠𝑖+1.

Several days later Koa found these numbers, but she couldn’t remember the strings.

So Koa would like to find some strings 𝑠1,𝑠2,…,𝑠𝑛+1 which would have generated numbers 𝑎1,𝑎2,…,𝑎𝑛. Can you help her?

If there are many answers print any. We can show that answer always exists for the given constraints.

Input
Each test contains multiple test cases. The first line contains 𝑡 (1≤𝑡≤100) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer 𝑛 (1≤𝑛≤100) — the number of elements in the list 𝑎.

The second line of each test case contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖≤50) — the elements of 𝑎.

It is guaranteed that the sum of 𝑛 over all test cases does not exceed 100.

Output
For each test case:

Output 𝑛+1 lines. In the 𝑖-th line print string 𝑠𝑖 (1≤|𝑠𝑖|≤200), consisting of lowercase Latin letters. Length of the longest common prefix of strings 𝑠𝑖 and 𝑠𝑖+1 has to be equal to 𝑎𝑖.

If there are many answers print any. We can show that answer always exists for the given constraints.

Example
inputCopy
4
4
1 2 4 2
2
5 3
3
1 3 1
3
0 0 0
outputCopy
aeren
ari
arousal
around
ari
monogon
monogamy
monthly
kevinvu
kuroni
kurioni
korone
anton
loves
adhoc
problems
Note
In the 1-st test case one of the possible answers is 𝑠=[𝑎𝑒𝑟𝑒𝑛,𝑎𝑟𝑖,𝑎𝑟𝑜𝑢𝑠𝑎𝑙,𝑎𝑟𝑜𝑢𝑛𝑑,𝑎𝑟𝑖].

Lengths of longest common prefixes are:

Between 𝑎𝑒𝑟𝑒𝑛 and 𝑎𝑟𝑖 →1
Between 𝑎𝑟𝑖 and 𝑎𝑟𝑜𝑢𝑠𝑎𝑙 →2
Between 𝑎𝑟𝑜𝑢𝑠𝑎𝑙 and 𝑎𝑟𝑜𝑢𝑛𝑑 →4
Between 𝑎𝑟𝑜𝑢𝑛𝑑 and 𝑎𝑟𝑖 →2

题意：
要求构造n+1个小写字母串，使得第i个串和第i-1个串的最大公共前缀长度为 $a [i]$

思路：
第0个串设置为aaaaaaa…
那么第1个串复制第0个串，再把 $a [1] + 1$ 位置换掉就好了。
以此类推

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<unordered_map>using namespace std;
typedef long long ll;int a[105];
char b[105];int main() {int T;scanf("%d",&T);while(T--) {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) scanf("%d",&a[i]);for(int i = 1;i <= 100;i++) {b[i] = 'a';printf("%c",b[i]);}printf("\n");for(int i = 1;i <= n;i++) {for(int j = 1;j <= 100;j++) {if(j == a[i] + 1) {b[j]++;if(b[j] > 'z') b[j] = 'a';printf("%c",b[j]);} else {printf("%c",b[j]);}}printf("\n");}}return 0;
}