容斥 面试题
共 2 篇真实面经 · 涵盖 中国电信 / 虾皮 等 2 家公司
中国电信 11 月 14 日机考:标签合格统计与网格棋盘差值
中国电信 11 月 14 日机考两道编程题:第一题把含 # 的串切成若干标签,统计首尾字符不同、元音个数为奇数、字母种类不少于 3 种的合格标签个数与长度之和、最大长度;第二题对 0/1 网格按行号列号之和的奇偶给每个 1 赋 ±1 权值,多次询问子矩形内 1 的个数与棋盘加权差值,用两张二维前缀和 O(1) 回答每次询问。
虾皮 11 月 15 日机考笔试:恰好 t 种数字的子数组与迷宫不可达格数
虾皮 2026 年 11 月 15 日机考的两道编程题:第一题统计「恰好包含 t 种不同数字」的连续子数组个数,输入规模 2×10^4,做法是「至多 k 种」的滑动窗口加容斥;第二题在 m×m 的 0/1 迷宫里统计从左上角出发走不到的格子数(含墙格),m 最大 1000,做一次 BFS 后总数减可达数即可。原文在第二题的解析处被服务端截断,这里补全解法。