竞赛讨论区 > 【题解】2021牛客暑期多校训练营3
头像
王清楚
发布于 2022-07-21 15:29
+ 关注

【题解】2021牛客暑期多校训练营3

A

如果 问是不是大于 ， 回答是，就把 的数覆盖一遍，否则把 的数覆盖一遍，否则把 的覆盖一遍。

如果一个数被覆盖大于一次，就不可能是他

赢当且仅当只有一个数覆盖次数小于等于

发现大于 的可以舍去，有效状态只有一段 ，一段 ，再一段 .

设 表示依次有 个 ， 个 ， 个 。决策单调性可以优化到 。

发现答案是 级别，而且关于第三维单调。就可以把第三维和答案交换，优化到 。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 9;
int n, dp[24][N][N];
int main() {
    cin >> n;
    memset(dp, 0xc0, sizeof(dp));
    dp[0][0][0] = 1;
    dp[0][0][1] = dp[0][1][0] = 0;

    for (int r = 1; r <= 18; ++r) {
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; i + j <= n; ++j) {
                int L = min(i, (1 << (r - 1)) - j);
                dp[r][i][j] = max(dp[r][i][j], dp[r - 1][i - L][j]);
                dp[r][i][j] = max(dp[r][i][j], (1 << (r - 1)) - j + dp[r - 1][i][j]);
            }
        }

        for (int j = 0; j <= n; ++j) {
            int la = j;

            for (int i = 0; i + j <= n; ++i) {
                bool flag = false;

                for (int l = la; l >= 0; --l) {
                    if (dp[r - 1][i][l] >= j - l) {
                        flag = true;
                        dp[r][i][j] = max(dp[r][i][j], dp[r - 1][l][j - l]);
                        la = l;
                        break;
                    }
                }

                if (!flag)
                    break;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        int now = 0;

        while (dp[now][i - 1][n - i + 1] < 0)
            ++now;

        printf("%d ", now);
    }

    return 0;
}

B

考虑如何刻画涂黑第三个点可以免费第四个点这个条件。

仔细思考一下，发现等价于选择一个点 就表示加入了第 行和第 列。对于任意一个矩形，他所涉及的行 ,和列 ，只需要其中任意三条边，例如： ，就能表示这四个点。把所有情况枚举出来，发现这四个点联通是充要条件。

那么用点来表示行和列，涂黑一个点 即选择一条边 。需要求如何花费最小的代价使图联通，可知用最小生成树算法。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 9;
vector<int>had[100005];
int fa[N * 2];
int n, m, a, a1, b, c, d, p, s;
int get(int x) {
    return x == fa[x] ? x : fa[x] = get(fa[x]);
}
int main() {
    scanf("%d%d%d%d%d%d%d", &n, &m, &a, &b, &c, &d, &p);
    s = n * m;
    a1 = (1ll * a * a * b + 1ll * a * c + d) % p;

    for (int i = 0; i < s; i++) {
        had[a1].push_back(i);
        a1 = (1ll * a1 * a1 * b + 1ll * a1 * c + d) % p;
    }

    for (int i = 0; i < n + m; i++)
        fa[i] = i;

    long long ans = 0;

    for (int i = 0; i < p; i++) {
        for (auto z : had[i]) {
            int x = z / m, y = z % m;

            if (get(x) != get(n + y)) {
                ans += i;
                fa[get(n + y)] = get(x);
            }
        }
    }

    printf("%lld", ans);
    return 0;
}

C

从大到小枚举填入数的大小 ，找出 的行和列。

对于这些选出的行列的交点，填一个 可以满足两个条件。对于其他的，填一个 只能满足一次条件。发现这是一个最大匹配的问题，用匈牙利算法即可解决。假设对于数 ，有 个满足条件的行列，最大匹配数为 ，那么代价就是 。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3 + 9;
int n, m, k, u, v, b[N], c[N], fa[N], ans = 0;
vector<int> e[N];
bool used[N];
bool dfs(int u) {
    for (int i = 0; i < e[u].size(); ++i) {
        int v = e[u][i];

        if (used[v])
            continue;

        used[v] = true;

        if (!fa[v] || dfs(fa[v])) {
            fa[v] = u;
            return true;
        }
    }

    return false;
}
signed main() {
    scanf("%lld%lld%lld", &n, &m, &k);

    for (int i = 1; i <= n; ++i)
        scanf("%lld", &b[i]), ans += b[i];

    for (int i = 1; i <= n; ++i)
        scanf("%lld", &c[i]), ans += c[i];

    while (m--) {
        scanf("%lld%lld", &u, &v);

        if (b[u] == c[v])
            e[u].push_back(v);
    }

    for (int i = 1; i <= n; ++i) {
        memset(used, 0, sizeof used);
        ans -= dfs(i) * b[i];
    }

    printf("%lld", ans);
    return 0;
}

