2021牛客暑期多校训练营3

B、Black and white

题目大意

地图规模为级别，点权依靠公式生成，你可以花费点权那么多钱涂黑一个点，如果长方形中个顶点被涂黑了，那么剩下的顶点可以免费涂黑，询问将整张图涂黑的最小代价是多少？

Solution

考点：并查集

我们如何看待涂黑个点第四个点可以免费这个是我们解题的关键。

将个点沿着轴轴方向一路延申，你会发现选中的三个点才会联通在一起，并且我们可以免费填涂的第四个点也在他们的连通块之中。

那么我们把每个看成连接了​这样行列两个点的权值，做一次特殊一点的最小生成树即可。

#include <bits/stdc++.h>
using namespace std;
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define debug(x) cout << #x << ":" << x << '\n'
typedef tuple<int, int> tup;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = 1e5 + 7;
ll n, m;
ll a, b, c, d, p;
vector<pai> G[N];

int fa[5005 * 2];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

int solve() {
    n = read(), m = read(), a = read(), b = read(), c = read(), d = read(), p = read();
    ll pre = a, now;
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            now = (pre * pre * b + pre * c + d) % p;
            pre = now;
            G[now].push_back({ i, n + j });
        }
    }
    for (int i = 1; i <= n + m; ++i)    fa[i] = i;
    int fu, fv;
    ll res = 0;
    int sz = 0;
    for (int i = 0; i < p; ++i) {
        for (auto& [u, v] : G[i]) {
            fu = find(u), fv = find(v);
            if (fu != fv) {
                fa[fv] = fu;
                res += i;
                ++sz;
                if(sz == n + m - 1){
                    print(res);
                    return 1;
                }
            }
        }
    }

    return 1;
}

int main() {
    //int T = read(); for (int i = 1; i <= T; ++i)
    {
        solve();
        //cout << (solve() ? "YES" : "NO") << endl;
    }
    return 0;
}

C、Minimum grid

题目大意

你有一个​的矩阵，他里面有​个位置必须填非负整数，并且要求填入的数必须​。

并且给出每行的最大值，以及每列的最大值，要求我们构造一个这样合理的行列最大值矩阵的最小是多少。

Solution

考点：匈牙利算法

首先我们肯定是从小往大开始枚举填入数的大小，接下来我们可以知道有哪些行，哪些列他们的最大值就是这个数。

因为我们被允许填，所以我们在每一行每一列存在一个他要求的就行了。那么对于一些不相交的行列来说，我们并不能少填某些数，只有在某行某列的最大值相同，并且这行这列还被允许填入数字的时候，这时我们填入一个最大值相当于同时满足了个条件，那么我们就可以少算一次。

那么可能会有某一行和很多列的最大值相同，也可能会有很多汗和某一列的最大值相同，那么求解这个最大匹配的问题就用到匈牙利算法就行了。

最终这个就被计算了行数加列数减去匹配数那么多次。

#include <bits/stdc++.h>
using namespace std;
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define debug(x) cout << #x << ":" << x << '\n'
typedef tuple<int, int> tup;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = 2e3 + 7, M = 1e6 + 7;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};
ll n, m, k;

vector<int> rows[M], cols[M], G[N << 1];
bool vis[N][N];

bool st[N << 1];
int match[N << 1];

bool find(int u) {
    for (auto& v : G[u]) {
        if (st[v])    continue;
        st[v] = 1;
        if (match[v] == -1 || find(match[v])) {
            match[v] = u;
            return 1;
        }
    }
    return 0;
}

