#131. 【NOI2015】品酒大會(huì)

一年一度的“幻影閣夏日品酒大會(huì)”隆重開幕了。大會(huì)包含品嘗和趣味挑戰(zhàn) 兩個(gè)環(huán)節(jié)，分別向優(yōu)勝者頒發(fā)“首席品酒家”和“首席獵手”兩個(gè)獎(jiǎng)項(xiàng)，吸引了眾多品酒師參加。

在大會(huì)的晚餐上，調(diào)酒師 Rainbow 調(diào)制了 n 杯雞尾酒。這 n 杯雞尾酒排成一行，其中第 n 杯酒 (1 ≤ i ≤ n) 被貼上了一個(gè)標(biāo)簽si，每個(gè)標(biāo)簽都是 26 個(gè)小寫 英文字母之一。設(shè) str(l, r)表示第 l 杯酒到第 r 杯酒的 r ? l + 1 個(gè)標(biāo)簽順次連接構(gòu)成的字符串。若 str(p, po) = str(q, qo)，其中 1 ≤ p ≤ po ≤ n, 1 ≤ q ≤ qo ≤ n, p ≠ q, po ? p + 1 = qo ? q + 1 = r ，則稱第 p 杯酒與第 q 杯酒是“ r 相似” 的。當(dāng)然兩杯“ r 相似”(r > 1)的酒同時(shí)也是“ 1 相似”、“ 2 相似”、……、“ (r ? 1) 相似”的。特別地，對(duì)于任意的 1 ≤ p , q ≤ n ， p ≠ q ，第 p 杯酒和第 q 杯酒都 是“ 0 相似”的。

在品嘗環(huán)節(jié)上，品酒師 Freda 輕松地評(píng)定了每一杯酒的美味度，憑借其專業(yè)的水準(zhǔn)和經(jīng)驗(yàn)成功奪取了“首席品酒家”的稱號(hào)，其中第 i 杯酒 (1 ≤ i ≤ n) 的 美味度為 ai 。現(xiàn)在 Rainbow 公布了挑戰(zhàn)環(huán)節(jié)的問題：本次大會(huì)調(diào)制的雞尾酒有一個(gè)特點(diǎn)，如果把第 p 杯酒與第 q 杯酒調(diào)兌在一起，將得到一杯美味度為 ap*aq 的 酒。現(xiàn)在請(qǐng)各位品酒師分別對(duì)于 r = 0,1,2, ? , n ? 1 ，統(tǒng)計(jì)出有多少種方法可以 選出 2 杯“ r 相似”的酒，并回答選擇 2 杯“ r 相似”的酒調(diào)兌可以得到的美味度的最大值。

輸入格式

輸入文件的第 1 行包含 1個(gè)正整數(shù) n，表示雞尾酒的杯數(shù)。

第 2 行包含一個(gè)長(zhǎng)度為 nn 的字符串 S，其中第 ii 個(gè)字符表示第 ii 杯酒的標(biāo)簽。

第 3 行包含 n 個(gè)整數(shù)，相鄰整數(shù)之間用單個(gè)空格隔開，其中第 ii 個(gè)整數(shù)表示第 ii 杯酒的美味度 aiai。

輸出格式

輸出文件包括 nn 行。第 ii 行輸出 22 個(gè)整數(shù)，中間用單個(gè)空格隔開。第 11 個(gè)整數(shù)表示選出兩杯“(i?1)(i?1)相似”的酒的方案數(shù)，第 22 個(gè)整數(shù)表示選出兩杯“(i?1)(i?1)相似”的酒調(diào)兌可以得到的最大美味度。若不存在兩杯“(i?1)(i?1)相似”的酒，這兩個(gè)數(shù)均為 00。

樣例一

input

10 ponoiiipoi 2 1 4 7 4 8 3 6 4 7

output

45 56 10 56 3 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0

explanation

用二元組 (p,q)(p,q) 表示第 pp 杯酒與第 qq 杯酒。

0 相似：所有 45? 對(duì)二元組都是 00 相似的，美味度最大的是 8×7=568×7=56。

1 相似：(1,8)(1,8) (2,4)(2,4) (2,9)(2,9) (4,9)(4,9) (5,6)(5,6) (5,7)(5,7) (5,10)(5,10) (6,7)(6,7) (6,10)(6,10) (7,10)(7,10)，最大的 8×7=568×7=56。

2? 相似：(1,8)(1,8) (4,9)(4,9) (5,6)(5,6)，最大的 4×8=324×8=32。

沒有 3,4,5,…,93,4,5,…,9 相似的兩杯酒，故均輸出 0。

樣例二

input

12 abaabaabaaba 1 -2 3 -4 5 -6 7 -8 9 -10 11 -12

output

66 120 34 120 15 55 12 40 9 27 7 16 5 7 3 -4 2 -4 1 -4 0 0 0 0

×思路：本題是我在知道是后綴數(shù)組的情況下做的，但是仍然沒有想出來。思路很巧妙：

