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
#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
自分ではわかっていても、簡単には言えないような気がします.