竞赛讨论区 > 【题解】"蔚来杯"2022牛客暑期多校训练营4
头像
王清楚
编辑于 2022-08-09 15:08
+ 关注

【题解】"蔚来杯"2022牛客暑期多校训练营4

C

设 为字符集大小。

因为是排列计数，所以考虑使用 而不是 。对于一种字符，我们列出它方案数对应的 如下:
那全部卷起来就是答案的生成函数：
接下来暴力展开式子，枚举后面那个多项式选了多少个
由于只关心 的大小，于是设 为前 个字符，选取 个字符的多项式相乘的答案。转移只需要考虑第 个选不选即可。这部分时间复杂度 。

现在式子变成了：
因为 的次数最高为 ，所以暴力展开 来卷。

但是如何快速求出 的第 项系数？第 项的系数就是长为 的序列，共有 种数可以放，最后能构成的序列的方案数。也就是 。然后要除以一个 表示为 形式。也就是：
乘 是为了抵消 中的 。这部分时间复杂度 。

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define pb push_back
using namespace std;
typedef long long LL;
const int N = 5e4+9;
const int M = 1e7+9;
const int p = 998244353;
int w, c[20], len, tot, n, q, r[N << 1];
LL a[N * 2], f[20][N * 2], ans;
LL fac[M], ifac[M];
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
int inv(int x, int base = p - 2) {
    int res = 1;
    while (base) {
        if (base & 1)
            res = 1ll * res * x % p;
        x = 1ll * x * x % p;
        base >>= 1;
    }
    return res;
}

void FFT(LL a[], int len, int op) {
    For(i, 0, len - 1) r[i] = r[i >> 1] >> 1 | ((i & 1) * (len >> 1));
    For(i, 0, len - 1) if (i < r[i])
        swap(a[i], a[r[i]]);
    for (int i = 1; i < len; i <<= 1) {
        LL wn = inv(3, (p - 1) / (i << 1));
        if (op == -1)
            wn = inv(wn, p - 2);
        for (int j = 0; j < len; j += i << 1) {
            LL w = 1, x, y;
            For(k, 0, i - 1) {
                x = a[j + k], y = a[i + j + k] * w % p, w = w * wn % p;
                a[j + k] = (x + y) % p, a[i + j + k] = (x - y + p) % p;
            }
        }
    }
    if (op == -1) {
        LL x = inv(len, p - 2);
        For(i, 0, len - 1) a[i] = a[i] * x % p;
    }
}

void work() {
    for (len = 1; len <= tot; len <<= 1);
    f[0][0] = 1;
    FFT(f[0], len, 1);
    For(i, 0, w - 1) {
        For(j, 0, len - 1) a[j] = 0;
        For(j, 0, c[i]) a[j] = (p - 1) * ifac[j] % p;
        FFT(a, len, 1);
        Rof(j, w, 1) For(k, 0, len - 1) f[j][k] = (f[j][k] + f[j - 1][k] * a[k]) % p;
    }
    For(i, 0, w) FFT(f[i], len, -1);
}

int main() {
    w = read();
    For(i, 0, w - 1) c[i] = read() - 1, tot += c[i];
    int m = 10000000;
    fac[0] = 1;
    For(i, 1, m) fac[i] = fac[i - 1] * i % p;
    ifac[m] = inv(fac[m], p - 2);
    Rof(i, m, 1) ifac[i - 1] = ifac[i] * i % p;
    work();
    q = read();
    while (q--) {
        n = read(), ans = 0;
        For(i, 0, w) {
            LL x = inv(w - i, n);
            LL invx = inv(w - i, p - 2);
            For(j, 0, min(n, tot)) {
                if (j == n)
                    x = 1;
                ans = (ans + x * f[i][j] % p * ifac[n - j]) % p, x = x * invx % p;
            }
        }
        printf("%lld\n", ans * fac[n] % p);
    }
    return 0;
}

E

考虑二维上的问题。如果对于一个点 存在一个点 满足 ，那么能满足 的一定能满足 ，所以 是无用的。把所有的无用点剔除，剩下的点呈阶梯状。只需要用二维前缀和即可算出贡献。

若需要动态加入点，则需要维护所谓的”有用点“数组，并让其有序（按第一关键字升序排序）。显对于所有的 一定满足 且 （不然一定有点会被剔除）。当新加入一个点 时，可以通过二分，找到 应该所在的位置，看是否能剔除其他点或被剔除。

