洛谷P2178 品酒大会

题意：若两个字符开始的后面r个字符都一样，则称这两个字符是r相似的。它们也是r-1相似的。

对于r∈[0,n)分别求有多少种方案，其中权值最大方案权值是多少。此处权值是选出的两个字符的权值之积。

解：后缀自动机吊打后缀数组！！！

先看第一问，我们考虑后缀自动机上每个节点的贡献。显然cnt>1的节点才会有贡献。

它会对r ∈ len[fail[x]] + 1 ~ len[x]这一段的答案产生C(cnt_x，2)的贡献。这就是一个区间加法。

有个小问题，如果r减少那么相应的可选的其实会变多，但是此处我们不统计，那些会在以另一个字符结尾的别的节点上考虑到。

这样第一问就解决了。第二问？发现问题很大...一个节点的每个串都是结尾相同，开头不同。那么开头的权值之积就不好维护。

因为结尾相同，所以考虑反着建后缀自动机，然后就变成了开头相同了。那么如何维护乘积最大值呢？

考虑到一个节点的末尾所在位置，也就是它的right集合。显然就是fail树的子树中所有在主链上的节点。

于是每个点维护子树最大值即可。因为有负数所以还要最小值。

这样一个节点对第二问的贡献就是区间取max了。这两问的操作都可以用线段树搞定。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 typedef long long LL;

 const int N = ;

 int tr[N][], tot = , fail[N], len[N], cnt[N], bin[N], topo[N], last = , val[N], n;

 int max1[N], max2[N], min1[N], min2[N];

 char str[N];

 LL tag[N << ], large[N << ];

 inline void insert(char c) {

     int f = c - 'a';

     int p = last, np = ++tot;

     last = np;

     len[np] = len[p] + ;

     cnt[np] = ;

     while(p && !tr[p][f]) {

         tr[p][f] = np;

         p = fail[p];

     }

     if(!p) {

         fail[np] = ;

     }

     else {

         int Q = tr[p][f];

         if(len[Q] == len[p] + ) {

             fail[np] = Q;

         }

         else {

             int nQ = ++tot;

             len[nQ] = len[p] + ;

             fail[nQ] = fail[Q];

             fail[Q] = fail[np] = nQ;

             memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));

             while(tr[p][f] == Q) {

                 tr[p][f] = nQ;

                 p = fail[p];

             }

         }

     }

     return;

 }

 inline void update(int x, int y) {

     int t[];

     t[] = max1[x];

     t[] = max2[x];

     t[] = max1[y];

     t[] = max2[y];

     std::sort(t, t + );

     max1[x] = t[];

     max2[x] = t[];

     t[] = min1[x];

     t[] = min2[x];

     t[] = min1[y];

     t[] = min2[y];

     std::sort(t, t + );

     min1[x] = t[];

     min2[x] = t[];

     return;

 }

 inline void prework() {

     for(int i = ; i <= tot; i++) {

         bin[len[i]]++;

     }

     for(int i = ; i <= tot; i++) {

         bin[i] += bin[i - ];

     }

     for(int i = ; i <= tot; i++) {

         topo[bin[len[i]]--] = i;

     }

     for(int i = tot; i >= ; i--) {

         int a = topo[i];

         cnt[fail[a]] += cnt[a];

         update(fail[a], a);

     }

     return;

 }

 inline void pushdown(int o) {

     if(tag[o]) {

         tag[o << ] += tag[o];

         tag[o <<  | ] += tag[o];

         tag[o] = ;

     }

     large[o << ] = std::max(large[o << ], large[o]);

     large[o <<  | ] = std::max(large[o <<  | ], large[o]);

     return;

 }

 void add(int L, int R, LL v, int l, int r, int o) {

     if(L <= l && r <= R) {

         tag[o] += v;

         return;

     }

     int mid = (l + r) >> ;

     pushdown(o);

     if(L <= mid) {

         add(L, R, v, l, mid, o << );

     }

     if(mid < R) {

         add(L, R, v, mid + , r, o <<  | );

     }

     return;

 }

 void out(int l, int r, int o) {

     if(l == r) {

         if(r != n) {

             printf("%lld %lld \n", tag[o], tag[o] ? large[o] : );

         }

         return;

     }

     int mid = (l + r) >> ;

     pushdown(o);

     out(l, mid, o << );

     out(mid + , r, o <<  | );

     return;

 }

 void change(int L, int R, LL v, int l, int r, int o) {

     if(v <= large[o]) {

         return;

     }

     if(L <= l && r <= R) {

         large[o] = v;

         return;

     }

     int mid = (l + r) >> ;

     pushdown(o);

     if(L <= mid) {

         change(L, R, v, l, mid, o << );

     }

     if(mid < R) {

         change(L, R, v, mid + , r, o <<  | );

     }

     return;

 }

 int main() {

     memset(max1, ~0x3f, sizeof(max1));

     memset(max2, ~0x3f, sizeof(max2));

     memset(min1, 0x3f, sizeof(min1));

     memset(min2, 0x3f, sizeof(min2));

     memset(large, ~0x3f, sizeof(large));

     scanf("%d", &n);

     scanf("%s", str + );

     int l1 = -0x3f3f3f3f, l2 = -0x3f3f3f3f, s1 = 0x3f3f3f3f, s2 = 0x3f3f3f3f;

     for(int i = ; i <= n; i++) {

         scanf("%d", &val[i]);

         if(l1 < val[i]) {

             l2 = l1;

             l1 = val[i];

         }

         else if(l2 < val[i]) {

             l2 = val[i];

         }

         if(s1 > val[i]) {

             s2 = s1;

             s1 = val[i];

         }

         else if(s2 > val[i]) {

             s2 = val[i];

         }

     }

     for(int i = n; i >= ; i--) {

         insert(str[i]);

         max1[last] = min1[last] = val[i];

     }

     prework();

     //

     for(int i = ; i <= tot; i++) {

         if(cnt[i] < ) {

             continue;

         }

         // len[fail[i]] + 1  ~  len[i]

         add(len[fail[i]] + , len[i], 1ll * cnt[i] * (cnt[i] - ) / , , n, );

         change(len[fail[i]] + , len[i], std::max(1ll * max1[i] * max2[i], 1ll * min1[i] * min2[i]), , n, );

     }

     printf("%lld %lld \n", 1ll * n * (n - ) / , std::max(1ll * l1 * l2, 1ll * s1 * s2));

     out(, n, );

     return ;

 }

AC代码

巴特西

洛谷P2178 品酒大会

最新文章

热门文章