D

因为 ，所以考虑容斥 个格子是否必选。然后看行列对角线是否不能选。然后统计剩余各自的答案。

假设最后留下了 行 列，那么可选的格子就是 。但是对角线的限制比较麻烦。可知如果第 行第 列可以选，但是主对角线不能选，那么可选格子数要 。 同理。可以设三维 背包，每次看是否选择 行，列。然后根据对角线的状态来背包。

时间复杂度 

#include <bits/stdc++.h>
using namespace std;
const int N = 35;
const int P = 1e4 + 7;
int C[N * N][N * N];
int n, K, m;
int cnt[1 << 7];
int x[7], y[7];
int vx[N], vy[N];
int f[N][N][N * 2], g[N][N][N * 2];
int solve(int f0, int f1, int ban) {
    f[0][0][0] = 1;
    int S = 0;
    for (int l = 1, r = n; l <= r; l++, r--) {
        memset(g, 0, sizeof(g));
        for (int i = 0; i <= S; i++)
            for (int j = 0; j <= S; j++)
                for (int k = 0; k <= 2 * S; k++) {
                    if (!f[i][j][k])
                        continue;
                    if (l != r) {
                        for (int s1 = vx[l]; s1 <= 1; s1++)
                            for (int s2 = vy[l]; s2 <= 1; s2++)
                                for (int s3 = vx[r]; s3 <= 1; s3++)
                                    for (int s4 = vy[r]; s4 <= 1; s4++) {
                                        int ti = i + s1 + s3, tj = j + s2 + s4, tk = k;
                                        if (s1 && s2 && f0)
                                            tk++;
                                        if (s3 && s4 && f0)
                                            tk++;
                                        if (s1 && s4 && f1)
                                            tk++;
                                        if (s2 && s3 && f1)
                                            tk++;
                                        g[ti][tj][tk] = (g[ti][tj][tk] + f[i][j][k]) % P;
                                    }
                    } else {
                        for (int s1 = vx[l]; s1 <= 1; s1++)
                            for (int s2 = vy[l]; s2 <= 1; s2++) {
                                int ti = i + s1, tj = j + s2, tk = k;
                                if (s1 && s2 && f0)
                                    tk++;
                                else if (s1 && s2 && f1)
                                    tk++;
                                g[ti][tj][tk] = (g[ti][tj][tk] + f[i][j][k]) % P;
                            }
                    }
                }
        if (l != r)
            S += 2;
        else
            S++;
        for (int i = 0; i <= S; i++)
            for (int j = 0; j <= S; j++)
                for (int k = 0; k <= 2 * S; k++)
                    f[i][j][k] = g[i][j][k];
    }
    int res = 0;
    for (int i = 0; i <= S; i++)
        for (int j = 0; j <= S; j++)
            for (int k = 0; k <= 2 * S; k++) {
                if (!f[i][j][k])
                    continue;
                if ((i + j) % 2 == 0)
                    res = (res + 1ll * f[i][j][k] * C[i * j - k - ban][m]) % P;
                else
                    res = (res - 1ll * f[i][j][k] * C[i * j - k - ban][m] % P + P) % P;
            }
    return res;
}
int F(int S) {
    memset(vx, 0, sizeof(vx));
    memset(vy, 0, sizeof(vy));
    int f0 = 0, f1 = 0;
    for (int i = 0; i < K; i++)
        if (S & (1 << i)) {
            vx[x[i]] = 1;
            vy[y[i]] = 1;
            if (x[i] == y[i])
                f0 = 1;
            if (x[i] + y[i] == n + 1)
                f1 = 1;
        }
    int res = 0;
    res = (res + solve(0, 0, cnt[S])) % P;
    if (!f0)
        res = (res - solve(1, 0, cnt[S]) + P) % P;
    if (!f1)
        res = (res - solve(0, 1, cnt[S]) + P) % P;
    if (!f0 && !f1)
        res = (res + solve(1, 1, cnt[S])) % P;
    return res;
}

