淘天3.15开发笔试前两题简单题解

只做出2题，第三题暴力拿了20%不会优化了

第一题：做了快 30 分钟，一开始就想着暴力求了，感觉写起来也挺恶心的，但是也想不到其他方法，有更好的可以评论。

假设原数组是 a，长度为 n

我是记录原数组每一个下标i 的在 [i, n] 区间上第一个 0 的位置 p0[i]，第一个 1 的位置p1[i]，第一个 2 的位置p2[i]，如果 a[i] 本身是 0，那么 p0[i] = i。可以从右往左扫一遍就可以求出这三个数组，边界情况设成 n+1

答案我是计算每一个 i 为左端点的子数组的 mex 值之和，分6种情况讨论（p0[i] < p1[i]<=p2[i], p0[i] < p2[i]<=p1[i] ......)，然后直接 O(1) 算出 mex 即可。

举个例子吧，假设 p0[i] < p1[i]<=p2[i]，说明 [p0[i], p1[i] - 1] 这段区间的 mex 是1，[p1[i], p2[i] - 1] 的 mex 是 2，[p2[i], n] 是 3

总复杂度是 O(n) 的，调了好一会，一开始一个都没过，随便写了个例子发现是自己分类讨论求 mex 写错了一点，过了 20%，发现可能超过 int，用 long long 存答案，过了

第二题：写两个 dfs 快速做完，耗时 15 分钟，没用并查集啥的，第一次dfs每个连通块（即相同部落且相邻的）统计周边的异族部落有多少个，记作 cnt ，第二次dfs填写连通块每个下标的答案为 cnt

第三题：不会，直接暴力求出每个 len 的答案，只有 20%