本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-02 16:53:32

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

$n^4$ 暴力即可。

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

    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$ ，操作的次数即为所求答案。