面灵AI→

中国电信 11 月 14 日机考:标签合格统计与网格棋盘差值

轮次
笔试
时间
2026-11
来源
牛客网

《面试题目》

第 1 题 — 标签合格统计

给定一个只含小写字母与分隔字符 # 的串,这些分隔字符会把它拆分成若干段非空的标签。

对某个标签,若下面三条同时成立就把它算作合格:

  1. 它的第一个字符和最后一个字符不相同;
  2. 其中属于元音 a/e/i/o/u 的字符个数是奇数;
  3. 它内部出现的字母种类不少于 3 种。

请求出合格标签一共有几个、全部合格标签的长度加起来是多少,以及合格标签里最长的那个有多长。统计字母种类时,只看这一个标签自身含有哪些互不相同的小写字母。

输入描述:一行,给出字符串 t,其长度记为 L(1 ≤ L ≤ 2×10⁵)。t 的开头和结尾都不会是 #,任意两个相邻的 # 中间至少夹着一个小写字母。t 里只会出现小写字母和 #。

输出描述:在一行内输出三个整数:合格标签的个数、全部合格标签的长度之和、合格标签中的最大长度。如果找不到任何合格的标签,那么后两个整数也都输出 0。

样例输入:queen#ab#idea#strip#cub

样例输出:4 17 5

样例说明:

  1. queen:开头 q、结尾 n 互异,元音 u、e、e 共 3 个,字母种类 4 种,合格。
  2. ab:字母种类只有 2 种,不合格。
  3. idea:开头 i、结尾 a 互异,元音 i、e、a 共 3 个,字母种类 4 种,合格。
  4. strip:首尾 s、p 不同,元音只有 i 一个,字母种类 5 种,合格。
  5. cub:首尾 c、b 不同,元音只有 u 一个,字母种类 3 种,合格。

合格标签共 4 个,长度之和为 5 + 4 + 5 + 3 = 17,其中最长的长度为 5。

第 2 题 — 网格棋盘差值

小林手里有一张网格,每个格子里写着 0 或 1,行号和列号都从 1 开始编。每一次询问会给出一个闭合的子矩形,需要数出其中 1 的个数,同时算出它的棋盘加权差值:对坐标为 (x, y) 的格子,若 x + y 是偶数,格子里的 1 记 +1;若 x + y 是奇数,则这个 1 记 −1;写着 0 的格子不计入。

输入描述:首行给出三个整数 H, W, k(1 ≤ H, W ≤ 300;1 ≤ H × W ≤ 10⁵;1 ≤ k ≤ 10⁵),依次为网格的行数、列数以及询问的个数。随后共 H 行,其中第 x 行是一个长为 W 的串,仅由 0 和 1 构成,描述网格的第 x 行。再往后共 k 行,每行四个整数 x₁, y₁, x₂, y₂(1 ≤ x₁ ≤ x₂ ≤ H;1 ≤ y₁ ≤ y₂ ≤ W),表示所询问的子矩形覆盖第 x₁ 行至第 x₂ 行、第 y₁ 列至第 y₂ 列。

输出描述:每次询问单独占一行,输出两个整数:先是该子矩形里 1 的个数,再是它的棋盘加权差值。

样例输入:

3 4 3
0110
1101
1011
1 2 1 2
2 1 3 2
1 1 3 4

样例输出:

1 -1
3 1
8 2

样例说明:

  1. 询问 1 2 1 2:只有格子 (1,2),它是 1 且 1+2 为奇数,记 −1,所以输出 1 −1。
  2. 询问 2 1 3 2:1 落在 (2,1)、(2,2)、(3,1),分别记 −1、+1、+1,共 3 个,差值为 1。
  3. 询问 1 1 3 4:整张网格有 8 个 1,其中 (1,3)、(2,2)、(2,4)、(3,1)、(3,3) 记 +1,(1,2)、(2,1)、(3,4) 记 −1,差值为 5 − 3 = 2。

《参考解析》

第 1 题:单趟扫描分标签。按 # 切分后逐个标签检查即可,题目保证标签非空。对每个标签同时统计两样东西:元音 a/e/i/o/u 的出现次数,以及出现过的不同字母种类数(用一个长度 26 的布尔数组记录)。三条判据取与:首字符与末字符不同、元音个数为奇数、种类数不少于 3。合格的标签把个数加 1、长度总和加上自身长度、最大值取较大者。没有合格标签时三个答案保持初值 0。时间复杂度 O(L),每个字符只被扫一次;空间 O(L)(Java 的 split 会额外分配一份标签数组,C++ 的指针扫描不额外分配)。

第 2 题:两张二维前缀和。两个要求的量都能写成「每个格子给一个权值,求子矩形权值和」:1 的个数用权值 1(格子是 1 时),棋盘差值用权值 +1(格子是 1 且 x+y 为偶数)或 −1(格子是 1 且 x+y 为奇数)。对两种权值各建一张二维前缀和,询问时用容斥 S(x₂,y₂) − S(x₁−1,y₂) − S(x₂,y₁−1) + S(x₁−1,y₁−1) 取子矩形和,两张表各算一次即可同时输出个数与差值。k 到 10⁵,逐格统计是 O(HWk) 会超时,前缀和把每次询问压到 O(1);预处理与空间都是 O(HW)。

容易踩的坑。第一题的「字母种类」只看单个标签内部,不能拿全局的字符集算;元音判定是小写 a/e/i/o/u,不含 y。第二题的奇偶判定用 x + y(行号列号都从 1 开始),写成 (x+y) % 2 时注意负数取模;差值可能为负,输出用有符号整数,别用无符号类型直接打印。