AcWing 1004. 品酒大会 题解

题目分析

本题描述了“幻影阁夏日品酒大会”的相关背景，调酒师调制了(n)杯鸡尾酒，每杯酒有一个由小写英文字母组成的标签，同时每杯酒有一个美味度。题目定义了“(r)相似”的概念，要求对于(r = 0, 1, 2, \cdots, n - 1)，统计选出(2)杯“(r)相似”的酒的方法数，并求出选择(2)杯“(r)相似”的酒调兑可以得到的美味度的最大值。

解题思路

本题主要通过后缀数组和并查集来解决。
1. 首先利用基数排序和倍增算法构造后缀数组(sa)和(height)数组，(height)数组记录了相邻后缀的最长公共前缀长度。
2. 然后通过并查集来合并具有相同(height)值的后缀，在合并过程中统计“(r)相似”的酒的对数以及调兑后美味度的最大值。

代码逐段分析

1. 头文件和全局变量定义

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;

const int N = 300010;
const LL INF = 2e18;

int n, m;
char s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];
int w[N], p[N], sz[N];
LL max1[N], max2[N], min1[N], min2[N];
vector<int> hs[N];
PLL ans[N];

• 引入必要的头文件，包括输入输出、字符串操作、算法和向量相关的头文件。
• 使用宏定义x和y分别表示pair类型的第一个和第二个元素。
• 定义LL为long long的别名，PLL为pair<LL, LL>的别名。
• 定义常量(N)表示最大的字符串长度，INF表示一个极大值。
• 变量(n)表示鸡尾酒的杯数，(m)在基数排序中用于表示字符的种类数。
• s[N]存储鸡尾酒标签组成的字符串。
• sa[N]、x[N]、y[N]、c[N]、rk[N]、height[N]用于构造和存储后缀数组相关信息。
• w[N]存储每杯酒的美味度。
• p[N]、sz[N]用于并查集，p[N]存储每个元素的父节点，sz[N]存储每个集合的大小。
• max1[N]、max2[N]、min1[N]、min2[N]分别存储每个集合中美味度的最大值、次大值、最小值、次小值。
• hs[N]是一个向量数组，用于存储具有相同(height)值的后缀的下标。

• ans[N]用于存储最终的答案，每个元素是一个PLL类型，分别表示“(r)相似”的酒的对数和调兑后美味度的最大值。

• 构造后缀数组函数

void get_sa()
{
    for (int i = 1; i <= n; i ++ ) c[x[i] = s[i]] ++ ;
    for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
    for (int i = n; i; i -- ) sa[c[x[i]] -- ] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for (int i = n - k + 1; i <= n; i ++ ) y[ ++ num] = i;
        for (int i = 1; i <= n; i ++ )
            if (sa[i] > k)
                y[ ++ num] = sa[i] - k;
        for (int i = 1; i <= m; i ++ ) c[i] = 0;
        for (int i = 1; i <= n; i ++ ) c[x[i]] ++ ;
        for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
        for (int i = n; i; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1, num = 1;
        for (int i = 2; i <= n; i ++ )
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        if (num == n) break;
        m = num;
    }
}

• 该函数通过基数排序和倍增算法构造后缀数组(sa)。
• 首先进行第一轮基数排序，统计每个字符的出现次数并确定初始排名。

• 然后通过倍增的方式，每一轮根据上一轮的结果重新排序，直到所有后缀的排名都不同。

• 计算Height数组函数

void get_height()
{
    for (int i = 1; i <= n; i ++ ) rk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; i ++ )
    {
        if (rk[i] == 1) continue;
        if (k) k -- ;
        int j = sa[rk[i] - 1];
        while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++ ;
        height[rk[i]] = k;
    }
}

• 该函数用于计算(height)数组，根据后缀数组(sa)先计算出(rk)数组（(sa)的逆数组）。

