1003

公式有点烂，$mathjax$​​ 渲染出来的和 我本地的 typora​ 出来不一样，不想修了啊 。T_T

似乎修好了， \ast 写成 * 的问题。

字符集为 $|S|= \lbrace 0,1…9,\ast \rbrace$​​​​​​​​​ ，其中 $\ast$​​ 为通配符，求两个串 $s_1$​​，$s_2$​​ 长分别为 $n$​​ ，$m$​​($n\geq m$​​) 的字符串匹配情况，具体来说是第一个串的一个长度为 $m$​​ 的子串和第二串的整串去匹配，容许有 $k$​​ 个字符不一样，对所有 $k \in [0,m]$​​​​​​​​ 输出能匹配的方案个数。

卷积求带通配符的串匹配情况，还好比赛里做出来了。

题目主要特点是字符集小，且允许 $k$​​ 个地方不一样，那我们必须得到每个位置结尾前缀的子串有几个字符一样或者不一样，这样就对所有 $k$​ 输出答案了。

无法通过构造函数来推出这一点，因为字符的差值固定，不太好做。

于是只能枚举字符来做。

$Solution_1$：

考虑一种字符 $c$​​

对第一个串构造 $A[i]=(s1[i]==c)$​​

对第二个串构造 $B[i]=(s2[i]==c \lor s2[i]==*)$​​​

此处 $s2$​ 当然已经按照套路翻转过了。

这样就得到了 $s_1$​ 所有位置这个字符和 $s_2$ 匹配情况，这样做字符集次，最后只需要加上 $s_1$ 每个位置前缀长 $m$ 的 $*$​​​​​ 即可，不难发现这样能得出所有结尾位置匹配上的情况了。$O(10nlog_2n)$​

$Solution_2$​：

题解的做法，枚举完字符，第二串中的通配符也不管，这样每个位置最后答案需要额外

$+$​ (第二串中 $\ast$​ ) $+$​ (第一串中一段的 $\ast$ )$-$​ (共用也就是匹配上的 $\ast$​ )

不难发现这样也是正确的，简单容斥了一下，多算的去掉。

$O(11nlog_2n)$​

md，比赛里想了好久才想到一种正确的做法，脑子好慢啊

1004

给定 $n$​​​ 条直线， $Alice$​​​ 选 $k$​​​ 条出来， $Bob$​​ 会画一条直线，前者想让后者画的直线于她选的交点尽可能多，后者想让尽可能少，对所有 $k \in [1,n]$​​ 输出交点数。

分析：

首先， $n$ 条不平行直线，Bob 只能得到 $n-1$ 的答案，只能画一条和某一条直线平行的线来做到。

这样，我们可以推得一点就是若存在共线的直线， $Bob$​​​​ 一定是画一条与最多平行直线平行的一条。

而反过来 $Alice$ 一定想让最大平行数尽可能少，于是缓慢递增，统计一个每种次数出现的后缀和就能做到。

1009

$n*n$​​ 网格图，从 $(1,1)$​ 走到 $(n,n)$​，只能走右或下，经过某点能获得 $a_{i,j}$​的钻石，并使得钻石价值提升 $b_{i,j}$​​​ ，到终点最后会统一售卖出去，求能获得的最大价值，保证数据随机。 $(n \leq 100)$

数据随机又是乱搞题，但还是必须基于一定策略。

设 $f[i][j][k]$ 表示达到 $(i,j)$ 且身上有 $k$ 个钻石能获得的最大单价。

到达一个点，对于已经有 $a$​​​​， $b$​​​​ 个钻石的状态，若 $(a<b) \land f[i][j][a]<=f[i][j][b]$​​ ，那么前者不可能成为答案，比你多且比你有钱怎么能成为答案呢。

故只需维护一个对钻石数量的单价下降序列即可，类似单调栈。

数据随机是保证在 $n=100$​ ，这样的状态数峰值在 千级别。

复杂度 $O(n^2*state)$​

1010

$n$ 个点 $m$ 条边的无向图，每条边有两种费用 $d_i$， $c_i$，$d_i\leq c_i$，求恰好使用 $k$​ 次便宜边的最小生成树。$(n\leq1000,m\leq200000,1\leq d_i \leq c_i \leq 1000)$

题面如果这么被读出来了，就是恰好使用 $k$ 条白边的最小生成树，是个显然的 $wqs$ 二分问题。

直接做边数依然过大，那显然最后使用的边只会是在原来纯用黑边或白边的最小生成树中。这样边数也是 $O(n)$ 级别了。

由于值域很小，且要对所有 $k$ 输出答案，故可以不二分，对所有 $-1000$ 到 $1000$ 的附加权参数预处理出最终 $MST$ 权值 和 用的白边的次数。

询问直接找即可。

复杂度 $O(mlog_2m+nc)$​​​ 。

当然直接对每个 $k$ 二分做应该也是可以的。