总结

100 + 0 + 100 + 30 = 230分
对于昨天来说好多了，但是第二题忘去重了（本来去重了，但是对拍写错了，然后就把去重删掉了?）！第四题板子写错了！

T1

水题！将 \(a_i\) 加起来除以 \(m\) 即可。
时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

T2

数学题，但是我?，观察式子

\[a - c = c - b \]

化简可得

\[a + b = 2 \times c \]

题目还说：\(c\) 不一定属于这 \(n\) 个自然数
意思其实就是看有几组相加为偶数的数对，那我们就只用观察 \(a_i\) 的余数即可，（所以就是余数为一的 \(\times\) 余数为一的减一 \(+\) 余数为零的 \(\times\) 余数为零的减一）\(\div 2\)
时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

注意去重！！

T3

乍一看有点像滑动窗口（但我不会）?
于是我思考到了这道题有单调性，若长度为 \(m\) 的一段区间可以包含所有口味的蛋糕，那长度 \(\ge m\) 的也可以包含所有口味的蛋糕，所以我们理所当然的想到了二分，那二分里的 \(check\) 函数怎么用 \(O(n)\) 实现呢，我们可以用一个数组来记录每种口味的蛋糕在这个长度为 \(x\) 的区间里出现了几次，再用一个变量来记录在这个区间里总共有几种口味的蛋糕，\(check\) 函数的代码如下：

bool check(int x){
	for(int i = 1; i <= m; i++){
		cnt[i] = 0;
	} 
	int sum = 0;
	for(int i = 1; i <= x; i++){
		cnt[a[i]]++;
		if(cnt[a[i]] == 1){
			sum++;
		}
		if(sum == m){
			return true;
		}
	} 
	for(int l = 1, r = x + 1; r <= n; l++, r++){
		cnt[a[l]]--;
		if(cnt[a[l]] == 0){
			sum--;
		}		
		cnt[a[r]]++;
		if(cnt[a[r]] == 1){
			sum++; 
		} 
		if(sum == m){
			return true;
		}
	}
	return false;
}

时间复杂度：\(O(n\log n)\)
空间复杂度：\(O(n)\)