• 然后从第二个后缀开始，逐步计算每个后缀与前一个后缀的最长公共前缀长度并存储在(height)数组中。

• 并查集查找函数

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

• 并查集的查找函数，用于查找元素(x)所在集合的根节点，同时进行路径压缩。

• 计算组合数函数

LL get(int x)
{
    return x * (x - 1ll) / 2;
}

• 计算从(x)个元素中选(2)个元素的组合数，即(C_{x}^2 = \frac{x(x - 1)}{2})。

• 计算答案函数

PLL calc(int r)
{
    static LL cnt = 0, maxv = -INF;

    for (auto x: hs[r])
    {
        int a = find(x - 1), b = find(x);
        cnt -= get(sz[a]) + get(sz[b]);
        p[a] = b;
        sz[b] += sz[a];
        cnt += get(sz[b]);
        if (max1[a] >= max1[b])
        {
            max2[b] = max(max1[b], max2[a]);
            max1[b] = max1[a];
        }
        else if (max1[a] > max2[b]) max2[b] = max1[a];
        if (min1[a] <= min1[b])
        {
            min2[b] = min(min1[b], min2[a]);
            min1[b] = min1[a];
        }
        else if (min1[a] < min2[b]) min2[b] = min1[a];
        maxv = max(maxv, max(max1[b] * max2[b], min1[b] * min2[b]));
    }

    if (maxv == -INF) return {cnt, 0};
    return {cnt, maxv};
}

• 该函数用于计算“(r)相似”的酒的对数以及调兑后美味度的最大值。
• 遍历具有相同(height)值（等于(r)）的后缀下标：
  • 先通过并查集找到两个相邻后缀所在集合的根节点(a)和(b)。
  • 从当前的对数统计中减去(a)和(b)集合原来的组合数，然后合并(a)和(b)集合，更新集合大小和对数统计。
  • 合并集合时，更新集合中美味度的最大值、次大值、最小值、次小值。
  • 计算调兑后美味度的最大值，取当前最大值和新计算的最大值（集合中最大两个值的乘积或最小两个值的乘积）中的较大值。

• 如果最终最大值仍为初始的极小值(-INF)，说明没有“(r)相似”的酒，返回对数和(0)；否则返回对数和计算得到的最大值。

• 主函数

int main()
{
    scanf("%d", &n), m = 122;
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    get_sa();
    get_height();
    for (int i = 2; i <= n; i ++ ) hs[height[i]].push_back(i);

    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i, sz[i] = 1;
        max1[i] = min1[i] = w[sa[i]];
        max2[i] = -INF, min2[i] = INF;
    }

    for (int i = n - 1; i >= 0; i -- ) ans[i] = calc(i);
    for (int i = 0; i < n; i ++ ) printf("%lld %lld\n", ans[i].x, ans[i].y);

    return 0;
}

• 读入鸡尾酒的杯数(n)，初始化(m)为(122)（考虑字符的ASCII码范围）。
• 读入鸡尾酒标签字符串和每杯酒的美味度。
• 构造后缀数组并计算(height)数组。
• 将具有相同(height)值的后缀下标存入对应的向量中。
• 初始化并查集相关数组和美味度相关数组。
• 从(r = n - 1)到(r = 0)，依次调用calc函数计算答案并存入ans数组。
• 输出每一个(r)对应的答案，即“(r)相似”的酒的对数和调兑后美味度的最大值。

时间复杂度分析

• 构造后缀数组和计算(height)数组的时间复杂度为(O(n \log n))。
• 后续处理并查集和计算答案的部分，对于每个(r)，遍历具有相同(height)值的后缀，时间复杂度为(O(n))，总共(n)个(r)，所以这部分时间复杂度为(O(n^2))。但由于(height)数组的性质，实际运行时效率会高于(O(n^2))。总体时间复杂度近似为(O(n \log n))。

空间复杂度分析

主要空间消耗在于存储各种数组和向量，空间复杂度为(O(n))。