2021“MINIEYE杯”中国大学生算法设计超级联赛(3) 杭电多校3 题解
sdxjzsq
2021-08-03 15:38:11
## 目录
| 题号 | 题目 | 知识点 | 完成度 |
| ---- | ------------------------------------------------------------ | ------ | ------ |
| 1003 | HDU6975 [Forgiving Matching](https://acm.hdu.edu.cn/showproblem.php?pid=6975) | FFT | √ |
| 1009 | HDU6981 [Rise in Price](https://acm.hdu.edu.cn/showproblem.php?pid=6981) | 宽搜+剪枝 | √ |
| 1010 | HDU6982 [Road Discount](https://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1010&cid=986) | - | - |
| 1001 | HDU6973 [Bookshop](https://acm.hdu.edu.cn/showproblem.php?pid=6973) | - | - |
| 1012 | HDU6984 [Tree Planting](https://acm.hdu.edu.cn/showproblem.php?pid=6984) | - | - |
| 1002 | HDU6974 [Destinations](https://acm.hdu.edu.cn/showproblem.php?pid=6974) | - | - |
| 1006 | HDU6978 [New Equipments II](https://acm.hdu.edu.cn/showproblem.php?pid=6978) | - | - |
| 1005 | HDU6977 [Kart Race](https://acm.hdu.edu.cn/showproblem.php?pid=6977) | x | x |
| 1008 | HDU6980 [Restore Atlantis II](https://acm.hdu.edu.cn/showproblem.php?pid=6980) | x | x |
## 1003 HDU6975 [Forgiving Matching](https://acm.hdu.edu.cn/showproblem.php?pid=6975)
### 题意
已知两个字符串 $s$ 和 $t$，字符集为 $0\sim 9$ 和 $*$，其中 $*$ 可以匹配任意字符，现在要在容错的情况下在 $s$ 中匹配 $t$，问在容错字符数为 $0\cdots \left|t\right|$ 的情况下分别能够匹配到多少次。
### 思路
在多项式中，结果的第 $i$ 个系数是 $\sum_{j=0}^{i}a_j*b_{i-j}$ ，而 $t$ 去匹配 $s$ 的 $i\sim i+|t|-1$ 位能够匹配上的字符个数是 $\sum_{j=0}^{|t|-1}s_j==t_j$ ，可以发现，如果将 $t$ 逆置，则可以化为 $\sum_{j=0}^{|t|-1}s_j==t_{|t|-1-j}$ ，如果再将逆置后的 $t$ 后面补一些字符集外的字符，则可以变成 $\sum_{j=0}^{i}s_j==t_{i-j}$ ，发现除了比较符号外，和多项式乘法的结果完全一致！
那么如何将比较符号变成乘法呢？观察到题目中字符集只有 $0\sim 9$ 和 $*$ ，因此可以对于每种字符分开计算，每次将 $s$ 和 $t$ 中是该种字符的位置置为 $1$ ，其余位置置为 $0$ ，则对于特定字符来说，$s_j==t_{i-j}\iff s_j\times t_{i-j}$ 。
因此，我们可以对于字符集内每种字符做一遍多项式乘法，则第 $i+|t|-1$ 个系数的结果和便对应 $t$ 去匹配 $s[i,i+|t|-1]$ 能匹配上的字符个数，用 $|t|$ 减去这个个数便是需要容错的字母个数。
### code
```cpp
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int maxn = 2e5 + 7, maxm = 6e5;
int n, m, T, ans[maxn], num[maxn];
char s[maxn], t[maxn];
const double PI = acos(-1.0);
struct Complex
{
double x, y;
Complex(double _x = 0.0, double _y = 0.0) { x = _x, y = _y; }
Complex operator-(const Complex &b) const { return Complex(x - b.x, y - b.y); }
Complex operator+(const Complex &b) const { return Complex(x + b.x, y + b.y); }
Complex operator*(const Complex &b) const { return Complex(x * b.x - y * b.y, x * b.y + y * b.x); }
};
void change(Complex y[], int len)
{
int i, j, k;
for (int i = 1, j = len / 2; i < len - 1; i++)
{
if (i < j) swap(y[i], y[j]);
k = len / 2;
while (j >= k) j = j - k, k = k / 2;
if (j < k) j += k;
}
}
/*
* 做 FFT
* len 必须是 2^k 形式
* on == 1 时是 DFT，on == -1 时是 IDFT
*/
void fft(Complex y[], int len, int on)
{
change(y, len);
for (int h = 2; h <= len; h <<= 1)
{
Complex wn(cos(2 * PI / h), sin(on * 2 * PI / h));
for (int j = 0; j < len; j += h)
{
Complex w(1, 0);
for (int k = j; k < j + h / 2; k++)
{
Complex u = y[k];
Complex t = w * y[k + h / 2];
y[k] = u + t;
y[k + h / 2] = u - t;
w = w * wn;
}
}
}
if (on == -1)
for (int i = 0; i < len; i++) y[i].x /= len;
}
Complex x1[maxm], x2[maxm];
int main()
{
for (scanf("%d", &T); T--;)
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) num[i] = ans[i] = 0;
scanf("%s", &s);
scanf("%s", &t);
int len = 1;
while (len < n << 1) len <<= 1;
for (int j = 0; j < 11; ++j)
{
for (int i = 0; i < n; ++i) x1[i] = Complex((s[i] == ('0' + j)) || (s[i] == '*' && j == 10), 0);
for (int i = n; i < len; ++i) x1[i] = Complex(0, 0);
for (int i = 0; i < m; ++i) x2[m - i - 1] = Complex((t[i] == ('0' + j)) || (t[i] == '*') || j == 10, 0);
for (int i = m; i < len; ++i) x2[i] = Complex(0, 0);
fft(x1, len, 1);
fft(x2, len, 1);
for (int i = 0; i < len; ++i) x1[i] = x1[i] * x2[i];
fft(x1, len, -1);
for (int i = 0; i < n; ++i) num[i] += x1[i].x + 0.5;
}
for (int i = m - 1; i < n; ++i) ans[m - num[i]]++;
for (int i = 0; i <= m; ++i) printf("%d\n", ans[i] += i ? ans[i - 1] : 0);
}
return 0;
}
```
## 1009 HDU6981 [Rise in Price](https://acm.hdu.edu.cn/showproblem.php?pid=6981)
### 题意
已知 $n\times n$ 的格子，初始在 $(1,1)$ 处，只能向右或向下走，到达 $(n,n)$ ，每个格子里都有重量为 $a_{i,j}$ 的宝石，并且经过每个格子都可以让单位重量宝石的价格提升 $b_{i,j}$，求能得到的所有宝石的最大价格。
### 思路
因为只会经过 $2n-1$ 个格子，且 $n\le100$ ，数据量较小，因此考虑宽搜剪枝，如果对于位于 $i,j$ 的两个状态 $s_1,s_2$ ，满足 $\sum a_1 < \sum a_2,\sum b_1 < \sum b_2$，则可以将状态 $s_1$剪掉。
### code
```cpp
```