int solve() {
    n = read(), m = read(), k = read();
    int x, y;
    for (int i = 1; i <= n; ++i) {
        x = read();
        rows[x].push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
        x = read();
        cols[x].push_back(n + i);
    }
    for (int i = 1; i <= m; ++i) {
        x = read(), y = read();
        vis[x][y] = 1;
    }

    ll res = 0;
    for (int i = 1; i <= k; ++i) {
        if (rows[i].size() == 0 && cols[i].size() == 0)
            continue;
        for (int i = 1; i <= n + n; ++i)    G[i].clear();
        for (auto& row : rows[i])
            for (auto& col : cols[i])
                if (vis[row][col - n]) {
                    G[row].push_back(col);
                    G[col].push_back(row);
                }

        ms(match, -1);
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            ms(st, 0);
            if (find(i)) ++cnt;
        }
        res += (rows[i].size() + cols[i].size() - cnt) * 1ll * i;
    }
    print(res);

    return 1;
}

int main() {
    //int T = read(); for (int i = 1; i <= T; ++i)
    {
        solve();
        //cout << (solve() ? "YES" : "NO") << endl;
    }
    return 0;
}

E、Math

题目大意

想要你求解的有多少对？。

Solution

考点：OEIS韦达定理

赛中的时候通过枚举，然后把全部合理的丢进OEIS之后发现真有这个数列8 27 30 64 112 - OEIS。

然后就发现了生成的公式：

然后枚举全部可能的，得到全部的，之后进行​就行了。

关于正确的韦达定理解法可以看看这个博主的E.Math 解题报告（结论、打表）。

const int N = 1e7 + 7;
const ll M = 1e18 + 1;
ll n, m;
ll f[N]; // f[i] = x^2 * f[i-1] - f[i-2]
int cnt = 0;

void init(){
    for (ll i = 2; i * i * i <= M; ++i) {
        ll x = i, y = i * i * i;
        while (y <= M) {
            f[++cnt] = y;
            if ((M + x) / i / i < y)    break;
            ll tmp = y * i * i - x;
            x = y;
            y = tmp;
        }
    }
    sort(f + 1, f + 1 + cnt);
}

int solve() {
    n = read();
    print(upper_bound(f + 1, f + 1 + cnt, n) - f);

    return 1;
}

F、24dian

Solution

对这个题目挺无语的，比较讨厌这种有先决条件的题目，你首先要会传统意义上的点才能做出这题，我就没听说过这种游戏，题目也不带解释。如果你会玩原先的​点，那么这题就变成一个纯模拟题，就是原先的基础上加了必须要有不能整除的除法方案。

const int N = 1e6 + 7;

const double eps = 1e-8;
ll n, m;
vector<vector<int>> res;
vector<int> v;

int cnt1, cnt2;

bool isok(const double& x) {
    return x > (int)x + eps;
}

bool isok(const double& x,const double& y) {
    return isok(x) || isok(y) || isok(x / y);
}

void dfs2(bool ok, vector<double> a) {
    int sz = a.size();
    if (sz == 1) {
        if (fabs(a[0] - m) < eps) {
            ++cnt1; // 一组构成m的解
            if (ok)    ++cnt2; // 构成m的前提下还要有分数的解
        }
        return;
    }
    for (int i = 0; i < sz; ++i) {
        for (int j = 0; j < sz; ++j) {
            if (i == j)    continue;
            vector<double> p;
            for (int k = 0; k < sz; ++k) {
                if (k != i && k != j)
                    p.push_back(a[k]);
            }

            p.push_back(a[i] + a[j]);
            dfs2(ok, p);
            p.pop_back();

            p.push_back(a[i] - a[j]);
            dfs2(ok, p);
            p.pop_back();

            p.push_back(a[i] * a[j]);
            dfs2(ok, p);
            p.pop_back();

            p.push_back(a[i] / a[j]);
            dfs2(ok | isok(a[i], a[j]), p);
            p.pop_back();
        }
    }
}

bool check(const vector<int> a) {
    cnt1 = cnt2 = 0;
    vector<double> b(n);
    for (int i = 0; i < n; ++i)    b[i] = a[i];
    dfs2(false, b);
    if (cnt1 && cnt1 == cnt2)    return true;
    return false;
}

void dfs1(int dep, int pre) {
    if (dep == n + 1) {
        if (check(v))
            res.push_back(v);
        return;
    }
    for (int i = pre; i <= 13; ++i) {
        v.push_back(i);
        dfs1(dep + 1, i);
        v.pop_back();
    }
}

