题意描述
The length of the longest common prefix of two strings s=s1s2…sn and t=t1t2…tm is defined as the maximum integer k (0≤k≤min(n,m)) such that s1s2…sk equals t1t2…tk.
Koa the Koala initially has n 1 strings s1,s2,…,sn 1.
For each i (1≤i≤n) she calculated ai — the length of the longest common prefix of si and si 1.
Several days later Koa found these numbers, but she couldn’t remember the strings.
So Koa would like to find some strings s1,s2,…,sn 1 which would have generated numbers a1,a2,…,an. Can you help her?
If there are many answers print any. We can show that answer always exists for the given constraints.
思路
每次将s[a[i]] 即可
AC代码
代码语言：javascript复制#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x )
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=105;
const int M=1e6 10;
const int INF=0x3f3f3f3f;
const int MOD=1e9 7;
int a[N];
char s[N];
void solve(){
mst(a,0);
int n;cin>>n;
int MAX=-1;
rep(i,1,n 1){
cin>>a[i];
MAX=max(MAX,a[i]);
}
rep(i,0,MAX 1) s[i]='a';
cout<<s<<endl;
rep(i,1,n 1){
if(s[a[i]]=='z') s[a[i]]='a';
else s[a[i]] ;
cout<<s<<endl;
}
}
int main(){
IOS;
int t;cin>>t;
while(t--){
solve();
}
return 0;
}
