首页 > 其他分享 >蓝桥杯省赛真题（砍树 整数删除 景区导游 翻转硬币）

蓝桥杯省赛真题（砍树 整数删除 景区导游 翻转硬币）

时间：2023-08-22 18:12:08浏览次数：47  
标签：真题 int ll 我们 蓝桥 复杂度 LCA 省赛 节点

蓝桥杯省赛真题（砍树 整数删除 景区导游 翻转硬币）

四道比较难的题（题解是官方提供的）

砍树 （树上差分）

https://www.lanqiao.cn/problems/3517/learning/

解题思路

在这个问题中，我们需要找到一条边，砍掉它之后，所有给出的节点对 \((a_i, b_i)\) 之间都不再连通。换言之，这条边应是所有 \((a_i, b_i)\) 的通路必经之路。

为了找到这样的边，我们需要先确定这些路径（节点对 \((a_i, b_i)\) 之间的通路）的交集。即我们要找到一些节点，这些节点是所有路径的公共部分。

这些节点其实就是所有 \((a_i, b_i)\) 的最近公共祖先（LCA）。为什么呢？因为对于任意两个节点 \(a\) 和 \(b\)，它们的路径必然经过它们的最近公共祖先。也就是说，如果我们找到了所有 \((a_i, b_i)\) 的 LCA，那么这些 LCA 就是所有路径的交集。因此，我们需要找到的边就是连接这些 LCA 与它们父节点的边。

举个例子，假设我们有三对节点，\((a_1, b_1)\)、\((a_2, b_2)\)、\((a_3, b_3)\)，它们的 LCA 分别是 \(c_1\)、\(c_2\)、\(c_3\)。假设 \(c_1\) 是 \(c_2\) 的祖先，\(c_2\) 是 \(c_3\) 的祖先，那么所有的路径都会经过节点 \(c_2\)，所以我们需要找的边就是连接 \(c_2\) 和它的父节点的边。

所以，我们需要做的第一步就是找到所有 \((a_i, b_i)\) 的 LCA。这可以通过一种叫做“倍增”的算法来实现。这种算法可以在 \(O(\log n)\) 的时间内找到任意两个节点的 LCA。

之后我们还需要使用树上差分的思想来处理这个问题，首先对每一对 \((a_i, b_i)\) 的路径进行 \(+1\) 操作，这意味着我们在 \(a_i\) 和 \(b_i\) 之间添加了一条边。接着，我们对它们的最近公共祖先（LCA）进行 \(-2\) 操作，这意味着我们从 LCA 中移除了两条边（因为从根节点到 LCA 的路径被计算了两次，所以需要减去两次）。

这个操作可以使用深度优先搜索（DFS）来实现。首先，对所有的节点对进行 \(+1\) 操作，然后对它们的 LCA 进行 \(-2\) 操作。然后，使用 DFS 从根节点开始，更新每个节点的计数值。

在这些操作之后，如果一个节点的计数值等于 \(m\)（对数的数量），那么这个节点就是所有 \((a_i, b_i)\) 的通路的交点。因为，只有当所有的 \((a_i, b_i)\) 都经过某个节点时，这个节点的计数值才会等于 \(m\)。换句话说，从根节点到这个节点的路径就是我们需要找的边。

具体实现

  1. 初始化：首先，我们需要初始化每个节点的深度和父节点。我们从树的根节点开始，递归地设置每个节点的深度（即距离根节点的距离）和父节点。
  2. 计数：接下来，我们需要找到所有 \((a_i, b_i)\) 的路径，并将它们的计数添加到数组中。具体来说，我们将路径上的每个节点的计数加一，但是要将它们的最近公共祖先的计数减二。这样做的目的是，如果一个节点的计数值等于 \(m\)，那么从根节点到该节点的路径就是我们需要找的边。
  3. 深度优先搜索：然后，我们通过深度优先搜索，遍历所有的节点，更新它们的计数值。我们从根节点开始，对每个节点的子节点进行递归操作，更新每个节点的计数值。
  4. 寻找结果：最后，我们再次遍历所有的节点，找出计数值等于 \(m\) 的节点。如果存在多个这样的节点，我们取其中编号最大的边作为结果。

Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 5, M = 20;
ll n, m, dep[N], cnt[N];
vector<pii> v[N];
int id[N], f[N][M];

