10.2 xm模拟赛题解
__S08577__
·
·
个人记录
T1
赛时A了。
用折半搜索，如果整个序列用一个搜索，那么复杂度将会为 O(2^n)，显然会T飞，那么不妨考虑折半搜索，先搜索前半段，再搜索后半段，复杂度为 O（2\times 2^{\frac{n}{2}}），可以AC。
我们将前半段和后半段搜索的结果分别放入 sum1 和 sum2 中，双指针求最大值即可。
注意，这里两个数组的长度在 1e5 左右，O(n^2) 过不了，需要稍微剪剪枝。（本人自己测之前写的 n^2，当 n=35 时，T飞了）
T2
20pts
我们发现对于 \forall i,j,s_i\neq s_j，不难发现个数即为 C_n^4。
40pts
### 100pts
DP
设 $f_{i,j}$ 为在前 $i$ 个选 $j$ 个的方案数，$lst_i$ 为 $i$ 上一次出现的位置，不难推出状态转移方程：
$$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}$$
$$f_{i,j}=f_{i,j}-f_{lst_{s_i}-1,j-1}[lst_{s_i} \neq 0] $$
（第一句的意思是杨辉三角，即组合数）
（$f_{lst_{s_i}-1,j-1}$ 是减去重复的。很好理解，$lst_{s_i}-1$ 为该字母上一次出现的位置）
初始化：
$$f_{i,0}=1$$
在前 $i$ 个里面啥都不选，显然只有一种方式。
最后输出 $f_{n,4}$ 即可。
### key code
```cpp
for(int i=0;i<=n;i++) f[i][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=4;j++){
f[i][j]=f[i-1][j]+f[i-1][j-1];
if(lst[s[i]]) f[i][j]-=f[lst[s[i]]-1][j-1];
}
lst[s[i]]=i;
}
cout<<f[n][4];
```
鸣谢 @Dtw
## T3
### 20-60pts
dfs暴力即可
看剪枝剪了多少。
### 100pts
分类讨论。
这道题已知小W杀了不超过3只，这是很方便进行分讨的。
题目已知小Z不超过小W，可以分讨各杀了几只。
$3-1,3-2,3-3,2-1,2-2
以小W杀了3只为例，暴力枚举杀了3只的所有情况，判断有无路径，并记录怪兽的最大值最小值以及价值和。
将所有路径按照最小值降序和最大值降序两种方式排列，分别给小W和小Z，用双指针类似T1的方式合并即可。
最后将所有讨论所得的最大值记录一下输出即可。
复杂度为 O(n^6 \log n)。
T4
30pts
暴力贪心，对于每次询问的 l 和 r，我们选一条能覆盖到 l ， 且右端点最大的线段（不需要考虑左端点，对于左端点只需覆盖到 l 即可。），重复操作，知道覆盖到 r ，操作的次数即为所求答案。