首页 > 其他分享 >2023牛客暑期多校训练营6 ABCEG

2023牛客暑期多校训练营6 ABCEG

时间：2023-08-10 09:00:33浏览次数：52  
标签：fa int sum ABCEG 多校 牛客 i128 using 复杂度

比赛链接

A

题解

方法一

知识点：并查集，树形dp，背包dp。

因为需要路径中的最大值，因此考虑按边权从小到大加入图中，保证通过这条边产生贡献的点对已经全部出现。

在加边的同时进行树上背包，答案存在集合根节点里即可。

树上背包需要用到上下界限制的转移优化，能将复杂度从 \(O(n^3)\) 降到 \(O(n^2)\) ，基本思想是每个点对只在LCA处贡献一次。

时间复杂度 \(O(n^2)\)

空间复杂度 \(O(n^2)\)

方法二

知识点：Kruskal重构树，树形dp，背包dp。

对原图进行最小生成树性质的Kruskal重构，任意两点的LCA点权为路径最大值。

然后，在这棵重构树上进行dp，核心内容一致，区别在于原边权变为了点权，原子树大小变为叶子节点个数。

时间复杂度 \(O(n^2)\)

空间复杂度 \(O(n^2)\)

代码

方法一

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct DSU {
    vector<int> fa;
    vector<int> sz;

    DSU(int n = 0) { init(n); }

    void init(int n) {
        fa.assign(n + 1, 0);
        sz.assign(n + 1, 1);
        iota(fa.begin(), fa.end(), 0);
    }

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

    bool same(int x, int y) { return find(x) == find(y); }

    void merge(int x, int y) {
        sz[y] += sz[x];
        fa[find(x)] = find(y);
    }
};

tuple<int, int, int> e[3007];
bool black[3007];
int cost[3007];

ll f[3007][3007];
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> black[i];
    for (int i = 1;i <= n;i++) {
        cin >> cost[i];
        f[i][black[i]] = 0;
        f[i][black[i] ^ 1] = -cost[i];
    }
    for (int i = 1;i <= n - 1;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = { w,u,v };
    }

    sort(e + 1, e + n);
    DSU dsu(n);
    for (int i = 1;i <= n;i++) {
        auto [w, u, v] = e[i];
        u = dsu.find(u);
        v = dsu.find(v);
        vector<ll> g(n + 1, -1e18);
        for (int j = 0;j <= dsu.sz[u];j++) {
            for (int k = 0;k <= dsu.sz[v];k++) {
                ll val = 1LL * (j * (dsu.sz[v] - k) + k * (dsu.sz[u] - j)) * w;
                g[j + k] = max(g[j + k], f[u][j] + f[v][k] + val);
            }
        }
        for (int j = 0;j <= dsu.sz[u] + dsu.sz[v];j++) f[u][j] = g[j];
        dsu.merge(v, u);
    }
    ll ans = 0;
    for (int i = 0;i <= n;i++) ans = max(ans, f[dsu.find(1)][i]);
    cout << ans << '\n';
    return 0;
}

方法二

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct DSU {
    vector<int> fa;
    vector<int> sz;

    DSU(int n = 0) { init(n); }

    void init(int n) {
        fa.assign(n + 1, 0);
        sz.assign(n + 1, 1);
        iota(fa.begin(), fa.end(), 0);
    }

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

    bool same(int x, int y) { return find(x) == find(y); }

    void merge(int x, int y) {
        sz[y] += sz[x];
        fa[find(x)] = find(y);
    }
};

int n;
struct edge {
    int u, v, w;
}e[3007];
bool black[3007];
int cost[3007];

int g_w[6007];
vector<int> g[6007];
DSU dsu;
void kruskal_rebuild() {
    sort(e + 1, e + n, [&](const edge &a, const edge &b) {return a.w < b.w;});
    dsu.init(2 * n - 1);
    for (int i = 1;i <= n - 1;i++) {
        auto [u, v, w] = e[i];
        u = dsu.find(u);
        v = dsu.find(v);
        g_w[n + i] = w;
        g[n + i].push_back(u);
        g[n + i].push_back(v);
        dsu.merge(u, n + i);
        dsu.merge(v, n + i);
    }
}
/// kruskal重构树，O(mlogm)，图重构为树后任意两点LCA的权值是路径瓶颈
//* 最小生成树 <=> u-v所有路径最大边权中的最小值

