題目描述

一年一度的“幻影閣夏日品酒大會”隆重開幕了。大會包含品嘗和趣味挑戰 兩個環節，分別向優勝者頒發“首席品酒家”和“首席獵手”兩個獎項，吸引了眾多品酒師參加。

在大會的晚餐上，調酒師 Rainbow 調制了 n 杯雞尾酒。這 n 杯雞尾酒排成一行，其中第 n 杯酒 (1 ≤ i ≤ n) 被貼上了一個標簽si，每個標簽都是 26 個小寫 英文字母之一。設 str(l, r)表示第 l 杯酒到第 r 杯酒的 r ? l + 1 個標簽順次連接構成的字符串。若 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 相似” 的。當然兩杯“ r 相似”(r > 1)的酒同時也是“ 1 相似”、“ 2 相似”、……、“ (r ? 1) 相似”的。特別地，對于任意的 1 ≤ p , q ≤ n ， p ≠ q ，第 p 杯酒和第 q 杯酒都 是“ 0 相似”的。

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

輸入輸出格式

輸入格式：

第 1 行包含 1 個正整數 n ，表示雞尾酒的杯數。

第 2 行包含一個長度為 n 的字符串 S，其中第 i 個字符表示第 i 杯酒的標簽。

第 3 行包含 n 個整數，相鄰整數之間用單個空格隔開，其中第 i 個整數表示第 i 杯酒的美味度 ai 。

輸出格式：

包括 n 行。第 i 行輸出 2 個整數，中間用單個空格隔開。第 1 個整 數表示選出兩杯“ (i ? 1) 相似”的酒的方案數，第 2 個整數表示選出兩杯 “ (i ? 1) 相似”的酒調兌可以得到的最大美味度。若不存在兩杯“ (i ? 1) 相似” 的酒，這兩個數均為 0 。

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

后綴數組處理height，然后從后向前掃，用并查集維護同組最大、次大、最小、次小，然后轉移就行了。

吐槽luogu評級黑色太水。

代碼：

#include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 300050 #define inf 1000000001ll #define ll long long int n,a[N],hs[N],rank[N],tr[N],sa[N],h[N]; char s[N]; ll v[N],as1[N],as2[N]; bool cmp(int x,int y,int k) {if(x+k>n||y+k>n)return 0;return rank[x]==rank[y]&&rank[x+k]==rank[y+k]; } void get_sa() {int i,cnt=0;for(i=1;i<=n;i++)a[i]=s[i];for(i=1;i<=n;i++)hs[a[i]]++;for(i=1;i<=200;i++)if(hs[i])tr[i]=++cnt;for(i=1;i<=200;i++)hs[i]+=hs[i-1];for(i=1;i<=n;i++)rank[i]=tr[a[i]],sa[hs[a[i]]--]=i;for(int k=1;cnt!=n;k<<=1){for(i=1;i<=n;i++)hs[i]=0;for(i=1;i<=n;i++)hs[rank[i]]++;for(i=1;i<=n;i++)hs[i]+=hs[i-1];for(i=n;i>=1;i--)if(sa[i]>k)tr[sa[i]-k]=hs[rank[sa[i]-k]]--;for(i=1;i<=k;i++)tr[n-i+1]=hs[rank[n-i+1]]--;for(i=1;i<=n;i++)sa[tr[i]]=i;for(i=1,cnt=0;i<=n;i++)tr[sa[i]]=cmp(sa[i],sa[i-1],k)?cnt:++cnt;for(i=1;i<=n;i++)rank[i]=tr[i];} } void get_h() {for(int i=1;i<=n;i++){if(rank[i]==1)continue;for(int j = max(1,h[rank[i-1]]-1);;j++){if(s[i+j-1]==s[sa[rank[i]-1]+j-1])h[rank[i]]=j;else break;}} } int hed[N],cnt; struct EG {int u,v,nxt; }e[N]; void ae(int f,int u,int v) {e[++cnt].u = u;e[cnt].v = v;e[cnt].nxt = hed[f];hed[f] = cnt; } int fa[N]; ll f[N][4],siz[N]; int findfa(int x) {while(fa[x]!=fa[fa[x]])fa[x]=fa[fa[x]];return fa[x]; } int main() {scanf("%d%s",&n,s+1);get_sa();get_h();for(int i=1;i<=n;i++)scanf("%lld",&v[i]);for(int i=2;i<=n;i++)ae(h[i],sa[i],sa[i-1]);for(int i=1;i<=n;i++){fa[i]=i;siz[i]=1;f[i][0]=v[i];f[i][1]=-inf;f[i][2]=inf;f[i][3]=v[i];}int u,v,f1,f2;ll now = 0;as2[n+1]=-inf*inf;for(int i=n;i>=0;i--){as2[i]=as2[i+1];for(int j=hed[i];j;j=e[j].nxt){u = e[j].u,v = e[j].v;f1=findfa(u),f2=findfa(v);if(f1!=f2){fa[f1]=f2;now-=siz[f1]*(siz[f1]-1)/2;now-=siz[f2]*(siz[f2]-1)/2;siz[f2]+=siz[f1];now+=siz[f2]*(siz[f2]-1)/2;if(f[f1][0]>=f[f2][0]){f[f2][1]=f[f2][0];f[f2][0]=f[f1][0];if(f[f1][1]>f[f2][1]){f[f2][1]=f[f1][1];}}else if(f[f1][0]>f[f2][1]){f[f2][1]=f[f1][0];}as2[i]=max(as2[i],f[f2][0]*f[f2][1]);if(f[f1][3]<=f[f2][3]){f[f2][2]=f[f2][3];f[f2][3]=f[f1][3];if(f[f1][2]<f[f2][3]){f[f2][3]=f[f1][2];}}else if(f[f1][3]<f[f2][2]){f[f2][2]=f[f1][3];}if(f[f2][2]!=inf)as2[i]=max(as2[i],f[f2][2]*f[f2][3]);}}as1[i]=now;}for(int i=0;i<n;i++){if(as2[i]==-inf*inf)as2[i]=0;printf("%lld %lld\n",as1[i],as2[i]);}return 0; }

?

轉載于:https://www.cnblogs.com/LiGuanlin1124/p/9725117.html

總結

以上是生活随笔為你收集整理的[NOI2015]品酒大会的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。