于是我们把所有的点先按第三维升序排序，然后每一层动态加入点进行修改。并在三维差分数组上修改。由于每个点被加入一次，删除一次，所以总时间复杂度是 。最后做一次三维前缀和即可 查询答案。时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int M = 4e2 + 9;
const int p = 998244353;
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
set<pair<int, int>>s[N];
struct node {
    int y, z, id;
};
vector<node>e[M];
int dp[M][M][M], a[M][M];
void add(int x1, int y1, int x2, int y2) {
    a[x1][y1]++;
    a[x1][y2]--;
    a[x2][y1]--;
    a[x2][y2]++;
}
void insert(int i, int y, int z) {
    auto it = s[i].lower_bound({y, z});
    int last = y;
    auto now = it;
    int z1 = now == s[i].begin() ? M - 1 : (--now)->second;
    if (z1 <= z)
        return;
    while (1) {
        if (it == s[i].end())
            break;
        add(last, z, it->first, z1);
        if (it->second < z)
            break;
        now = it++;
        last = now->first;
        z1 = now->second;
        s[i].erase(now);
    }
    s[i].insert({y, z});
}
int n, m, q;
int main() {
    n = read(), q = read();
    for (int i = 1; i <= n; i++) {
        s[i].insert({401, 0});
        m = read();
        for (int j = 1; j <= m; j++) {
            int x = read(), y = read(), z = read();
            e[x].push_back({y, z, i});
        }
    }
    for (int i = 1; i <= 400; i++) {
        for (auto it : e[i])
            insert(it.id, it.y, it.z);
        for (int y = 1; y <= 400; y++)
            for (int z = 1; z <= 400; z++)
                dp[i][y][z] = dp[i][y - 1][z] + dp[i][y][z - 1] - dp[i][y - 1][z - 1] + a[y][z];
    }
    int seed;
    seed = read();
    mt19937 rng(seed);
    uniform_int_distribution<> u(1, 400);
    int lastans = 0;
    ll ans = 0;
    for (int i = 1; i <= q; i++) {
        int IQ = (u(rng)^lastans) % 400 + 1; // The IQ of the i-th friend
        int EQ = (u(rng)^lastans) % 400 + 1; // The EQ of the i-th friend
        int AQ = (u(rng)^lastans) % 400 + 1; // The AQ of the i-th friend
        lastans = dp[IQ][EQ][AQ];
        ans = (lastans + ans * seed % p) % p;
    }
    printf("%lld\n", ans);
    return 0;
}

G

发现答案之多与三条射线有关，所以暴力是 的。

接下来，对于射线条数以及形态进行分类讨论。（下文的其余情况均可通过旋转整个图形得到）：

  • 条，当且仅当不存在射线

  • 条，选取底部和顶部中最左/右的射线，并且左右两边不能有射线

  • 条

    • 平行，则只需要把底部和顶部的射线合并起来，选取相邻两条更新答案。
    • 垂直，则只可能在整个图形左上/左下（剩下的旋转图形即可计算），枚举哪一方射线先出来即可。

  • 条

    • +---------------+
|--------->|    |
|    ^     |    |
|    |     |    |
|    |     v    |
+---------------+

      一种是按照底边，侧边，顶边的顺序。枚举底边射线 ，然后在 到 右侧下一根射线这个区间内，在顶部找到最靠右的射线。然后侧边的射线要尽可能高。

    • +---------------+
|-------------> |
|    ^     ^    |
|    |     |    |
|    |     |    |
+---------------+

      另一种是侧边+两个底边。这个显然只需要选择底边相邻两个，然后侧边尽可能高。