ll sz[6007], f[6007][3007];
void dfs(int u) {
    sz[u] = u <= n;
    for (auto v : g[u]) {
        dfs(v);
        vector<ll> ff(n + 1, -1e18);
        for (int i = 0;i <= sz[u];i++) {
            for (int j = 0;j <= sz[v];j++) {
                ll val = 1LL * (i * (sz[v] - j) + j * (sz[u] - i)) * g_w[u];
                ff[i + j] = max(ff[i + j], f[u][i] + f[v][j] + val);
            }
        }
        for (int i = 0;i <= sz[u] + sz[v];i++) f[u][i] = ff[i];
        sz[u] += sz[v];
    }
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> black[i];
    for (int i = 1;i <= n;i++) {
        cin >> cost[i];
        f[i][black[i]] = 0;
        f[i][black[i] ^ 1] = -cost[i];
    }
    for (int i = 1;i <= n - 1;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = { u,v,w };
    }

    kruskal_rebuild();
    dfs(2 * n - 1);

    ll ans = 0;
    for (int i = 0;i <= n;i++) ans = max(ans, f[2 * n - 1][i]);
    cout << ans << '\n';
    return 0;
}

B

题解

知识点：排列组合。

只有大小相同的多重子集才能产生贡献。对于一对子集，显然从小到大排序后，对应数字的差的绝对值的和就是最小操作次数，现在考虑枚举每个点对产生的贡献。

对于一组点对 \((i,j)\) 表示A中第 \(i\) 个数和B中第 \(j\) 个数在对应位置，那么包含它们的子集有：

\[\begin{aligned} \left( \sum_{k = 0}^{\min(i-1,j-1)} \dbinom{i-1}{k} \dbinom{j-1}{k} \right) \cdot \left( \sum_{k = 0}^{\min(n-i,n-j)} \dbinom{n-i}{k} \dbinom{n-j}{k} \right) \end{aligned} \]

直接算是 \(O(n)\) 的，无法预处理，这里需要用到范德蒙德卷积公式：

\[\begin{aligned} \sum_{i = 0}^{k} \dbinom{n}{i} \dbinom{m}{k-i} = \dbinom{n+m}{k} \end{aligned} \]

其中一个推论是：

\[\begin{aligned} \sum_{i = 0}^{m} \dbinom{n}{i} \dbinom{m}{m-i} = \sum_{i = 0}^{m} \dbinom{n}{i} \dbinom{m}{i} = \dbinom{n+m}{m} \end{aligned} \]

因此原式可以化简为 \(O(1)\) 的计算。

时间复杂度 \(O(n^2)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int P = 998244353;
namespace Number_Theory {
    const int N = 4e3 + 7;
    int qpow(int a, ll k) {
        int ans = 1;
        while (k) {
            if (k & 1) ans = 1LL * ans * a % P;
            k >>= 1;
            a = 1LL * a * a % P;
        }
        return ans;
    }
    int fact[N], invfact[N];
    void init(int n) {
        fact[0] = 1;
        for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % P;
        invfact[n] = qpow(fact[n], P - 2);
        for (int i = n;i >= 1;i--) invfact[i - 1] = 1LL * invfact[i] * i % P;
    }
}
namespace CNM {
    using namespace Number_Theory;
    int C(int n, int m) {
        if (n == m && m == -1) return 1; //* 隔板法特判
        if (n < m || m < 0) return 0;
        return 1LL * fact[n] * invfact[n - m] % P * invfact[m] % P;
    }
}
/// 公式法求组合数，O(n)，预处理阶乘及其逆元快速求出组合数

int a[2007], b[2007];
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) cin >> b[i];
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    CNM::init(2 * n);
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            int val = abs(a[i] - b[j]);
            (ans += 1LL * CNM::C(i + j - 2, min(i, j) - 1) * CNM::C(2 * n - i - j, min(n - i, n - j)) % P * val % P) %= P;
        }
    }
    cout << ans << '\n';
    return 0;
}