int solve() {
    n = read(), m = read();
    dfs1(1, 1);

    print(res.size());
    for (auto& it : res) {
        for (int i = 0, sz = it.size(); i < sz; ++i) {
            print(it[i], " \n"[i + 1 == sz]);
        }
    }

    return 1;
}

G、Yu Ling(Ling YueZheng) and Colorful Tree

题目大意

给出一棵有根树，根节点是，树上边权告诉你。之后题目有两种操作。

  1. 选择一个点把它变成一种颜色​，保证任意时间内某种颜色只会有一个唯一的。
  2. 询问对于一个点，在他的祖先们中，谁离最近并且满足的颜色是的倍数，并且的颜色在区间中。

Solution

标答写的是树分块+，不过好像没什么人是这么写的。

赛后见了一个暴力的做法居然过了，跑出树上节点的序和时间戳。

然后暴力的枚举中间的倍数，因为颜色和唯一对应，那么我们就可以通过时间戳判断是不是祖先关系。

不过这种做法好像挺假的，看了逆十字的代码，因为颜色都是正的好像祖先关系可以通过二分去找…

const int N = 1.1e5 + 7;
ll n, m;
vector<pai> G[N];
int dep[N], in[N], out[N], tot, pos[N];

void dfs(int u) {
    in[u] = ++tot;
    for (auto& [v, w] : G[u]) {
        if (in[v])    continue;
        dep[v] = dep[u] + w;
        dfs(v);
    }
    out[u] = ++tot;
}

int solve() {
    n = read(), m = read();
    int u, v, w;
    for (int i = 1; i < n; ++i) {
        u = read(), v = read(), w = read();
        G[u].push_back({ v,w });
        G[v].push_back({ u,w });
    }
    dfs(1);

    int op, l, r, x;
    while (m--) {
        op = read();
        if (!op) {
            u = read(), x = read();
            pos[x] = u; // 当前颜色x的节点编号为u
        }
        else {
            u = read(), l = read(), r = read(), x = read();
            int be = (l + x - 1) / x * x;
            int ans = LLONG_MAX;
            for (int i = be; i <= r; i += x) {
                if (pos[i] == 0)    continue;
                if (in[pos[i]] <= in[u] && out[pos[i]] >= out[u]) {
                    ans = min(ans, dep[u] - dep[pos[i]]);
                }
            }
            if (ans == LLONG_MAX)    puts("Impossible!");
            else print(ans);
        }
    }

    return 1;
}

J、Counting Triangles

题目大意

题目生成一个完全图，图上边权只有黑白两种，询问有多少个三角形边的颜色完全一致。

Solution

考点：容斥

我们思考在不存在限制的时候选择三角形数目等于，我们只需要用总数减掉不符合要求的三角形数目即可。

那么我们就要思考什么样的三角形是不符合要求的。一定是有一条边和另外两条边颜色不一样，那么这条不一样的变就会连接两个端点，这两个端点之间也一定连接着不同颜色的多条边。

我们就可以对每个点数他连接的黑边数和白边数，两者相乘就是非法的数量了，注意我们这里要除以，因为黑白，白黑被计算了两次。

int black[8005], white[8005];

int solve() {

    int n, seed;
    cin >> n >> seed;
    srand(seed);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            if (read())    ++black[i], ++black[j]; // 用他的生成函数
            else ++white[i], ++white[j];
        }


    ll ans = 1ll * n * (n - 1) * (n - 2) / 6, res = 0;
    for (int i = 0; i < n; ++i)    res += black[i] * white[i];

    print(ans - res / 2);

    return 1;
}
2021牛客暑期多校训练营 文章被收录于专栏

））补题-ing

全部评论

相关推荐

