BZOJ3325 [Scoi2013]密码【Manacher】【构造】【贪心】

Description

Fish是一条生活在海里的鱼。有一天他很无聊，就到处去寻宝。他找到了位于海底深处的宫殿，但是一扇带有密码锁的大门却阻止了他的前进。通过翻阅古籍，Fish 得知了这个密码的相关信息：

该密码的长度为N。
密码仅含小写字母。
以每一个字符为中心的最长回文串长度。
以每两个相邻字符的间隙为中心的最长回文串长度。

很快Fish 发现可能有无数种满足条件的密码。经过分析，他觉得这些密码中字典序最小的一个最有可能是答案，你能帮他找到这个密码么？

注意：对于两个串A和B，如果它们的前i个字符都相同，而A的第i+1个字符比B的第i+1个字符小，那么认为是则称密码A 的字典序小于密码B 的字典序，例如字符串abc 字典序小于字符串acb。如果密码A的字典序比其他所有满足条件的密码的字典序都小，则密码A是这些密码中字典序最小的一个。

Input

输入由三行组成。

第一行仅含一个整数N，表示密码的长度。

第二行包含N 个整数，表示以每个字符为中心的最长回文串长度。

第三行包含N - 1 个整数，表示每两个相邻字符的间隙为中心的最长回文串长度。

对于20% 的数据，1 <= n <= 100。

另有30% 的数据，1 <= n <= 1000。

最后50% 的数据，1 <= n <= 10^5。

Output

输出仅一行。输出满足条件的最小字典序密码。古籍中的信息是一定正确的，故一定存在满足条件的密码。

Sample Input

Sample #1

3

1 1 1

0 0

Sample #2

3

1 3 1

0 0

Sample #3

3

1 3 1

2 2

Sample Output

Sample #1

abc

Sample #2

aba

Sample #3

aaa

HINT

思路

因为有了每个点为中心的回文串长度

所以可以把前面的串的字符覆盖到后面

每次只需要把回文串可以覆盖到的最右端点更新一下

如果有延伸就可以直接复制

然后还要记录下每个位置不能填哪些值

所以就每次暴力贪心枚举当前的可以填的最小的字符

然后就可以了

//Author: dream_maker

#include<bits/stdc++.h>

using namespace std;

//----------------------------------------------

//typename

typedef long long ll;

//convenient for

#define fu(a, b, c) for (int a = b; a <= c; ++a)

#define fd(a, b, c) for (int a = b; a >= c; --a)

#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)

//inf of different typename

const int INF_of_int = 1e9;

const ll INF_of_ll = 1e18;

//fast read and write

template <typename T>

void Read(T &x) {

  bool w = 1;x = 0;

  char c = getchar();

  while (!isdigit(c) && c != '-') c = getchar();

  if (c == '-') w = 0, c = getchar();

  while (isdigit(c)) {

    x = (x<<1) + (x<<3) + c -'0';

    c = getchar();

  }

  if (!w) x = -x;

}

template <typename T>

void Write(T x) {

  if (x < 0) {

    putchar('-');

    x = -x;

  }

  if (x > 9) Write(x / 10);

  putchar(x % 10 + '0');

}

//----------------------------------------------

const int N = 1e5 + 10;

bool vis[N][26] = {0};

int n, p1[N], p2[N];

int ans[N];

int getnum(int id) {

  fu(i, 0, 25)

    if (!vis[id][i])

      return i;

}

int main() {

  Read(n);

  memset(ans, -1, sizeof(ans));

  fu(i, 1, n) Read(p1[i]), p1[i] = (p1[i] + 1) >> 1;

  fu(i, 1, n - 1) Read(p2[i]), p2[i] = p2[i] >> 1;

  int maxp = 0;

  fu(i, 1, n) {

    if (ans[i] == -1) {

      ans[i] = getnum(i);

      maxp = max(maxp, i);

    }

    fu(j, maxp + 1, i + p1[i] - 1) ans[j] = ans[i * 2 - j];

    vis[i + p1[i]][ans[i - p1[i]]] = 1;

    fu(j, maxp + 1, i + p2[i]) ans[j] = ans[i * 2 - j + 1];

    vis[i + p2[i] + 1][ans[i - p2[i]]] = 1;

    maxp = max(maxp, max(i + p1[i] - 1, i + p2[i]));

  }

  fu(i, 1, n) putchar('a' + ans[i]);

  return 0;

}

巴特西