??????????????????? 1.首先不想最大值的事情，那么我們發(fā)現(xiàn)，對(duì)于兩杯酒r相似，它們的最長(zhǎng)公共前綴會(huì)大于等于r

??????????????????? 2.那么聯(lián)想到height數(shù)組，它本是求對(duì)與兩個(gè)后綴排名相鄰的數(shù)組的最長(zhǎng)公共前綴，所以它表示的是所有的公共前綴最大長(zhǎng)度的兩兩組合

??????????????????? 3,所以我們維護(hù)一個(gè)并查集，按height數(shù)組的值從高到低進(jìn)行排序，每次把那兩個(gè)相關(guān)的后綴所在的集合合并，在合并前把這兩個(gè)集合的siz乘起來作為對(duì)答案的貢獻(xiàn)，這是顯然的，因?yàn)槭前磆eight數(shù)組從高到低來的，所以在集合中的后綴都擁有了大于r的相同的前綴，現(xiàn)在的那兩個(gè)相關(guān)的后綴所關(guān)系到的所有與它們擁有大于r的相同的前綴的后綴，都是擁有了與那兩個(gè)相關(guān)的后綴相同的長(zhǎng)度為r的前綴，所以計(jì)入答案。至于集合內(nèi)部的組合，我們?cè)诮y(tǒng)計(jì)答案的時(shí)候做一下累加即可（當(dāng)然兩杯“ r 相似”(r > 1)的酒同時(shí)也是“ 1 相似”、“ 2 相似”、……、“ (r ? 1) 相似”的。）

?????????????????? 4.再隨意維護(hù)一下那個(gè)最大值即可

#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm>using namespace std;#define LL long long #define pb push_back #define Set(a, v) memset(a, v, sizeof(a)) #define For(i, a, b) for(int i = (a); i <= (int)(b); i++) #define Forr(i, a, b) for(int i = (a); i >= (int)(b); i--)#define MAXN (300000+5) #define INF (1LL<<60)struct node{int h, a, b;bool operator <(const node &rhs)const{return h > rhs.h;} };int n, wine[MAXN], s[MAXN], fa[MAXN], siz[MAXN]; LL deli[MAXN], ans[MAXN]; char rs[MAXN];int c[MAXN], c1[MAXN], c2[MAXN], sa[MAXN], rank[MAXN], height[MAXN]; int Max[MAXN], Min[MAXN]; node nodes[MAXN];void build_sa(int m){int *x = c1, *y = c2, p;For(i, 1, m) c[i] = 0;For(i, 1, n) c[x[i]=s[i]]++;For(i, 1, m) c[i] += c[i-1];Forr(i, n, 1) sa[c[x[i]]--] = i;for(int k = 1; k <= n; k <<= 1){p = 0;For(i, n-k+1, n) y[++p] = i;For(i, 1, n) if(sa[i] > k) y[++p] = sa[i]-k;For(i, 1, m) c[i] = 0;For(i, 1, n) c[x[y[i]]]++;For(i, 1, m) c[i] += c[i-1];Forr(i, n, 1) sa[c[x[y[i]]]--] = y[i];swap(x, y);x[sa[1]] = p = 1;For(i, 2, n)x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k])? p: ++p;if(p >= n) break;m = p;} // For(i, 1, n) printf("sa[%d] = %s\n", i, rs+sa[i]); }void get_height(){For(i, 1, n) rank[sa[i]] = i;int k = 0;For(i, 1, n){if(k) k--;int j = sa[rank[i]-1];while(s[i+k] == s[j+k]) k++;height[rank[i]] = k;} }void height_init(){For(i, 2, n) nodes[i-1] = (node){height[i], sa[i-1], sa[i]};sort(nodes+1, nodes+n); }int find(int x){return x==fa[x]? x: (fa[x]=find(fa[x])); }void solve(){For(i, 0, n) deli[i] = -INF;For(now, 1, n-1){int h = nodes[now].h, a = nodes[now].a, b = nodes[now].b;int u = find(a), v = find(b);ans[h] += (LL)siz[u]*siz[v];fa[u] = v; siz[v] += siz[u];deli[h] = max(deli[h], max((LL)Max[u]*Max[v], (LL)Min[u]*Min[v]));Max[v] = max(Max[v], Max[u]); Min[v] = min(Min[v], Min[u]);}Forr(i, n-2, 0){deli[i] = max(deli[i+1], deli[i]);ans[i] += ans[i+1];}For(i, 0, n-1) printf("%lld %lld\n", ans[i], deli[i]==-INF? 0: deli[i]); }int main(){scanf("%d%s", &n, rs+1);For(i, 1, n){scanf("%d", &wine[i]);s[i] = rs[i]-'a'+1;fa[i] = i; siz[i] = 1; Max[i] = Min[i] = wine[i];}build_sa(26); get_height();height_init(); solve();return 0; }

??????????

轉(zhuǎn)載于:https://www.cnblogs.com/miaomiao1220/p/6642353.html

總結(jié)

以上是生活随笔為你收集整理的NOI 2015 品酒大会的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。