AT_abc264_g.[ABC264G] String Fair

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在字符串品评会上，对于仅由小写英文字母组成的非空字符串 $S$ ，将决定其“美丽度”。

字符串 $S$ 的美丽度被定义为 $N$ 个评审项目得分的总和。对于 $i=1,2,\ldots,N$ ，第 $i$ 个评审项目的得分为“字符串 $T_i$ （输入中给出，长度不超过 $3$ ）在 $S$ 中作为连续子串出现的次数”乘以 $P_i$ 。

请输出仅由小写英文字母组成的非空字符串 $S$ 所能取得的最大美丽度。如果美丽度可以取得任意大的值，则输出 Infinity。

这里，字符串 $U=U_1U_2\ldots U_{|U|}$ 中字符串 $V$ 作为连续子串出现的次数，指满足 $1\leq i\leq |U|-|V|+1$ 且 $U_iU_{i+1}\ldots U_{i+|V|-1}=V$ 的整数 $i$ 的个数。

输入格式

输入以以下格式从标准输入给出。

$N$
$T_1$ $P_1$
$T_2$ $P_2$
$\vdots$
$T_N$ $P_N$

输出格式

请输出仅由小写英文字母组成的非空字符串 $S$ 所能取得的最大美丽度。如果美丽度可以取得任意大的值，则输出 Infinity。

输入输出样例

输入#1
```
3
a -5
ab 10
ba -20
```
输出#1
```
Infinity
```

输入#2

28
a -5
ab 10
ba -20
bb -20
bc -20
bd -20
be -20
bf -20
bg -20
bh -20
bi -20
bj -20
bk -20
bl -20
bm -20
bn -20
bo -20
bp -20
bq -20
br -20
bs -20
bt -20
bu -20
bv -20
bw -20
bx -20
by -20
bz -20

输出#2

输入#3

26
a -1
b -1
c -1
d -1
e -1
f -1
g -1
h -1
i -1
j -1
k -1
l -1
m -1
n -1
o -1
p -1
q -1
r -1
s -1
t -1
u -1
v -1
w -1
x -1
y -1
z -1

输出#3

-1

说明/提示

限制条件

$1 \leq N \leq 18278$
$N$ 为整数
$T_i$ 是仅由小写英文字母组成、长度为 $1$ 到 $3$ 的字符串
$i \neq j \Rightarrow T_i \neq T_j$
$-10^9 \leq P_i \leq 10^9$
$P_i$ 为整数

样例解释 1

例如，对于 $S = \text{abzabz}$ ，

第 $1$ 个评审项目的得分为，a 作为 $S$ 的连续子串出现了 $2$ 次，因此 $2 \times (-5) = -10$ 分；
第 $2$ 个评审项目的得分为，ab 作为 $S$ 的连续子串出现了 $2$ 次，因此 $2 \times 10 = 20$ 分；
第 $3$ 个评审项目的得分为，ba 作为 $S$ 的连续子串出现了 $0$ 次，因此 $0 \times (-20) = 0$ 分；
所以 $S$ 的美丽度为 $(-10) + 20 + 0 = 10$ 。
另一个例子， $S = \text{abzabzabz}$ 时，
第 $1$ 个评审项目的得分为，a 作为 $S$ 的连续子串出现了 $3$ 次，因此 $3 \times (-5) = -15$ 分；
第 $2$ 个评审项目的得分为，ab 作为 $S$ 的连续子串出现了 $3$ 次，因此 $3 \times 10 = 30$ 分；
第 $3$ 个评审项目的得分为，ba 作为 $S$ 的连续子串出现了 $0$ 次，因此 $0 \times (-20) = 0$ 分；
所以 $S$ 的美丽度为 $(-15) + 30 + 0 = 15$ 。
一般地，对于正整数 $X$ ，将 abz 重复 $X$ 次得到的字符串的美丽度为 $5X$ 。
由于 $S$ 的美丽度可以取得任意大的值，因此输出 Infinity。

样例解释 2

$S = \text{ab}$ 可以取得最大美丽度。

样例解释 3

请注意， $S$ 必须是非空字符串。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页