void dfs (int u, int fa) {
    dep[u] = dep[fa] + 1, f[u][0] = fa;
    for (int i = 1; (1 << i) <= dep[u]; i++)    f[u][i] = f[f[u][i-1]][i-1];
    for (auto vi : v[u]) {
        int j = vi.first;
        if (j == fa)    continue;
        dfs (j, u);
        id[j] = vi.second;
    }
}

int lca (int a, int b) {
    if (dep[a] < dep[b])    swap (a, b); //确保a往上跳
    for (int k = 15; k >= 0; k--) {
        if (dep[f[a][k]] >= dep[b]) { //注意是>=
            a = f[a][k];
        }
    }
    if (a == b)     return a;
    for (int k = 15; k >= 0; k--) {
        if (f[a][k] != f[b][k]) {
            a = f[a][k], b = f[b][k];
        }
    }
    return f[a][0];
}

void add (int u, int fa) {
    //cnt[fa] += cnt[u]; //这里不行
    for (auto vi : v[u]) {
        int j = vi.first;
        if (j == fa)    continue;
        add (j, u);
        cnt[u] += cnt[j]; 
    }
}

int main () {
    scanf ("%lld%lld", &n, &m);
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf ("%d%d", &a, &b);
        v[a].push_back ({b, i}), v[b].push_back ({a, i});
    }
    dfs (1, 0); //倍增初始化
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf ("%d%d", &a, &b);
        cnt[a]++, cnt[b]++, cnt[lca(a, b)] -= 2;
    }
    add (1, 0); //求前缀和
    int ans = -1;
    for (int i = 1; i <= n; i++) {
        if (cnt[i] == m)    ans = max(ans, id[i]);
    }
    printf ("%d\n", ans);
}

整数删除 （优先队列）

https://www.lanqiao.cn/problems/3515/learning/

解题思路

删除数组中的任意元素的时间复杂度为 \(O(n)\)，本题存在大量删除操作，若使用数组会导致时间复杂度过大，故考虑使用链表进行存储、删除操作。而需要动态的求最小值，显然可以使用堆。每次从堆中取出最小值的下标，然后在链表中删除它。但本题特殊点在于将其删除，并把与它相邻的整数加上被删除的数值，所以会导致还在堆中的元素的权值变化。

我们可以注意到，每次删除操作只会让一些元素变大，而不会让元素变小。也就是，可能会让原本的最小值变成不是最小值。因此我们取出堆中的最小值时，需要将此元素的排序权值和实际的值进行对比，如果实际的值变大了，则当前元素并不一定是最小值，需要重新放回堆中。

具体做法如下：

  • 使用双向链表存储数列，并使用数组 \(v_i\) 存储每个节点的值，\(l_i\) 存储节点 \(i\) 的前驱节点，\(r_i\) 存储节点 \(i\) 的后继节点。
  • 使用最小堆存储数列中未被删除的节点，堆中的元素是 { 权值，结点下标}。
  • 初始化双向链表和最小堆，并将所有节点加入最小堆中。
  • 重复执行以下步骤 \(K\) 次：
    • 取出最小堆中的堆顶元素（最小值）。
    • 比较堆顶元素的权值和实际值是否相等，如果不相等，则说明这个节点的实际值已经发生了变化，当前元素并不一定是最小值，需要重新放回堆中，否则删除该节点，将其相邻节点的值加上被删除节点的值。
    • 如果需要重新放回堆中，那么需要将该节点的权值更新为实际值，并重新放回堆中。
  • 输出双向链表中剩余的节点的值。

每次删除操作最多会让两个元素的值变化，因此从堆中取出的次数是 \(K\) ，时间复杂度为 \(O((n + k)\log n)\)。

Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;
typedef pair<ll, ll> pii;
const int N = 5e5 + 5;
ll n, k, l[N], r[N], a[N];

