5.14

• 120min, 20:00 - 22:00
• 25 单选 + 5 不定项选择 + 3算法
• 总分：100 = 50 + 20 + 30

单选

• 数据结构，算法（排序，二叉树，链表，时间复杂度，二叉树的度，递归），设计模式，数据库，函数默认参数，socket，Java接口，数值转换等

不定项选择

• 二叉树，C++指针，进程线程，数据库等

编程题

1. 输入数值，逆序输出
2. 给定一个长度为 n 的 01 串组成的环，默认为白色，现在要把某一段染成红色, 使得红色区域中 0 的个数等于得白色区域中 0 的个数，红色区域中 1 的个数等于得白色区域中 1 的个数，求有多少种染法（n 为偶数，n <= 300000）

滑动窗口：由题可知选出来的红色区域的长度为 n / 2, 分别计算 0 ，1串的前缀和，遍历每一个下标作为红色区域起点 start = i，则终点坐标为 end = i + n / 2 - 1, end < n 就直接求前缀和差值，否则为cnt = sum[start, n) + sum[0, end %n]

当 两种字符都满足 cnt = sum[n-1] 时，ans++

3. 给定一个数组，从数组中选出若干数使得他们的和为 k 的倍数，能取到满足条件的最大和是多少（n,k <= 1000）

提供思路：(通过 72%，没空调试了hhh)

dp：dp[i][j] 表示从前 i 个数中选出若干数的和 % k 的余数为 j 的最大和，则 dp[i][j] = max(dp[i - 1][j] , dp[i - 1][(j - a[i] % k + k) % k] + a[i]

总结

• 选择题占比很大，三道编程题只占30分，要更加注重选择题了
• 注意笔试题各部分时间安排