C

题解

知识点：数学。

显然，\(2\) 的个数远比 \(5\) 多，因此我们只需要计算 \(5\) 因子的个数即可。

我们化简后有如下式子：

\[\begin{aligned} \prod_{i=1}^n i!! = 1^{\left\lceil \frac{n}{2} \right\rceil} \cdot 2^{\left\lfloor \frac{n}{2} \right\rfloor} \cdot 3^{\left\lceil \frac{n}{2} \right\rceil - 1} \cdot 4^{\left\lfloor \frac{n}{2} \right\rfloor - 1} \cdots \end{aligned} \]

注意到， \(5\) 的倍数会贡献一次， \(5^2\) 的倍数又会贡献一次，以此类推。因此，我们按 \(5\) 的幂求幂次数总和即可。

但是，这里奇数和偶数的幂次规律是不同的，但都是等差，分别求一下即可。例如， \(5\) 的倍数时，分别求 \(5,15,25,\cdots\) 和 \(10,20,30,\cdots\) 两个幂次等差数列的和即可。

时间复杂度 \(O(\log n)\)

空间复杂度 \(O(1)\)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;

template<class T>
inline void write(T x) {
    if (x < 0) { putchar('-');x = -x; }
    if (x >= 10) write(x / 10);
    putchar(x % 10 + '0');
}

i128 calc1(i128 n, i128 x) {
    i128 a1 = (n + 1) / 2 - x / 2;
    i128 an = a1 % x;
    i128 cnt = (a1 - an) / x + 1;
    return (a1 + an) * cnt / 2;
}

i128 calc0(i128 n, i128 x) {
    i128 a1 = n / 2 - x + 1;
    i128 an = a1 % x;
    i128 cnt = (a1 - an) / x + 1;
    return (a1 + an) * cnt / 2;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n;
    cin >> n;
    i128 x = 5, ans = 0;
    while (n >= x) {
        if (n >= 2 * x) ans += calc0(n, x);
        ans += calc1(n, x);
        x *= 5;
    }
    write(ans);
    puts("");
    return 0;
}

E

题解

知识点：枚举，前缀和。

我们求出前缀和 \(sum\)，那么原式改写为 \(sum_{b_1} - sum_{l-1},sum_{b_2} - sum_{b_1} \cdots\) 。显然，当 \(sum_{l-1}\) 和 \(sum_{r}\) 不同奇偶时无解，否则需要在 \([l,r-1]\) 的前缀和之间找到 \(k-1\) 个和 \(sum_{l-1},sum_{r}\) 同奇偶的位置，这个过程可以用 \(cnt\) 记录前缀和奇偶个数的前缀和，可以 \(O(1)\) 查询。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll a[100007];
int cnt[100007];
bool solve() {
    int n, q;
    cin >> n >> q;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        a[i] += a[i - 1];
        cnt[i] = (a[i] & 1) + cnt[i - 1];
    }
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        if ((a[l - 1] & 1) != (a[r] & 1)) {
            cout << "NO" << '\n';
            continue;
        }
        int res = cnt[r - 1] - cnt[l - 1];
        if (!(a[l - 1] & 1)) res = r - l - res;
        if (res >= k - 1) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

G

题解

知识点：GCD和LCM。

可以分三类讨论：

  1. 当 \(x,y = 0\) 时，当且仅当 \(z = 0\) 时有解。
  2. 否则，当 \(x = 0\) 或 \(y = 0\) 时，当且仅当 \(z\) 为其中非零数的倍数时有解。
  3. 否则，当且仅当 \(z\) 是 \(0\) 或者 \(\gcd(x,y)\) 的倍数时有解。

时间复杂度 \(O(T\log{\min\{x_i,y_i\}})\)