具体细节注意一下就好了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 9;
const int lim = 2e9;
struct node {
    int x, y;
} a[N];
int n, m, k, U[N], b[N], D[N];
int ans;
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
void work() {
    int l1 = 0, l2 = 0, l3 = 0;
    int lmn = lim, L = -lim, rmn = lim, R = -lim, mx = -lim;
    for (int i = 1; i <= k; ++i) {
        if (a[i].y == 0)
            D[++l1] = a[i].x, b[++l2] = a[i].x;
        else if (a[i].x == 0)
            lmn = min(lmn, a[i].y), L = max(L, a[i].y);
        else if (a[i].y == m)
            U[++l3] = a[i].x, b[++l2] = a[i].x;
        else if (a[i].x == n)
            rmn = min(rmn, a[i].y), R = max(R, a[i].y);
    }
    if (!l1)
        return;
    sort(D + 1, D + 1 + l1);
    D[0] = 0;
    D[l1 + 1] = n;
    sort(b + 1, b + 1 + l2);
    mx = max(L, R);
    sort(U + 1, U + 1 + l3);
    U[0] = 0;
    U[l3 + 1] = n;
    ans = max(ans, L < 0 ? b[1] * m : lmn * D[1]);
    ans = max(ans, R < 0 ? (n - b[l2]) * m : (n - D[l1]) * rmn);
    for (int i = 2; i <= l2; ++i)
        ans = max(ans, m * (b[i] - b[i - 1]));
    if (mx >= 0)
        for (int i = 2; i <= l1; ++i)
            ans = max(ans, (D[i] - D[i - 1]) * mx);
    if (L >= 0) {
        for (int i = 1; i <= l1; ++i) {
            int r = U[lower_bound(U + 1, U + 1 + l3, D[i + 1]) - U - 1];
            if (r > D[i])
                ans = max(ans, (r - D[i]) * L);
            int l = U[lower_bound(U + 1, U + 1 + l3, D[i]) - U - 1];
            if (!l)
                ans = max(ans, (D[i] - l) * (m - L));
        }
    }
    if (R >= 0) {
        for (int i = 1; i <= l1; ++i) {
            int l = U[upper_bound(U + 1, U + 1 + l3, D[i - 1]) - U];
            if (l < D[i])
                ans = max(ans, (D[i] - l) * R);
            int r = U[upper_bound(U + 1, U + 1 + l3, D[i]) - U];
            if (r == n)
                ans = max(ans, (r - D[i]) * (m - R));
        }
    }
}
void rebuild() {
    for (int i = 1; i <= k; ++i) {
        if (a[i].y == 0)
            a[i].y = n - a[i].x, a[i].x = 0;
        else if (a[i].x == 0)
            a[i].x = a[i].y, a[i].y = n;
        else if (a[i].y == m)
            a[i].y = n - a[i].x, a[i].x = m;
        else if (a[i].x == n)
            a[i].x = a[i].y, a[i].y = 0;
    }
    swap(n, m);
}
signed main() {
    int T = read();
    while (T--) {
        k = read();
        n = read();
        m = read();
        ans = 0;
        for (int i = 1; i <= k; ++i)
            a[i] = {read(), read()};
        work();rebuild();
        work();rebuild();
        work();rebuild();
        work();
        printf("%lld\n", ans);
    }

    return 0;
}

I

设整张地图为 ，飞船为 （都是 维数组）。

由于 很小，若一种放置方式对于任意 都满足 中值为 的位置对应在 中的值大于等于 ，那么这个放置方式也是合法的。

具体的，将 中值为 的点设为 ，其余地方设为 。把 中值大于等于 的点设为 ，其余地方设为 。若一种放置方式，存在 对应位置都为 ,那么就不合法。

到此，可以用 的与操作优化，但显然是过不了的。

维的操作很麻烦，不妨化成一维上的数组：

。

同理， 也化成类似形式。为了与 匹配，多余的地方置为 。即：

现在就变成了 维的问题！

