0offer 老师，逼着做项目和毕设，女朋友生病去了医院几天

候选人来现场面试，表现的非常客气，我跟他讲没有必要这样，我们在面试你的同时，其实也是你对我们的一次面试。

三道题1. 给一个4X4的矩阵，矩阵有W和R两种元素，允许上下左右移动，问有多少种只经过R的最长的路径太小了可以直接O(16!)搜索2. 给一个长10^5的数组a，q次询问[l,r]区间内有多少位置满足 a_i>a_{i-1}, a_i>a_{i+1}预处理前缀和，考虑一下边边上 O(n)3. 问[l,r]区间内有多少数字满足其中1和2的出现次数不同，r在10^100数量级应该有不少做法。转化为前缀差，即求[0,r]与[0,l]中满足要求数字的差。从大到小枚举每一位是什么，每次枚举时只枚举当前位，前面的位复制过来。举个例子：123 -> 0xx,10x,11x, 120, 121, 122单独处理123枚举过后转化为O(logn)个有前缀但是对x部分只有位数限制的子问题，每个子问题中直接枚举1和2的个数，组合数算出所有可能的放法。每个子问题复杂度最多为O(logn^2)。实际复杂度大概在(logn^3)这个级别，但是常数巨大看上去马上就T。

学校大部分举办的都是互联网+，挑战杯这类的ppt比赛，然后又是嫡系大战，一群拿了奖的人比赛，根本竞争不过，也混不进去队伍。😥😥😥别人有项目也不拉进😢

vector扩容有2倍，有1.5，面试咋说