codeforces 1384A（构造）

dejavu1zz

发布于 2020-10-23 15:23:56

2920

发布于 2020-10-23 15:23:56

题意描述

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代码

#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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/07/25 ，如有侵权请联系 cloudcommunity@tencent.com 删除

koa

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

koa

登录后参与评论

0 条评论

热度