int main () {
    scanf ("%lld%lld", &n, &k);
    priority_queue<pii, vector<pii>, greater<pii>> q;
    for (int i = 1; i <= n; i++) {
        scanf ("%lld", &a[i]);
        l[i] = i - 1, r[i] = i + 1; //双向链表
        q.push ({a[i], i});
    }
    while (k && !q.empty ()) {
        auto t = q.top ();
        q.pop ();
        ll val = t.first, id = t.second;
        if (val == a[id]) { //实际值等于当前值,可删除
            a[l[id]] += a[id], a[r[id]] += a[id], k--;
            r[l[id]] = r[id], l[r[id]] = l[id], a[id] = 0;
        }
        else    q.push ({a[id], id}); //把实际值放进来
    }
    for (int i = 1; i <= n; i++)    if (a[i])    cout << a[i] << ' ';
    cout << endl;
}

景区导游

https://www.lanqiao.cn/problems/3516/learning/

解题思路

最近公共祖先 （倍增求LCA）

其中 \(dis_{i, j}=dis_{v_i}+dis_{v_j}-2dis_{lca(v_i, v_j)}\)

Code

这题简单欸，比上一个LCA的简单

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 1e5 + 5, M = 20;
ll n, m, f[N][M], dep[N], v[N], ans;
ll h[N], e[N * 2], ne[N * 2], w[N * 2], idx;
ll del[N], dis[N];

void add (int a, int b, ll c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dfs (int u, int fa) {
    dep[u] = dep[fa] + 1, f[u][0] = fa;
    //dis[u] += dis[fa] + w[u];
    for (int i = 1; (1 << i) <= dep[u]; i++)    f[u][i] = f[f[u][i-1]][i-1];
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa)    continue;
        dis[j] += dis[u] + w[i];
        dfs (j, u);
    }
}

int lca (int a, int b) {
    if (dep[a] < dep[b])    swap (a, b); //确保a往上跳
    for (int k = 19; k >= 0; k--) {
        if (dep[f[a][k]] >= dep[b]) { //注意是>=
            a = f[a][k];
        }
    }
    if (a == b)     return a;
    for (int k = 19; k >= 0; k--) {
        if (f[a][k] != f[b][k]) {
            a = f[a][k], b = f[b][k];
        }
    }
    return f[a][0];
}

ll cal (int a, int b) {
    return dis[a] + dis[b] - 2ll * dis[lca (a, b)];
} 

int main () {
    memset (h, -1, sizeof h);
    scanf ("%lld%lld", &n, &m);
    for (int i = 1; i < n; i++) {
        int a, b;
        ll c;
        scanf ("%d%d%lld", &a, &b, &c);
        add (a, b, c), add (b, a, c);
    }
    dfs (1, 0);
    //for (int i = 1; i <= n; i++)    cout << dis[i] << ' ';
    //cout << endl;
    for (int i = 1; i <= m; i++)    scanf ("%lld", &v[i]);
    for (int i = 2; i <= m; i++)    del[i] = cal (v[i-1], v[i]), ans += del[i];
    printf ("%lld ", ans - del[2]);
    for (int i = 2; i < m; i++)     printf ("%lld ", ans - del[i] - del[i+1] + cal (v[i-1], v[i+1]));
    printf ("%lld\n", ans - del[m]);
}

翻转硬币

https://www.lanqiao.cn/problems/3509/learning/

解题思路

这个问题的解决方案建立在数论的基础上，主要使用了 Möbius 反演公式和 Dirichlet 卷积。我们可以先对问题进行一些转化和简化，然后对结果进行求和。

推理证明

  1. 首先，我们从硬币 \(1\) 开始，将所有对应硬币和它的倍数位置的硬币翻转。这种策略是有效的，因为我们每次操作都会翻转硬币 \(i\) 和它所有的倍数位置的硬币，这意味着我们实际上是在对硬币 \(i\) 的所有因子进行操作。

  2. 对每个硬币 \(i\)，我们定义 \(f(i)\) 为在递推过程中，硬币 \(i\) 是否需要被翻转。我们可以得到 \(f(i) = \sum_{d | i, d \neq i} f(d)\)，其中 \(d\) 是 \(i\) 的所有因子。

  3. 显然，硬币 \(1\) 一定会被翻转，所以我们有 \(f(1) = 1\)。对于其他硬币，因为它们最初都是朝上的，所以我们有 \(\sum_{d | i} f(d) = \varepsilon(i)\)。在 Dirichlet 卷积形式中，这可以写作 \(1 \times f = \varepsilon\)。对此进行 Möbius 反演，我们可以得到 \(f = \varepsilon \times \mu = \mu\)。根据此公式，我们知道当 \(f(i) = \mu(i) = -1\) 时，我们要将 \(f(i)\) 转换为 \(1\)。

  4. 我们要求的实际上是 \(f\) 的前缀和，也就是 \(\sum_{i=1}^{n} \mu^2(i)\)，这个和表示的是每个数 \(i\) 是否含有平方因子。我们可以通过枚举所有的平方因子，并对 \(\varepsilon\) 进行一次反演来计算这个和。

