HDU 2970 Suffix reconstruction
3575 ワード
Description
abcdeのような文字列の接尾辞文字列はabcde,bcde,cde,cが彼らに番号1 2 3 4 5を与えてから彼らの辞書順に並べ替えて1 2 3 4 5を得た現在問題は与えられた生成の並べ替えであり、生成の最小のその文字列は例を挙げるとabbaabababab接尾辞文字列1 abbaabab,2 bbaababab,3 baababab,4 aab,5 ababab,6 bab,7 abである.8 bそれから彼らの辞書の順序で並べ替えて4 7 5 1 8 3 6 2を得て、それから問題は上の列の数を入力して、元の列を出力します
Algorithm
これはどうしますか.このように4 7 5 1 8 3 6 2が入ってきて位置ごとに彼らの順位の4番目を放して1 7番目を放して2がすべて置いた後に1 2 3 4 4 5 7 8 8 8 6 1 3 7 2が入ってきて4その位置はきっとa 7のその位置を放してaを放しますかそれともbを放しますか?このように判断すると1後ろが3 2後ろが5なので2をaにするのは3対5が小さいので、つまりs[4]=s[7]s[5]Code
By the Way
自分ではわかっていても、簡単には言えないような気がします.
abcdeのような文字列の接尾辞文字列はabcde,bcde,cde,cが彼らに番号1 2 3 4 5を与えてから彼らの辞書順に並べ替えて1 2 3 4 5を得た現在問題は与えられた生成の並べ替えであり、生成の最小のその文字列は例を挙げるとabbaabababab接尾辞文字列1 abbaabab,2 bbaababab,3 baababab,4 aab,5 ababab,6 bab,7 abである.8 bそれから彼らの辞書の順序で並べ替えて4 7 5 1 8 3 6 2を得て、それから問題は上の列の数を入力して、元の列を出力します
Algorithm
これはどうしますか.このように4 7 5 1 8 3 6 2が入ってきて位置ごとに彼らの順位の4番目を放して1 7番目を放して2がすべて置いた後に1 2 3 4 4 5 7 8 8 8 6 1 3 7 2が入ってきて4その位置はきっとa 7のその位置を放してaを放しますかそれともbを放しますか?このように判断すると1後ろが3 2後ろが5なので2をaにするのは3対5が小さいので、つまりs[4]=s[7]s[5]
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 500000 + 9;
int a[maxn], b[maxn];
char ans[maxn];
void solve()
{
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(ans, 0, sizeof(ans));
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
a[i]--;
b[a[i]] = i;
}
b[n] = -1;
char ch = 'a';
ans[a[0]] = ch;
for (int i = 1; i < n; i++)
{
if (b[a[i] + 1] < b[a[i - 1] + 1]) ch++;
ans[a[i]] = ch;
if (ch > 'z') break;
}
if (ch > 'z') puts("-1"); else puts(ans);
}
int main()
{
int t;
scanf("%d", &t);
for (int i = 0; i < t; i++)
solve();
}
By the Way
自分ではわかっていても、簡単には言えないような気がします.