美团笔试0909

没有用dp，思路是a[i]与a[j]的出现次数是(i+1)*(n-j)，两个for循环也是15%

我用Hash Map辅助计算，超内存了。华✌，请教下，你第三题怎么A的？我用的贪心从1开始递增累加，但是没全通过测试用例

我C++也是15，O(n^2)，搞不懂啊搞不懂

第四题nlogn做法，算贡献就好了

按位算，对于每一位都记录0和1的前缀贡献和和以及后缀贡献和

分享一个NlogN思路，线性遍历，按二进制统计已遍历元素的信息，即每个二进制位上总共出现几次1几次0，算新的元素对结果的贡献就只需要遍历每个二进制位上的信息（按位计算符合分配律），时间是logN， 总共NlogN

没做这套，但是看舍友做了。。 考虑f(i)为结尾为i的答案，等于f(i-1) 1*a(i)^a(0) 2 * a(i)^a(1) ... (i-1) * a(i) ^ a(i-1)。 所以我们想要个异或的前缀和，前缀和一般是能预处理出来的，但是这里带一个系数，如果a(k) （k<i） 和 a(i)的某一位不相等，它会给k 1次贡献。所以你考虑前i-1个数每一个数在32位里的贡献，每个数k的贡献要乘以系数k 1。具体来说，设zeros[n][32] ones[n][32]为0，a[1]是3，那么ones[1][0] ones[1][1]分别加2，zeros[1][2-32]分别加2。a[i]的某位是0，就跟ones[i-1][那一位]去求，反之亦然。

我也是O(n^2)，TLE，按理说应该有O(n)解法，如果找到了求踢一脚

两两异或复杂度至少是O(N^2)，搞不懂这个题有什么不需要两两异或的解法

我最后一个dp也15%，大佬问下为啥第二题一直10%，我就是维护了一个sum总和，然后挨着判断右操作数比左操作数小的，取那个最大的最后双倍减去，自己怎么测都是对的，输出就是10%

大佬请问数组差异值思路

我也是先n^2复杂度，但只过了15%，憋了半小时写了个线性算法只过了75%...

第三题怎么过兄弟们

第四题一样过15 第三题有没有佬解答下 只过了16.67

团子这里大概要多少分才能进面呀

C随便写了个O(n²)的，果然TLE了，卡20%，不过两两异或是有什么快速解吗？依稀记得异或貌似有一个定理？记不太清

01的那道题只a了92是少考虑了啥

我也卡15 我记录了当前子串的前一个子串的值的 感觉没法继续优化了啊

有无大佬讲一下第三题是什么思路，我咋整都一个没过