具体实现

我们首先对小于 \(n\) 的所有数进行筛选，找出所有的质数，并计算它们的 Möbius 函数值。这可以通过经典的筛法完成。

然后，对于每个完全平方数，我们计算它对答案的贡献，并将这些贡献加起来。具体来说，对于每个完全平方数 \(i\)，它对答案的贡献是 \(\mu(i) \cdot \left\lfloor \frac{n}{i^2} \right\rfloor\)。我们可以通过预处理和整除分块的技术来计算这个和。

我们使用了一个哈希表来存储已经计算出的 Möbius 函数值的和，以避免重复计算。同时，我们利用了整除分块的方法来优化计算过程。

时间复杂度分析

这段代码的主要功能是计算给定的整数 \(n\) 下的 Möbius 函数的前缀和。它使用了线性筛法预处理质数和 Möbius 函数的值，并利用了整除分块的思想和哈希表优化了计算过程。

我们先来分析每个部分的时间复杂度：

  1. 线性筛法：时间复杂度为 \(O(n)\)，其中 \(n\) 是筛选的上界。在这段代码中，筛选的上界是 \(\text{lim} = n^{\frac{2}{5}}\)，所以时间复杂度为 \(O(n^{\frac{2}{5}})\)。

  2. 预处理 Möbius 函数的前缀和：时间复杂度为 \(O(n)\)，在这段代码中，时间复杂度为 \(O(n^{\frac{2}{5}})\)。

  3. 计算 Möbius 函数的前缀和：时间复杂度为 \(O(\sqrt{n} \cdot \log{n})\)，这是因为在最差情况下，每个数 \(i\) 都需要计算 \(\frac n i\) 次，其中 \(i\) 从 \(1\) 到 \(\sqrt{n}\)。这里使用了哈希表来存储已经计算过的 Möbius 函数的前缀和，以避免重复计算。同时，利用了整除分块的思想，对于每个区间 \([l, r]\)，都只需要计算一次 Möbius 函数的前缀和。

  4. 计算结果：时间复杂度为 \(O(\sqrt{n})\)，这个部分主要是对 \(\sqrt{n}\) 的所有整数进行了一次遍历。

因此，总体来看，这段代码的时间复杂度是 \(O(n^{\frac{2}{5}} + \sqrt{n} \cdot \log{n})\)。在实际运行时，由于代码中使用了预处理和整除分块的优化技术，所以运行速度会比这个理论的时间复杂度更快。

Code

我不会数论啊qaq
（先放个代码明天学）

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

constexpr int N = 1e9 + 10, M = 1.6e7;

int lim;

vector<int> pr;
int vis[M], mu[M], Sm1[M];

void sieve(){
    mu[1] = 1;
    for(int i = 2; i <= lim; i++){
        if(!vis[i]) pr.push_back(i), mu[i] = -1;
        for(int j = 0; j < pr.size() && pr[j] * i <= lim; j++){
            vis[pr[j] * i] = 1;
            if(i % pr[j] == 0){
                mu[pr[j] * i] = 0;
                break;
            }
            mu[pr[j] * i] = -mu[i];
        }
    }
    for(int i = 1; i < lim; i++)
        Sm1[i] = Sm1[i - 1] + mu[i];
}

unordered_map<int, int> Sm2;

int Sm(int n){
    if(n <= lim) return Sm1[n];
    auto it = Sm2.find(n);
    if(it != Sm2.end()) return it->second;

    int res = 1;
    for(int l = 2, r; l <= n; l = r + 1){
        r = n / (n / l);
        res -= (r - l + 1) * Sm(n / l);
    }
    return Sm2[n] = res;
}

