0816科大讯飞秋招笔试复盘三道题

#秋招笔面试记录#

------------------------------------

题目一：
题目大意：
有 n (1 <= n <= 1e5) 本书，分为精装本和普通本。你必须执行恰好 k (1 <= k <= 1e9) 次“装帧转换”操作（精装变平装，或平装变精装）。问操作结束后，最多能有多少本精装本。

解法思路：
这是一个贪心问题。为了最大化精装本数量，应该优先将平装本转换为精装本。统计初始的平装本数量 low_cnt。若 k <= low_cnt，说明操作次数不足以把所有平装本都转换，此时最优策略是花费 k 次操作将 k 本平装本变为精装本，最终精装本数量为 初始数量 + k。若 k > low_cnt，说明可以先把所有平装本都转换成精装本，此时书架上全是精装本，还剩下 k - low_cnt 次操作。对于剩下的操作，每两次操作（精装->平装->精装）可以抵消，不影响最终结果。因此，如果剩余操作是偶数次，最终可以保持全精装；如果是奇数次，则必须消耗一次操作，使得一本精装书变为平装，最终有 n-1 本精装。

------------------------------------

题目二：

题目大意：
给定一个 n (2 <= n <= 2e5) 个音符的非严格递增序列 a，和一个音高增量 m (1 <= m <= 1e9)。你可以执行一次操作：选择一个区间 [l, r]，对区间内每个音符 ai，其音高变为 ai + (r - i + 1) * m。目标是使得操作后的序列中存在 aj > a(j+1)，即打破单调性。求所需的最短区间长度。如果无法做到，输出-1。(T 组数据)

解法思路：
关键在于分析操作对相邻音符差值的影响。要使 aj > a(j+1)，必须让 aj 相对 a(j+1) 增加的音高大于它们原来的差值。分析操作公式可知，在区间内，ai 相对 a(i+1) 会多增加 m；在区间末尾，ar 相对 a(r+1) 也会增加 m。因此，只要存在一个位置 i，使得原始音高差 a(i+1) - ai < m，我们就可以通过操作打破这里的单调性。并且，此时只需选择长度为1的区间 [i, i] 进行操作，只提升 ai 的音高，就足以保证新的 a'i > a(i+1)。因此，只需遍历一遍数组，检查是否存在相邻音符的差值小于 m。如果存在，最短区间长度就是1；如果不存在，则无论如何操作都无法打破单调性，答案是-1。

------------------------------------

题目三：

题目大意：
有一个 n x m (1 <= n, m <= 1e9) 的LED灯阵列，初始全为0。经过 k (1 <= k <= 2e5) 次操作，每次操作会翻转指定行或列的状态（0变1，1变0）。所有操作结束后，将整个阵列按行拼接成一个巨大的二进制数，求其对应的十进制值对 1e9 + 7 取模的结果。

解法思路：
由于翻转操作是异或操作，一个位置 (i, j) 的最终状态只取决于第 i 行和第 j 列被翻转次数的奇偶性。最终状态 `a[i][j] = (row_flip[i] % 2) ^ (col_flip[j] % 2)`。首先遍历 k 次操作，用两个集合记录被翻转了奇数次的行号和列号。设被翻奇数次的行集合为 R，列集合为 C。第 i 行的数值，如果 i 不在 R 中，则其值为 `Sum_{j in C} 2^(m-j)`；如果 i 在 R 中，则其值为 `(2^m - 1) - Sum_{j in C} 2^(m-j)`。最终结果是 `Sum_{i=1 to n} (value_of_row_i * (2^m)^(n-i))`。这个复杂的求和式可以通过提取公因式和等比数列求和公式进行化简，所有的大数幂运算都通过快速幂取模来高效计算。

具体的详细代码和题解可以戳我主页的文章查看#牛客AI配图神器#