空间复杂度 \(O(1)\)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool solve() {
    int x, y, z;
    cin >> x >> y >> z;
    int d = gcd(x, y);
    if (x == 0 && y == 0) {
        if (z == 0) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
    else if (x == 0 || y == 0) {
        if (z % d == 0) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
    else {
        if (z && z % d == 0) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

标签：fa,int,sum,ABCEG,多校,牛客,i128,using,复杂度
From： https://www.cnblogs.com/BlankYang/p/17619254.html

相关文章

  • 2018牛客多校第五场 F take[树状数组]
    理解题目画了一个二叉树，然后思维定势让我想构建一个有n层的二叉树，然后统计叶子节点。。有点恐怖。但是正解是考虑每一个箱子对答案的贡献。图片来自take_baymax520的博客对于每个箱子，它要发生交换也就是为答案贡献的条件是它当前宝石大小小于它的大小。对于比它小的宝石之前取......
  • 杭电多校 2023 杂题题解
    打算只写点有意思的题。D1JEasyproblemI注意到\(x_i\)单增，所以一个数被减到负数之后，所有的操作都会将它减到负数，也就等价于乘\(-1\)再相加。使用一棵线段树维护所有数，将这些数分为两种，一种如上，一种是区间减。最终所有数都会变为需要乘\(-1\)再相加的数，于是只要每次精......
  • 根号分治-2023牛客7 E-Star Wars
      也就是说对于大点和小点我们采用不同的方式维护对于大点来说我们只需要记录它的周围点的总和不需要知道具体的谁链接了它 对于小点我们需要维护它的所有信息他自己链接了哪些点 需要再开一个vector表示自己链接的大点这样大对大或者小对大的时候维护的信息也......
  • 牛客网整数位宽转换
    1、veilog进阶篇VL32非整数倍数据位宽转换24to48描述：实现数据位宽转换电路，实现24bit数据输入转换为128bit数据输出。其中，先到的数据应置于输出的高bit位。valid_in用来指示数据输入data_in的有效性，valid_out用来指示数据输出data_out的有效性；clk是时钟信号；rst_n是异步复位信......
  • 2023第七场牛客多校-We Love Strings
    I-WeLoveStrings_2023牛客暑期多校训练营7题意 做法：根号分治+容斥原理将字符串分为两类：len<=20直接位运算枚举出可能的所有答案，看是否存在符合的len>20采用容斥原理，计算出所有长度为i的字符串中（假设为n个），1个字符串可以表示的(1个元素的交集) ，2个字符串可以表示的......
  • 2023牛客+杭电补题和总结记录（后半）
    前半继续写要被编辑器卡飞了，换个档杭电第六场\(1002.Pair\Sum\and\Perfect\Square\)对于每个位置可以求出该位置的数和哪些位置的数能够组成完全平方数，因为原序列是排列，并且完全平方数个数不多，所以预处理的复杂度不高。（也可以在后续统计过程中处理）处理出点对以后就变成了......
  • 牛客周赛 Round 6
    牛客周赛Round6A-游游的数字圈_牛客周赛Round6(nowcoder.com)枚举即可#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr);strings;cin>>s;intans=0;......
  • 记一场很厉害的牛客多校
    破防场。全是诈骗提。但是很有可以学的东西！\(I.\)给定\(n\)个01?串，?可以替换为0或1。称替换完的串集合为该串的生成串。问所有\(n\)个串的生成串集合的并的大小。长度不同的串分开处理。对于长度\(\le20\)的串，暴力枚举生成串，map去重。对于长度\(>20\)的......
  • 2023年多校联训NOIP层测试2
    T1 斐波那契树题目思路题解做法：可以先把白色边权看成1，黑色边权看成0，求最小生成树和最大生成树，判断这两个值之间是否存在一个斐波那契数。可以证明这中间的值都是可以出现的（参考求恰好k条白边的思路，BZOJ2654）。我的做法：找到最小生成树和最大生成树的值。看它们是否在点击......
  • 2023年多校联训NOIP层测试4+洛谷 8 月月赛 I & RiOI Round 2
    2023年多校联训NOIP层测试4爆零了T1幸运数字\(0pts\)T2密码\(0pts\)没做到，咕了。T3小X和他的朋友们\(0pts\)没做到，咕了。T4树上询问\(0pts\)没做到，咕了。【LGR-150-Div.2】洛谷8月月赛I&RiOIRound2T1luoguP9496「RiOI-2」hacker\(100pts\)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99