int main(){
    ios::sync_with_stdio(false); 
    cin.tie(nullptr); cout.tie(nullptr);
    
    ll n; cin >> n;
    lim = powl(n, 2.0 / 5) + 10;
    
    sieve();
    
    ll m = sqrtl(n);

    ll ans = 0, pre = 0, cur;
    for(ll l = 1, r; l <= m; l = r + 1){
        r = sqrtl(n / (n / (l * l)));
        ans += (Sm(r) - Sm(l - 1)) * (n / (l * l));
    }
    cout << ans << "\n";
    return 0;
}

标签：真题,int,ll,我们,蓝桥,复杂度,LCA,省赛,节点
From： https://www.cnblogs.com/CTing/p/17648804.html

相关文章

  • 蓝桥杯Web笔记
    一、node.js1、概念（1）Node.js是一个免费的、开源的、跨平台的JavaScript运行时环境，不是一门语言，也不是一个框架、库，而是一个JavaScript的运行环境。让JavaScript脱离了浏览器，能够允许开发人员在浏览器之外编写命令行工具和服务器端脚本例如：我们常关注的浏览器的兼容性，PC端和手机......
  • P9425 [蓝桥杯 2023 国 B] AB 路线 题解
    ~~应该能过官方数据吧~~---回归正题。我开始想过更简单的深搜，但是我怕无法记忆化，所以选择了广搜。和普通的广搜不同，此题的队列要存$3$个维度，分别是$x$，$y$，$z$，分别表示横坐标、纵坐标、目前的步数模$2k$的值。此时我们可以把每$2k$步进行分组，前$k$步走在```A```的格子......
  • 2020年12月英语六级翻译真题参考答案（3套）
    2020年12月英语六级翻译真题参考答案（3套） 河北文都考研微信公众号：考研EDU 1人赞同了该文章来源：文都教育六级翻译（一）港珠澳大桥（HongKong-Zhuhai-MacauBridge）全长55公里，是我国一项不同寻常的工程壮举。大桥将三个城市连接起来，是世界上最长的跨海桥梁......
  • 【蓝桥杯备赛系列 | 简单题】十六进制转八进制、十六进制转十进制、十进制转十六进制
    ......
  • 每日一练 | 华为认证真题练习Day96
    1、下列协议中属于动态IGP路由协议的是？A.StaticB.BGPC.OSPFD.Direct2、路由器进行数据包转发时需要修改数据包中的目的IP地址。A.对B.错3、route-static10.0.2.2255.255.255.25510.0.12.2preference20，关于此命令说法正确的是？A.该路由一定会出现在路由表当中B.该路由的......
  • 2019考研英语（一）小作文真题解析与参考 Aiding Rural Primary Schools 答复信
    2019考研英语（一）小作文真题解析与参考Directions:Supposeyouareworkingforthe“AidingRuralPrimarySchools” projectofyouruniversity.Writeanemailtoanswertheinquiryfromaninternationalschoolvolunteer,specifyingthedetailsoftheproject.Yous......
  • [蓝桥杯 2021 省 B] 双向排序 (线段树)
    调了整整5个小时,结果发现自己建树的方式有误,气死我了气死我了,比较好的一道线段树(虽然我不会-----#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;intn,m,res,point;vector<int>v[2];//用于存储结果的数组，下标0表示sum为0，下标1表示sum为1structno......
  • 【蓝桥杯备赛系列 | 简单题】数组排序（八大排序演示）
    ......
  • 文都教育：2014年6月英语六级翻译真题及译文
    文都教育：2014年6月英语六级翻译真题及译文 2014年6月英语六级翻译真题及参考译文：中国热词【六级翻译真题原文】中文热词通常反映社会变化和文化，有些在外国媒体上愈来愈流行。例如，土豪和大妈都是老词，但已获取了新的意义。土豪以前指欺压佃户和仆人的乡村地主，现在用于指花钱......
  • ​ 2014年6月大学英语六级​作文真题及参考范文
    ​ 文都教育：6月英语六级作文真题及参考范文 2014年6月大学英语六级考试已经结束，文都教育第一时间为大家提供英语六级作文范，供参考。【六级作文真题】Forthispart,youareallowed30minutestowriteanessayexplainingwhyitisunwisetojudgeaperson......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99