int main() {
    for (int i = 0; i < N * N; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
    }
    cin >> n >> K >> m;
    for (int i = 0; i < K; i++)
        cin >> x[i] >> y[i];
    for (int i = 0; i < (1 << K); i++)
        cnt[i] = cnt[i >> 1] + (i & 1);
    int ans = 0;
    for (int i = 0; i < (1 << K); i++) {
        m -= cnt[i];
        if (cnt[i] & 1)
            ans = (ans - F(i) + P) % P;
        else
            ans = (ans + F(i)) % P;
        m += cnt[i];
    }
    cout << ans << endl;
    return 0;
}

E

不得不说，对于这种题优先考虑打表是一个不错的选择。打表发现对于任意正整数 都满足。

设 整理得 。枚举 ，由韦达定理知

固定 ，计算上面答案对数。

若 满足条件， 也满足条件。因为 顺序不影响，所以 也合法。

发现这很符合打表找到的规律。每次得到 就可以得到 。利用打表得到的特例 递推下去，存在数组里排序二分求解。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int lim = 1e18;
int T, n, a[5000010];
signed main() {
    a[n++] = 1;

    for (int i = 2; i * i * i <= lim; i++) {
        int x = i, y = i * i * i;
        a[n++] = y;

        while (y <= (lim + x) / i / i) {
            x = i * i * y - x;
            swap(x, y);
            a[n++] = y;
        }
    }

    sort(a, a + n);
    scanf("%d", &T);

    while (T--) {
        int k;
        scanf("%lld", &k);
        printf("%lld\n", upper_bound(a, a + n, k) - a);
    }
}

F

直接暴力枚举 即可。但是要保证得到数的方式一定涉及分数，即不整除。

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-5;
int n, m, cnt;
bool ok, no, used[4];
double a[4];
struct node {
    int a[4];
} v;
vector<node>A;
void dfs2(int c, bool f) {
    if (c == n && fabs(a[0] - m) < eps) {
        ok = 1;

        if (!f)
            no = 1;

        return ;
    }

    for (int i = 0; i < n; i++)
        if (fabs(a[i] - floor(a[i])) > eps)
            f = 1;

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            if (used[i] || used[j])
                continue;

            double x = a[i], y = a[j];
            used[j] = 1;
            a[i] = x + y, dfs2(c + 1, f);
            a[i] = x - y, dfs2(c + 1, f);
            a[i] = y - x, dfs2(c + 1, f);
            a[i] = x * y, dfs2(c + 1, f);

            if (fabs(y) > eps)
                a[i] = x / y, dfs2(c + 1, f);

            if (fabs(x) > eps)
                a[i] = y / x, dfs2(c + 1, f);

            a[i] = x, a[j] = y, used[j] = 0;
        }
}
void dfs1(int x, int last) {
    if (x == n) {
        ok = no = false;
        dfs2(1, false);

        if (ok && !no) {
            v.a[0] = (int)a[0];
            v.a[1] = (int)a[1];
            v.a[2] = (int)a[2];
            v.a[3] = (int)a[3];
            A.push_back(v);
        }

        return ;
    }

    for (int i = last; i <= 13; i++)
        a[x] = i, dfs1(x + 1, i);
}
int main() {
    scanf("%d%d", &n, &m);
    dfs1(0, 1);
    printf("%d\n", cnt = A.size());

    for (int i = 0; i < cnt; i++) {
        for (int j = 0; j < n; j++)
            printf("%d ", A[i].a[j]);

        printf("\n");
    }
}

I

对于操作 ,利用差分可以将区间异或转为单点异或。具体的，作 的差分数组 ，有 ，则 。 每次区间 异或 改为 单点异或 ，最后还原即可。

而操作 乍一看很 ，但是按位考虑会发现很有规律。

如看 的第三位。依次是

发现每 位一个循环。那么不妨以 来分类，构造一个表格，第 行第 列表示 。会发现需要异或的是由一个矩阵加上剩下多出来的一个宽为 的矩阵。在二维差分数组上打标记，最后二维前缀和回去。最终 其中 为所有二进制位下，二位前缀和后的异或值。

