CCF 201809

1.就是求平均值，第一个和最后一个特判一下。

2.这题两种思路：第一种，直接n*n的判断有没有交叉的区间，有就直接加上去。第二种直接模拟时间轴，时间轴最大只有1e6，那个区间如果有覆盖就直接+1，然后两个人的区间覆盖，如果两个人都有这个区间就是2，数组为2的个数加起来就行了。由于区间长度是S-T，其实这个相当于[s,t),有一个是开区间。

3.请见政大佬

4.记忆化DFS，开一个vis[400][400][400]的数组，vis[pos][i][j],pos表示位置，i，表示当前位置的值，j,表示前一个位置的值。然后就暴力枚举所有的值，如果那个值和前面一个的值已经访问过了就直接返回0。从小往大搜索，这样就可以保证字典序最小。

这题可以用第一题对拍一下哈哈

主要考点:

1.平均值，知道a[pos],b[pos-1],b[pos]可以推出b[pos+1]只有3种取值(满足(b[pos-1]+b[pos]+b[pos+1])/3==a[pos])；

2 记忆化搜索，因为每种状态后面都有3种取值所以暴力是，3^100复杂度，明显超时。所以要剪枝，就是前面说的vis数组。这样所有状态最多跑一次，总复杂度300^3,（实际上没有这么大）可以过。

5.你能开这一题，可以直接跳过我博客了。