Kalorona

HNOI 2018 省队集训 Day 8 – 解题报告

A – 杀毒软件

这套题里面质量最好的题（虽然跟 BZOJ 的某题比较像）。

我们先考虑把所有的病毒串加到 AC 自动机里去，然后再考虑一个 DP 转移，设 \( dp[i][j] \) 为当前第 \(i\) 个字符匹配于自动机节点 \(j\) 上的方案数。发现数据范围很小，所以其实这个可以矩阵优化。建完 AC 自动机之后，我们针对 \(a_i = 0, 1, -1\) 算三个矩阵。算完这个之后用线段树来维护就可以了。（复杂度上天了）

实测矩阵乘法的时候剪枝可以快 10s 的样子。

// GuOJ1126.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200, MAX_S = 18, mod = 998244353;

int n, m, q, s, seq[MAX_N], idx[MAX_S], rk[MAX_S], ptot;
int ch[MAX_N][2], fail[MAX_N];
bool tag[MAX_N];
char str[MAX_N];

struct matrix
{
    int mat[MAX_S][MAX_S];

    int *operator[](const int &rhs) { return mat[rhs]; }
    void clear() { memset(mat, 0, sizeof(mat)); }
    matrix operator*(const matrix &rhs)
    {
        matrix ret;
        ret.clear();
        for (int i = 0; i <= s; i++)
            for (int k = 0; k <= s; k++)
                if (mat[i][k])
                    for (int j = 0; j <= s; j++)
                        if (rhs.mat[k][j])
                            ret[i][j] = (0LL + ret[i][j] + 1LL * mat[i][k] * rhs.mat[k][j] % mod) % mod;
        return ret;
    }
} nodes[MAX_N << 2], t1, t0, tr;

#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

void build(int l, int r, int p)
{
    if (l == r)
    {
        if (seq[l] == -1)
            nodes[p] = tr;
        else if (seq[l] == 0)
            nodes[p] = t0;
        else
            nodes[p] = t1;
        return;
    }
    build(l, mid, lson), build(mid + 1, r, rson);
    nodes[p] = nodes[lson] * nodes[rson];
}

void update(int qx, int l, int r, int p, int val)
{
    if (l == r)
    {
        if (val == 0)
            nodes[p] = t0;
        else if (val == 1)
            nodes[p] = t1;
        else
            nodes[p] = tr;
        return;
    }
    if (qx <= mid)
        update(qx, l, mid, lson, val);
    else
        update(qx, mid + 1, r, rson, val);
    nodes[p] = nodes[lson] * nodes[rson];
}

matrix query(int ql, int qr, int l, int r, int p)
{
    if (ql <= l && r <= qr)
        return nodes[p];
    bool tag1 = ql <= mid, tag2 = mid < qr;
    if (tag1 && tag2)
        return query(ql, qr, l, mid, lson) * query(ql, qr, mid + 1, r, rson);
    if (tag1)
        return query(ql, qr, l, mid, lson);
    else
        return query(ql, qr, mid + 1, r, rson);
}

void insert()
{
    int len = strlen(str + 1), p = 0;
    for (int i = 1; i <= len; i++)
    {
        if (ch[p][str[i] - '0'] == 0)
            ch[p][str[i] - '0'] = ++ptot;
        p = ch[p][str[i] - '0'];
    }
    tag[p] = true;
}

void build()
{
    queue<int> q;
    for (int i = 0; i < 2; i++)
        if (ch[0][i])
            q.push(ch[0][i]);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 2; i++)
            if (ch[u][i] == 0)
                ch[u][i] = ch[fail[u]][i];
            else
            {
                fail[ch[u][i]] = ch[fail[u]][i];
                tag[ch[u][i]] |= tag[fail[ch[u][i]]];
                q.push(ch[u][i]);
            }
    }
}

int main()
{
    // ptot = 2, ch[0][0] = 1, ch[0][1] = 2;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &seq[i]);
    for (int i = 1; i <= m; i++)
        scanf("%s", str + 1), insert();
    build();
    for (int i = 0; i <= ptot; i++)
        if (!tag[i])
            idx[++s] = i, rk[i] = s;
    for (int i = 0; i <= s; i++)
    {
        int id = idx[i], lc = rk[ch[id][0]], rc = rk[ch[id][1]];
        if (tag[id])
            continue;
        if (!tag[ch[id][0]])
            tr[i][lc]++, t0[i][lc]++;
        if (!tag[ch[id][1]])
            tr[i][rc]++, t1[i][rc]++;
    }
    build(1, n, 1);
    while (q--)
    {
        int x, y;
        scanf("%s%d%d", str + 1, &x, &y);
        if (str[1] == 'Q')
        {
            matrix src = query(x, y, 1, n, 1);
            int ans = 0;
            for (int i = 0; i <= s; i++)
                ans = (0LL + ans + src[0][i]) % mod;
            printf("%d\n", ans);
        }
        else
        {
            update(x, 1, n, 1, y);
            seq[x] = y;
        }
    }
    return 0;
}