时间复杂度 ，空间复杂度 ，当然可以用 bitset 优化到 的空间。

#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 9;
int n, q;
int a[N], b[N];
int d[N][22];
int main() {
    scanf("%d%d", &n, &q);

    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    while (q--) {
        int op, l, r, x;
        scanf("%d%d%d%d", &op, &l, &r, &x);

        if (op == 0)
            b[l] ^= x, b[r + 1] ^= x;
        else {
            for (int i = 0; i <= 19; i++)
                if ((x & (1 << i)) && (l + (1 << i)) - 1 <= r) {
                    d[l][i] ^= 1;
                    b[l] ^= (x >> i) << i;
                    b[l + (1 << i)] ^= (x >> i) << i;
                    l += (1 << i);
                    x += (1 << i);
                }

            for (int i = 19; i >= 0; i--)
                if ((l + (1 << i) - 1) <= r) {
                    d[l][i] ^= 1;
                    b[l] ^= (x >> i) << i;
                    b[l + (1 << i)] ^= (x >> i) << i;
                    l += (1 << i);
                    x += (1 << i);
                }
        }
    }

    for (int i = 19; i >= 1; i--)
        for (int j = 1; j <= n; j++) {
            if (!d[j][i])
                continue;

            d[j][i - 1] ^= 1;

            if (j + (1 << i - 1) <= n) {
                d[j + (1 << i - 1)][i - 1] ^= 1;
                b[j + (1 << i - 1)] ^= (1 << i - 1);

                if (j + (1 << i) <= n)
                    b[j + (1 << i)] ^= (1 << i - 1);
            }
        }

    for (int i = 1; i <= n; i++) {
        b[i] ^= b[i - 1];
        printf("%d ", a[i]^b[i]);
    }

    return 0;
}

J

如果不存在限制，三角形数目是 ，那考虑容斥用总数减去不合法的个数。

因为两两之间都会有边，那么枚举一个顶点，他的黑边数乘上白边数就是包含他的不合法的三角形的个数。观察一个不合法的三角形，会有一条边和另外两条边颜色不一样。会在这一条边的两个端点都计算一次答案。所以最终计算的不合法的个数要除以 。最后输出 减去不合法的个数

#include <bits/stdc++.h>
using namespace std;
const int N = 8e3 + 9;
namespace GenHelper {
    unsigned z1,z2,z3,z4,b,u;
    unsigned get() {
        b=((z1<<6)^z1)>>13;
        z1=((z1&4294967294U)<<18)^b;
        b=((z2<<2)^z2)>>27;
        z2=((z2&4294967288U)<<2)^b;
        b=((z3<<13)^z3)>>21;
        z3=((z3&4294967280U)<<7)^b;
        b=((z4<<3)^z4)>>12;
        z4=((z4&4294967168U)<<13)^b;
        return (z1^z2^z3^z4);
    }
    bool read() {
        while (!u) u = get();
        bool res = u & 1;
        u >>= 1;
        return res;
    }
    void Srand(int x) {
        z1=x;
        z2=(~x)^0x233333333U;
        z3=x^0x1234598766U;
        z4=(~x)+51;
        u = 0;
    }
}
using namespace GenHelper;
bitset<N>e[N];
int main() {
    int n, seed ;
    long long ans = 0, res = 0;
    cin >> n >> seed;
    ans = 1ll * n * (n - 1) * (n - 2);
    Srand(seed);

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            e[j][i] = e[i][j] = read();

    for (int i = 0; i < n; i++) {
        int a = e[i].count();
        res += 1ll * a * (n - 1 - a);
    }

    printf("%lld\n", (ans / 6 - (res / 2)));
    return 0;
}
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
腾讯音乐娱乐集团2024校园招聘-技术研究类笔试（I）
深信服23届秋招测试开发A卷
网易互娱2022实习生游戏设计师方向问答题汇总
全部 >
面经
面试常考问题整理
23届联想面经分享： 秋招上岸
22届-国企上岸经验分享
Springboot全套注解解析《看不懂算我输》
全部 >
内推
员工内推码获取
体验中心实习生招募 - 淘天集团
携程内推携程内推码
小鹏内推来了！共1000多个岗位！
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

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

本文相关内容

等你来战

查看全部

热门推荐

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”