腾讯0326后端笔试记录

一共5题，难度还是挺大的，作为一个打过acm的菜鸡，差点最后都没写完，ak的时候只剩下不到10分钟了。

第一题 送分题，反转链表操作，按题意模拟就行了。我是图方便，全部放进一个数组里，每k个反转完了之后再生成一下链表。

第二题 记不太清了，印象中也是个简单题，写了10分钟就写完了，一遍ac。

第三题 本质是让你构造一个数组c和给定数组b的偏序关系相同，然后和a进行对应位置做差的绝对值之和尽可能小，这题直接结构体sort一下之后贪心就行了。笔试完之后水群好像听说题面有点什么问题，不过我也没发现，应该是当时直接配合样例就看懂题意了吧，其实就是B和C数组的偏序要一致。

第四题 区间异或等于区间乘积，这题我写的特别麻烦，因为1这个东西很不好处理（不考虑1的话，那么最多32个数就超过int了），写了快1小时写吐了。

第五题 子序列gcd等于k的数量。这题放校招真的合适吗？感觉放区域赛都有铜牌以上难度了吧。稍微说一下思路吧，首先显然必须取k的倍数，不是k的倍数就直接被淘汰了。然后我们可以转化为，每个数除k以后，问有多少子序列gcd是1。这个是个比较经典的容斥问题，先处理gcd为2、3、5、7……的情况。然后发现2*3、2*5这种被算了2次，要减回来；然后2*3*5这种形式的被减多了，又要加回来……最后发现容斥的结果和莫比乌斯函数有关系。还好我以前打acm的时候做过类似的题目，这题没卡多久，不然可能最后时间都不够。

最后想吐槽一下，现在的校招也太难了吧，真的不给校招生一点活路么。。