#P2178. [NOI2015] 品酒大会

    ID: 1196 远端评测题 1000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2015并查集NOI 系列概率论统计后缀数组SA

[NOI2015] 品酒大会

题目描述

一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战 两个环节,分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项,吸引了众多品酒师参加。

在大会的晚餐上,调酒师 Rainbow 调制了 nn 杯鸡尾酒。这 nn 杯鸡尾酒排成一行,其中第 nn 杯酒 (1in1 ≤ i ≤ n) 被贴上了一个标签 sis_i ,每个标签都是 2626 个小写 英文字母之一。设 str(l,r)str(l, r) 表示第 ll 杯酒到第 rr 杯酒的 rl+1r - l + 1 个标签顺次连接构成的字符串。若 str(p,p0)=str(q,q0)str(p, p_0) = str(q, q_0),其中 1pp0n1 ≤ p ≤ p_0 ≤ n, 1qq0n1 ≤ q ≤ q_0 ≤ n, pqp ≠ qp0p+1=q0q+1=rp_0-p+1 = q_0 - q + 1 = r ,则称第 pp 杯酒与第 qq 杯酒是“ rr 相似” 的。当然两杯“ rr 相似”(r>1r > 1)的酒同时也是“ 11 相似”、“ 22 相似”、……、“ (r1)(r - 1) 相似”的。特别地,对于任意的 1p,qn,pq1 ≤ p ,q ≤ n,p ≠ q,第 pp 杯酒和第 qq 杯酒都 是“ 00 相似”的。

在品尝环节上,品酒师 Freda 轻松地评定了每一杯酒的美味度,凭借其专业的水准和经验成功夺取了“首席品酒家”的称号,其中第 ii 杯酒 (1in1 ≤ i ≤ n) 的 美味度为 aia_i 。现在 Rainbow 公布了挑战环节的问题:本次大会调制的鸡尾酒有一个特点,如果把第 pp 杯酒与第 qq 杯酒调兑在一起,将得到一杯美味度为 ap×aqa_p\times a_q 的 酒。现在请各位品酒师分别对于 r=0,1,2,,n1r = 0,1,2,⋯,n-1 ,统计出有多少种方法可以 选出 22 杯“ rr 相似”的酒,并回答选择 22 杯“rr 相似”的酒调兑可以得到的美味度的最大值。

输入格式

11 行包含 11 个正整数 nn ,表示鸡尾酒的杯数。

22 行包含一个长度为 nn 的字符串 SS,其中第 ii 个字符表示第 ii 杯酒的标签。

33 行包含 nn 个整数,相邻整数之间用单个空格隔开,其中第 ii 个整数表示第 ii 杯酒的美味度 aia_i

输出格式

包括 nn 行。

ii 行输出 22 个整数,中间用单个空格隔开。第 11 个整 数表示选出两杯“ (i1)(i - 1) 相似”的酒的方案数,第 2 个整数表示选出两杯 “ (i1)(i - 1) 相似”的酒调兑可以得到的最大美味度。若不存在两杯“ (i1)(i - 1) 相似” 的酒,这两个数均为 00

10
ponoiiipoi
2 1 4 7 4 8 3 6 4 7
45 56
10 56
3 32
0 0
0 0
0 0
0 0
0 0
0 0
0 0
12
abaabaabaaba
1 -2 3 -4 5 -6 7 -8 9 -10 11 -12

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

提示

【样例说明 1】

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

00 相似:所有 4545 对二元组都是 00 相似的,美味度最大的是 8×7=568 × 7 = 56

11 相似: $(1,8) (2,4) (2,9) (4,9) (5,6) (5,7) (5,10) (6,7) (6,10) (7,10) $,最大的 8×7=568 × 7 = 56

22 相似: (1,8)(4,9)(5,6)(1,8) (4,9) (5,6) ,最大的 4×8=324 × 8 = 32

没有 3,4,5,,93,4,5, ⋯ ,9 相似的两杯酒,故均输出 00

【时限1s,内存512M】