对于一种匹配，想快速得到 中是否不存在位置同为 ，即按位相乘的和是否不 。这启发我们想到 。只需要乘一次，即可得到所有的匹配结果。但是注意 不能放出 的位置（指在 维下），这个判断一下即可。设 ，时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
const int N = 6;
const int p = 998244353;
const int G = 3;
int k;
int n[N], sz;
vector<int> T, S;
int m[N];
int len1, len2;
int a[N];
vector <int> A, B, val;
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
int get(int *a) {
    int res = 0;

    for (int i = 1; i <= k; i++)
        res = res * n[i] + a[i];
    return res;
}
int check(int x) {
    for (int i = k; i; i--) {
        if (x % n[i] >= m[i])
            return 0;
        x /= n[i];
    }
    return k;
}
int check2(int x) {
    for (int i = k; i; i--) {
        if (x % n[i] > n[i] - m[i])
            return 0;
        x /= n[i];
    }
    return 1;
}
int len;
int inv(int x, int base = p - 2) {
    int res = 1;
    while (base) {
        if (base & 1)
            res = 1ll * res * x % p;
        x = 1ll * x * x % p;
        base >>= 1;
    }
    return res;
}
void FFT(vector<int> &A, int op = 0) {
    for (int i = 0; i < len; i++) {
        int r = 0;
        for (int j = i, k = len; k > 1; j >>= 1, k >>= 1)
            r = (r << 1) | (j & 1);
        if (i < r)
            swap(A[i], A[r]);
    }
    for (int i = 1; i < len; i <<= 1) {
        int wn = inv(G, (p - 1) / (i << 1));
        for (int j = 0; j < len; j += (i << 1)) {
            int w = 1;
            for (int k = 0; k < i; k++) {
                int x = A[j + k], y = 1ll * w * A[j + k + i] % p;
                A[j + k] = (x + y) % p;
                A[j + k + i] = (x + p - y) % p;
                w = 1ll * w * wn % p;
            }
        }
    }
    if (op == -1) {
        for (int i = 1; i < (len >> 1); i++)
            swap(A[i], A[len - i]);
        int INV = inv(len);
        for (int i = 0; i < len; i++)
            A[i] = 1ll * A[i] * INV % p;
    }
}
void mul(vector<int> &A, vector<int> &B) {
    len = 1;
    while (len < A.size() + B.size())
        len <<= 1;
    A.resize(len);
    B.resize(len);
    FFT(A);
    FFT(B);
    for (int i = 0; i < len; i++)
        A[i] = 1ll * A[i] * B[i] % p;
    FFT(A, -1);
}
int ans;
int main() {
    k = read();
    sz = 1;
    for (int i = 1; i <= k; i++) {
        n[i] = read();
        sz *= n[i];
    }
    T.resize(sz);
    S.resize(sz);
    for (int i = 0; i < sz; i++)
        T[i] = k;
    len1 = read();
    for (int i = 1; i <= len1; i++) {
        int v;
        for (int j = 1; j <= k; j++)
            a[j] = read();
        v = read();
        T[get(a)] = v;
    }
    for (int i = 1; i <= k; i++)
        m[i] = read();
    val.resize(sz);
    for (int i = 0; i < sz; i++) {
        S[i] = check(i);
        val[i] = check2(i);
    }
    len2 = read();
    for (int i = 1; i <= len2; i++) {
        int v;
        for (int j = 1; j <= k; j++)
            a[j] = read();
        v = read();
        S[get(a)] = v;
    }
    for (int i = 1; i <= k; i++) {
        A.resize(sz);
        B.resize(sz);
        for (int j = 0; j < sz; j++) {
            A[j] = T[j] < i;
            B[sz - j - 1] = S[j] == i;
        }
        mul(A, B);
        for (int j = 0; j < sz; j++)
            val[j] &= (A[j + sz - 1] == 0);
    }
    for (int i = 0; i < sz; i++)
        ans += val[i];
    printf("%d\n", ans);
    return 0;
}

M

对于两个点 ，若钦定 在直线上的投影在 的左边，那么会有一个 ° 的区间范围限制。对于所有的相邻两点都计算出这个限制，取交就是直线方向。而直线具体位置是没有关系的。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9;
int n;
struct node {
    int x, y;
    int operator*(node &X)const {
        return x * X.y - y * X.x;
    }
};
node a[N], l, r, L, R;
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y;
    L.x = L.y = 1;
    for (int i = 2; i <= n; i++) {
        node b;
        b.x = a[i].x - a[i - 1].x;
        b.y = a[i].y - a[i - 1].y;
        if (b.x == 0 && b.y == 0)
            continue;
        r.y = -b.x;
        l.x = -b.y;
        l.y = b.x;
        r.x = b.y;
        if (i == 2) {
            L = l, R = r;
            continue;
        }
        if ((l * R) > 0 && (r * L) < 0) {
            puts("NO");
            return 0;
        }
        if ((l * L) > 0)
            L = l;
        if ((r * R) < 0)
            R = r;
    }
    puts("YES");
    cout << "0 0 ";
    cout << L.x << " " << L.y;
}
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
2021届阅文Android方向笔试卷
【2020】自如秋招产品经理-B卷
【2021】腾讯秋招技术岗编程合集
全部 >
面经
面试常考问题整理
Springboot全套注解解析《看不懂算我输》
0926腾讯音乐笔试题解
23届联想面经分享： 秋招上岸
全部 >
内推
员工内推码获取
体验中心实习生招募 - 淘天集团
【美团】校招社招内推，所有岗位，进度可查，消息必回
拼多多内推实习&校招
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(0) 回帖
加载中...
话题 回帖
返回全部帖子

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”