0915电信秋招笔试复盘

1.
题目大意：将一个公比为 m 的 n 项几何数列划分为两个子集，要求一个子集的和不大于另一个，且二者差值最小。

解题思路：
    -> 分类讨论公比 m。当 m=1 时，所有项相等，取 floor(n/2) 项。当 m≥2 时，利用几何级数性质，最大项 a_n 大于前面所有项之和，因此最优策略是将前 n-1 项分给一方，最大项分给另一方。

2.
题目大意：给定数组 a，判断是否对任意 i, j 均满足 a_i ⊕ a_j = i ⊕ j。
解题思路：
    -> 固定 j=1，原式可变形为 a_i = i ⊕ (a_1 ⊕ 1)。令常数 k = a_1 ⊕ 1，则数组所有元素必须满足 a_i = i ⊕ k。基于此式进行 O(n) 线性验证。

3.
题目大意：给定 n，求区间 [1, n] 内所有整数的因子和的总和的奇偶性。

    -> 解题思路：核心数论性质是，一个正整数的因子和为奇数当且仅当该数是完全平方数。问题因此转化为统计区间 [1, n] 内完全平方数的数量，即 floor(sqrt(n))，并判断该数量的奇偶性。
#发面经攒人品#