[语言月赛 202404] 非众数

Luogu
IDLGB3967
Time1000ms
Memory512MB
DifficultyP2
2024O2优化字符串(入门)函数与递归语言月赛
给定一个长度为 $n$ 的字符串 $s$,保证 $s$ 仅包含小写字母,求 $s$ 的非空子串中非众数串的个数。 > **定义:非空子串** > > 用 $s_i$ 表示 $s$ 中的第 $i$ 个字符($1 \leq i \leq n$)。任取两个整数 $i, j$($1 \leq i \leq j \leq n$),将 $s_i, s_{i + 1}, \cdots, s_{j}$ 截取出来按原序排列作为一个新的字符串,则这个字符串叫做 $s$ 的非空子串。 例如,当 $s = \texttt{abcde}$ 时,$\texttt{ab}, \texttt{bcde}, \texttt{c}, \texttt{abcde}$ 都是 $s$ 的非空子串,而 $\texttt{acd}, \texttt{f}, \texttt{ngioasd}, \texttt{" "}$ 都不是 $s$ 的非空子串。 > **定义:非众数串** > > 若字符串 $a$ 中出现次数最多的字符出现的次数不超过 $\lfloor \frac{|a|}{2} \rfloor$,则称字符串 $a$ 为一个**非众数**串。其中 $\lfloor x \rfloor$ 代表 $\leq x$ 的最大整数,$|a|$ 代表 $a$ 的长度。 ## Input 一行一个字符串,表示 $s$。 ## Output 一行一个整数,表示答案。 [samples] ## Note ### 样例 1 解释 其中 $\texttt{ab,aabb}$ 是**非众数**非空子串。 ### 数据范围 对于 $100\%$ 的数据,$1 \le n \le 500$,字符串由小写字母组成。 | 测试点编号 | $n$ | 特殊性质 | | :-: | :-: | :-: | | $1$ | $= 2$ | 无 | | $2, 3$ | $\leq 10$ | 无 | | $4$ | $\leq 500$ | 所有字符相同 | | $5$ | $= 26$ | 所有字符不同 | | $6, 7$ | $\leq 500$ | 字符串内仅可能包含 $\texttt{a,b}$ 两种字母 | | $8 \sim 10$ | $\leq 500$ | 无 |
Samples
Input #1
aabb
Output #1
2
Input #2
fqmdfnc
Output #2
21
API Response (JSON)
{
  "problem": {
    "name": "[语言月赛 202404] 非众数",
    "description": {
      "content": "给定一个长度为 $n$ 的字符串 $s$,保证 $s$ 仅包含小写字母,求 $s$  的非空子串中非众数串的个数。 > **定义:非空子串** > > 用 $s_i$ 表示 $s$ 中的第 $i$ 个字符($1 \\leq i \\leq n$)。任取两个整数 $i, j$($1 \\leq i \\leq j \\leq n$),将 $s_i, s_{i + 1}, \\cdots, s_{j}$ 截取出",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3967"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个长度为 $n$ 的字符串 $s$,保证 $s$ 仅包含小写字母,求 $s$  的非空子串中非众数串的个数。\n\n> **定义:非空子串**\n>\n> 用 $s_i$ 表示 $s$ 中的第 $i$ 个字符($1 \\leq i \\leq n$)。任取两个整数 $i, j$($1 \\leq i \\leq j \\leq n$),将 $s_i, s_{i + 1}, \\cdots, s_{j}$ 截取出...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments