【链接】h在这里写链接


【题意】


    给你一个长度为n的字符串s;

    标志了每一杯酒;

    以及n个数字,表示每一杯酒的美味度ai。

    两杯酒(i,j)称为r相似

    当且仅当s的后缀i和后缀j的lcp>=r

    然后问你r相似的酒里面任意两个酒的ai*aj的最大值.

    以及r相似的酒的对数 (i<j)

【题解】


    后缀数组+并查集.



    如果连续出现了一段height值大于k的。

    就说明这一段后缀的lcp至少为k

    ->肯定是k相似的酒。

    那么我们就从height值最大的考虑。

    单个height单个height地考虑。

    这个height如果为k;

    那么因为是从大到小的。

    所以之前的height肯定>=k;

    那么如果我们此时把i和i-1并在一起。

    我们并起来的这两个集合里的任意两个后缀肯定都是k相似的。

    ->因为它中间会有一个height[i]=k,那么根据lcp的计算规则。

        两个集合里的后缀任意两两组合都是lcp==k的。

    然后我们再把k+1相似的答案累加一下。就能求出所有的答案了。

    并查集维护一下最大值、最小值就好.



    这种单个ai*aj的问题

    感觉都能用(a1+a2..) * (a3 + a4...)的形式来搞



    求出height数组;

    按照height数组从大到小排;

    ->记录每个height是排名第几的后缀的height;



    然后从最大的height开始逆序枚举;

    答案累加上相似值为i+1的对数,最大值和之前的一样。

    把这个height[i]的i和i-1合并在一起。

        对数递增两个集合的大小,最大值尝试更改一下。

    这个集合是排名的集合。

        ->排名第i一开始单独一个集合,大小为1,最大值、最小值都为val[Sa[i]];

【错的次数】


0

【反思】


大的heigth不影响小的height.
用并查集把比它大的连接起来。
保证lcp为i.

【代码】

#include<bits/stdc++.h>
using namespace std;
#define ll long long const int N = 3e5;
const int MAX_CHAR = 255;//每个数字的最大值。
char s[N + 10];//如果是数字,就写成int s[N+10]就好,从0开始存
int Sa[N + 10], T1[N + 10], T2[N + 10], C[N+10];
int Height[N + 10], Rank[N + 10];
ll a[N+10],sum[N+10],ans[N+10];
ll cnt[N+10],zd[N+10],zx[N+10];
int f[N+10];
pair <int,int> temp[N+10]; void build_Sa(int n, int m) {
int i, *x = T1, *y = T2;
for (i = 0; i<m; i++) C[i] = 0;
for (i = 0; i<n; i++) C[x[i] = s[i]]++;
for (i = 1; i<m; i++) C[i] += C[i - 1];
for (i = n - 1; i >= 0; i--) Sa[--C[x[i]]] = i;
for (int k = 1; k <= n; k <<= 1)
{
int p = 0;
for (i = n - k; i<n; i++) y[p++] = i;
for (i = 0; i<n; i++) if (Sa[i] >= k) y[p++] = Sa[i] - k;
for (i = 0; i<m; i++) C[i] = 0;
for (i = 0; i<n; i++) C[x[y[i]]]++;
for (i = 1; i<m; i++) C[i] += C[i - 1];
for (i = n - 1; i >= 0; i--) Sa[--C[x[y[i]]]] = y[i];
swap(x, y);
p = 1; x[Sa[0]] = 0;
for (i = 1; i<n; i++)
x[Sa[i]] = y[Sa[i - 1]] == y[Sa[i]] && y[Sa[i - 1] + k] == y[Sa[i] + k] ? p - 1 : p++;
if (p >= n) break;
m = p;
}
} void getHeight(int n)
{
int i, j, k = 0;
for (i = 1; i <= n; i++) Rank[Sa[i]] = i;
for (i = 0; i<n; i++) {
if (k) k--;
j = Sa[Rank[i] - 1];
while (s[i + k] == s[j + k]) k++;
Height[Rank[i]] = k;
}
} int ff(int x)
{
if (f[x]==x) return x;
else
return f[x] = ff(f[x]);
} int main() {
//freopen("F:\\rush.txt","r",stdin);
int n;
scanf("%d",&n);
scanf("%s", s);
for (int i = 0;i < n;i++) scanf("%lld",&a[i]); s[n] = 0;
build_Sa(n + 1, MAX_CHAR);//注意调用n+1
getHeight(n); for (int i = 2;i <= n;i++)
{
temp[i-1].first = Height[i];
temp[i-1].second = i;
} for (int i = 1;i <= n;i++)
{
f[i] = i;
cnt[i] = 1;
zd[i] = zx[i] = a[Sa[i]];
} sort(temp+1,temp+1+n-1);
reverse(temp+1,temp+1+n-1); for (int i = 0;i <= n-1;i++)
ans[i] = -1e18-10; int j = 1;
for (int r = temp[1].first;r >= 0;r--)
{
sum[r]=sum[r+1],ans[r] = ans[r+1];
for ( ;j <= n-1 && temp[j].first==r;j++)
{
int x = ff(temp[j].second),y = (temp[j].second-1);
sum[r] += cnt[x]*cnt[y];
ans[r] = max(ans[r],zd[x]*zd[y]);
ans[r] = max(ans[r],zx[x]*zx[y]);
f[y] = x;
cnt[x] += cnt[y];
zd[x] = max(zd[x],zd[y]);
zx[x] = min(zx[x],zx[y]);
}
} for (int i = 0;i <= n-1;i++)
printf("%lld %lld\n",sum[i],sum[i]==0?0:ans[i]);
return 0;
}
05-11 22:20
查看更多