B – 政治正确

什么狗屎题？

// GuOJ1127.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, md;
double v[MAX_N];

struct vec
{
    double d[10];
    void clear() { memset(d, 0, sizeof(d)); }
    double &operator[](const int &rhs) { return d[rhs]; }
    vec operator+(const vec &rhs)
    {
        vec ret;
        ret.clear();
        for (int i = 0; i < md; i++)
            ret[i] = d[i] + rhs.d[i];
        return ret;
    }
    vec operator-(const vec &rhs)
    {
        vec ret;
        ret.clear();
        for (int i = 0; i < md; i++)
            ret[i] = d[i] - rhs.d[i];
        return ret;
    }
    vec operator*(const double &rhs)
    {
        vec ret;
        ret.clear();
        for (int i = 0; i < md; i++)
            ret[i] = d[i] * rhs;
        return ret;
    }
    vec operator/(const double &rhs)
    {
        vec ret;
        ret.clear();
        for (int i = 0; i < md; i++)
            ret[i] = d[i] / rhs;
        return ret;
    }
    vec operator-(void)
    {
        vec ret;
        ret.clear();
        for (int i = 0; i < md; i++)
            ret[i] = -d[i];
        return ret;
    }
    double len2()
    {
        double ret = 0;
        for (int i = 0; i < md; i++)
            ret += d[i] * d[i];
        return ret;
    }
    vec normalize()
    {
        double t = sqrt(len2());
        return (*this) / t;
    }
    void scan()
    {
        for (int i = 0; i < md; i++)
            scanf("%lf", &d[i]);
    }
    void print()
    {
        for (int i = 0; i < md; i++)
            printf("%lf", d[i]);
    }
} pts[MAX_N];

vec under(vec &rhs) { return -rhs * (1 / (1 - rhs.len2())); }

vec centralize(vec &rhs)
{
    vec ret;
    ret.clear();
    for (int i = 1; i <= n; i++)
    {
        double len2 = (pts[i] - rhs).len2();
        if (len2 != 0)
            ret = ret + (rhs - pts[i]) * (v[i] / len2);
    }
    return ret;
}

int main()
{
    scanf("%d%d", &n, &md);
    for (int i = 1; i <= n; i++)
        pts[i].scan();
    double step = 0.5, rot = 0.8;
    vec ret;
    ret.clear();
    for (int rd = 1; rd <= 50; rd++)
    {
        vec c = under(ret) + centralize(ret);
        vec roted = c.normalize() * step;
        if ((ret + roted).len2() < 1)
            ret = ret + roted;
        step *= rot;
    }
    ret.print();
    return 0;
}

C – 水果拼盘

傻逼题，直接算每个水果的轮数，然后用组合数分开来计数即可。

// GuOJ1128.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100010, mod = 998244353;

int n, m, k, rdcnt[MAX_N], fac[MAX_N], fac_inv[MAX_N], ai[MAX_N], bi[MAX_N];

int fpow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

int binomial(int n_, int k_) { return n_ >= k_ ? 1LL * fac[n_] * fac_inv[k_] % mod * fac_inv[n_ - k_] % mod : 0; }

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++)
        scanf("%d", &ai[i]);
    for (int i = 1; i <= m; i++)
        scanf("%d", &bi[i]);
    for (int i = fac[0] = 1; i <= n; i++)
        fac[i] = 1LL * fac[i - 1] * i % mod;
    fac_inv[0] = fac_inv[1] = 1;
    for (int i = 2; i <= n; i++)
        fac_inv[i] = 1LL * (mod - mod / i) * fac_inv[mod % i] % mod;
    for (int i = 2; i <= n; i++)
        fac_inv[i] = 1LL * fac_inv[i - 1] * fac_inv[i] % mod;
    for (int i = 1, ktot, val; i <= n; i++)
    {
        scanf("%d", &ktot);
        while (ktot--)
            scanf("%d", &val), rdcnt[val]++;
    }
    int ans = 0, inv = fpow(binomial(n, k), mod - 2);
    for (int i = 1; i <= m; i++)
    {
        int prob = 1LL * binomial(n - rdcnt[i], k) * inv % mod;
        ans = (0LL + ans + 1LL * prob * bi[i] % mod + 1LL * (1 + mod - prob) % mod * ai[i] % mod) % mod;
    }
    printf("%d\n", ans);
    return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *