2021“MINIEYE杯”中国大学生算法设计超级联赛(3) 杭电多校3 题解

2021-08-03 15:38:11


目录

题号 题目 知识点 完成度
1003 HDU6975 Forgiving Matching FFT
1009 HDU6981 Rise in Price 宽搜+剪枝
1010 HDU6982 Road Discount - -
1001 HDU6973 Bookshop - -
1012 HDU6984 Tree Planting - -
1002 HDU6974 Destinations - -
1006 HDU6978 New Equipments II - -
1005 HDU6977 Kart Race x x
1008 HDU6980 Restore Atlantis II x x

1003 HDU6975 Forgiving Matching

题意

已知两个字符串 $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

#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

题意

已知 $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