0920b站笔试复盘

#牛客AI配图神器#1.
题目大意：在二维网格中，找出所有仅与一个独立空地相邻的'x'字符连通块，并汇总每个此类空地可以消除的'x'字符总数。

解题思路：BFS或DFS遍历网格以识别所有'x'连通块。对于每个连通块，统计其大小及所有相邻的空地坐标集合。若一个连通块的相邻空地集合大小为1，则将该连通块的大小累加至该唯一空地对应的消灭数上。

2.
题目大意：计算多个形如 (x ± d) 的一次多项式乘积展开后，x一次项的系数对特定模数取模的结果。

解题思路：根据韦达定理，x一次项的系数等于所有因子常数项中，去掉任意一个后剩下所有项乘积的总和。为避免 O(m^2) 的暴力计算，可预处理出所有常数项的前缀积和后缀积数组。对于第 i 个因子，其对总系数的贡献为 pre[i-1] * suf[i+1]，总系数即为所有贡献之和。

3.
题目大意：将一个大于等于8的整数n分解为四个质数之和。
解题思路：根据n的奇偶性，先固定前两个质数将问题简化为将一个偶数分解为两个质数之和。若n为偶数，取2, 2，剩余目标为 n-4；若n为奇数，取2, 3，剩余目标为 n-5。之后，遍历查找一个质数p，并检验剩余目标减去p的结果是否也为质数。

#发面经攒人品#