不愿透露姓名的神秘牛友
11-21 17:16
求帮选校招Offer：科大讯飞、金山办公
科大讯飞 算法工程师 28.0k*14.0, 百分之三十是绩效，惯例只发0.9
点赞 评论 收藏
分享
11-25 15:37
已编辑
北京邮电大学 银行其它
本科别学ai
坐标北邮ai,大四上学校硬排了五门专业课……大四上学期，我要上多模态，三维重建，情感计算，智能医学，专业实习，人工智能创新（这课很逆天，论文or三个月以上实习or竞赛）两周的小学期智能医学，没一点用，竟然还爆改八周，每周一次代码作业，还要出去实习，考研人的绝望时刻。学的多且杂，本科期间要学cv,nlp,语音，多模态，大模型，rag,数据库，计网，计原c++,vue,js,python……。注，大四这些课，只能在第七学期学，无法提前上。不然谁会大四留给自己一堆课。最后，一句话让你知道有多卷，保研最低89分。北邮其它专业还行啊，并且ai有三个方向，我仅在此吐槽ai人工智能方向排课不合理。以后如果有...
想去夏威夷的小哥哥在度假：更重要的是学ai只有本科学历是找不到工作的，建议取消本科ai专业
选完offer后，你后悔学本专业吗
点赞 评论 收藏
分享
10-09 22:05
666 C++
我这能报啥
找到工作就狠狠玩CSGO：报联合国演讲，报电子烟设计与制造
点赞 评论 收藏
分享
11-22 18:25
内蒙古财经大学 策略运营
mentor带实习生最烦的是什么？
实习生常见问题及应对建议作为一个过来人，我想和大家分享一下实习生在职场中常见的一些问题，以及如何避免这些问题，让你的实习经历更加顺利。1.&nbsp;好问但不自学很多实习生喜欢问问题，这本身是好事，但有些人不看资料、不做功课就直接来问。比如，明明资料里有答案，却懒得看，直接跑来问：“太复杂了，你跟我说说吧。”&nbsp;还有些基础概念，百度一下就能找到，却还是要问别人。更糟糕的是，问了也记不住，下次还问同样的问题。我的建议是，先自己查资料，实在不懂再问。这样不仅能减轻别人的负担，还能让你学到更多。毕竟，大家都有自己的工作，不可能全天候手把手教你。2.&nbsp;觉得自己被欺负有些实习生觉得被安排整理数据、调研竞品、打印文件...
投递百度等公司10个岗位 >
点赞 评论 收藏
分享
评论
1
收藏
分享

全站热榜

正在热议
# 25届秋招总结 #
379879次浏览 3769人参与
# 如果再来一次，你还会选择这个工作吗？ #
103048次浏览 1040人参与
# 北方华创开奖 #
64793次浏览 505人参与
# 地方国企笔面经互助 #
6120次浏览 14人参与
# 简历被挂麻了，求建议 #
2527504次浏览 33474人参与
# 发工资后，你做的第一件事是什么 #
4938次浏览 19人参与
# 阿里云管培生offer #
46550次浏览 1381人参与
# ai智能作图 #
11949次浏览 190人参与
# 我的实习求职记录 #
6108065次浏览 83848人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
9032次浏览 185人参与
# 上班到公司第一件事做什么？ #
14618次浏览 165人参与
# 阿里求职进展汇总 #
71884次浏览 780人参与
# 如何写一份好简历 #
616167次浏览 8700人参与
# 听到哪句话就代表面试稳了or挂了？ #
96802次浏览 810人参与
# 还记得你第一次面试吗？ #
29943次浏览 422人参与
# 华为工作体验 #
109463次浏览 852人参与
# 面试体验感最好的是哪家？ #
91654次浏览 921人参与
# 网易求职进展汇总 #
38961次浏览 334人参与
# 如果有时光机，你最想去到哪个年纪？ #
27155次浏览 561人参与
# 腾讯求职进展汇总 #
205929次浏览 1688人参与
# 硬件兄弟们 甩出你的华为奖状 #
76136次浏览 615人参与
# 上班苦还是上学苦呢？ #
107026次浏览 870人参与
牛客网
牛客企业服务