Educational Codeforces Round 165 (Div. 2) A~E

A.Two Friends (思维)

题意：

小 A A A想开一个派对。他有 n n n个朋友，他希望至少有 2 2 2个朋友参加他的派对。
i i i 这个朋友最好的朋友是 p i p_i pi​ 。所有的 p i p_i pi​ 都是不同的，对于每一个 i ∈ [ 1 , n ] i \in [1, n] i∈[1,n] ， p i ≠ i p_i \ne i pi​=i 都是不同的。
小 A A A可以向朋友发出邀请。如果第 i i i 个朋友和第 p i p_i pi​ 个朋友都收到了邀请，那么第 i i i 个朋友就会来参加聚会（注意，第 p i p_i pi​ 个朋友不必真的来参加聚会）。每份邀请函都恰好发给其中一位朋友。
计算至少要发出多少份邀请函，才能让朋友来参加聚会？

分析：

如果有两人互为最好朋友则发两张，否则三张必定能解决。

代码：

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 5;
int a[N];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int flag = 0;
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; i++) {
            if (a[a[i]] == i)
                flag = 1;
        }
        if (flag)
            cout << 2 << endl;
        else
            cout << 3 << endl;
    }
    return 0;
}

B.Shifts and Sorting （思维）

题意：

给定一个只含 01 01 01的二进制序列，每次可选择一段序列将其尾元素移至首位，代价为序列长度，问最少用多少代价可以构造一个非降序序列。

分析：

问题等价于将所有的 0 0 0移到 1 1 1前面，一次最多把一个 0 0 0移到 1 1 1前面对。并且对于一个 0 0 0，最少的操作数一定是前面 1 1 1的个数 + 1 +1 +1。只需要统计前缀的 1 1 1的个数即可。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        LL num = 0;
        LL ans = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '1')
                num++;
            else if (num)
                ans += num + 1;
        }
        cout << ans << endl;
    }
    return 0;
}

C.Minimizing the Sum (dp)

题意：

给你一个长度为 n n n 的整数数组 a a a。可以执行以下操作：选择数组中的一个元素 a i a_i ai​，使得 a i + 1 = a i a_{i+1}=a_i ai+1​=ai​或者 a i − 1 = a i a_{i-1}=a_i ai−1​=ai​。
你的任务是计算执行最多 k k k 次上述操作数组的最小总和。

分析：

d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i个数，执行了 j j j次操作的最小和。从左到右枚举当前最小值的位置 i i i，枚举操作数 x x x，操作是把一个区间的值都变成最小值 a i a_i ai​，区间长度是 x + 1 x+1 x+1，可以直接枚举区间的左边界 l l l ，区间右边界就是 r = l + x r=l+x r=l+x。有转移方程： d p [ r ] [ t + x ] = m i n ( d p [ r ] [ t + x ] , d p [ l − 1 ] [ t ] + ( a [ i ] ∗ ( x + 1 ) ) ) ; dp[r][t+x]=min(dp[r][t+x],dp[l-1][t]+(a[i]*(x+1))); dp[r][t+x]=min(dp[r][t+x],dp[l−1][t]+(a[i]∗(x+1)));。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<LL> a(n + 1), s(n + 1);
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        vector<vector<LL>> dp(n + 1, vector<LL>(k + 1, 1e16));
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int x = 0; x <= k; x++) {
                for (int l = i; l >= i - x && l >= 1; l--) {
                    int r = l + x;
                    if (r > n)
                        continue;
                    for (int t = 0; t <= k - x; t++) {
                        dp[r][t + x] = min(dp[r][t + x], dp[l - 1][t] + (a[i] * (x + 1)));
                    }
                }
            }
        }
        LL ans = 1e16;
        for (int i = 0; i <= k; i++) {
            ans = min(dp[n][i], ans);
        }
        cout << ans << endl;
    }
    return 0;
}

D. Shop Game (贪心)

题意：

总共有 n n n件商品， A l i c e Alice Alice可以用 a i a_i ai​的价格购入， B o b Bob Bob可用 b i b_i bi​的价格从 A l i c e Alice Alice处购买，并且 B o b Bob Bob可以不花钱获得额外的 k k k件物品，询问双方在最优策略下， A l i c e Alice Alice可获得的收益最大为多少。

分析：

我们按照 b i b_i bi​的值从大到小排序。枚举边界 i i i，从 1 − i 1-i 1−i的部分选 k k k个， i + 1 − n i+1-n i+1−n部分任意选择。 1 − i 1-i 1−i部分选的 k k k个一定是这次选择里最大的 k k k个 b b b，这部分选的某个位置对答案的贡献是 − a i -a_i −ai​，将问题转化成选择 k k k个最小的 a i a_i ai​，因此维护一个 a i a_i ai​单调队列。
考虑到 i + 1 − n i+1-n i+1−n部分任意选，由于最大的 k k k个 b b b已经选了，这部分选的某个位置对答案的贡献是 b i − a i b_i-a_i bi​−ai​。因为这部分是任意选的，为了让答案更大，对答案的贡献就是 b i − a i b_i-a_i bi​−ai​结果为正值的和。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n), b(n);
        for (int i = 0; i < n; i++)
            cin >> a[i];
        for (int i = 0; i < n; i++)
            cin >> b[i];
        vector<int> tmp(n);
        iota(tmp.begin(), tmp.end(), 0);
        sort(tmp.begin(), tmp.end(), [&](int x, int y) {
            if (b[x] == b[y]) return a[x] > a[y];
            return b[x] > b[y];
        });
        LL ans = 0;
        LL l = 0, r = 0;
        priority_queue<int> p;
        for (int i = 0; i < k; i++) {
            int j = tmp[i];
            p.push(a[j]);
            l -= a[j];
        }
        for (int i = k; i < n; i++) {
            int j = tmp[i];
            r += max(0, b[j] - a[j]);
        }
        ans = max(ans, l + r);
        for (int i = k; i < n; i++) {
            int j = tmp[i];
            p.push(a[j]);
            l -= a[j];
            l += p.top();
            p.pop();
            r -= max(0, b[j] - a[j]);
            ans = max(ans, l + r);
        }
        cout << ans << endl;
    }
    return 0;
}

E. Unique Array (数据结构)

题意：

给你一个长度为 n n n 的整数数组 a a a 。 如果有一个整数在 a a a的子段中恰好出现一次，那么这个子段就是唯一的。
现在可以执行以下任意次数（可能为零）的操作：从数组中选择一个元素，然后用任意整数替换它。
你的任务是计算上述操作的最少次数，以使数组 a a a 的所有子段都是唯一的。

分析：

首先对于每个位置 a i a_i ai​，找到其前面和后面第一个与之相同的位置记为 p r e i pre_i prei​和 n x t i nxt_i nxti​，那么对于 a i a_i ai​，能使得所有 l ∈ [ p r e i + 1 , i ] , r ∈ [ i , n x t i − 1 ] l \in [pre_i+1,i],r \in [i,nxt_i-1] l∈[prei​+1,i],r∈[i,nxti​−1]的区间都变得符合要求。
这符合二维数点，通过用扫描线找到不满足要求的区间。假设对于每个点 i i i作为右端点时,其最大的不满足要求的左端点为 l i l_i li​。我们可以按照 l i l_i li​排序，然后每次贪心地修改最大的 l i l_i li​，然后记录修改过的最小的为 l i l_i li​为 m i n v a l minval minval，可以发现如果某些 i ≥ m i n v a l i \ge minval i≥minval，那么这个位置也不再需要修改了,可以跳过。可以发现这样是最优的。

代码：

#include <bits/stdc++.h>

using namespace std;
const int mod = 998244353;
const int INF = 1e9;
struct Info {
    int mn = INF, mnnow = 0;
};
using Tag = int;

Info operator+(const Info &a, const Info &b) {
    return a.mn < b.mn ? a : b;
}

void apply(Info &x, Tag &a, Tag f) {
    x.mn += f;
    a += f;
}

template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;

    LazySegmentTree() {}

    LazySegmentTree(int n, Info _init = Info()) {
        init(vector<Info>(n, _init));
    }

    LazySegmentTree(const vector<Info> &_init) {
        init(_init);
    }

    void init(const vector<Info> &_init) {
        n = (int) _init.size();
        info.assign((n << 2) + 1, Info());
        tag.assign((n << 2) + 1, Tag());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = _init[l - 1];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }

    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }

    void apply(int p, const Tag &v) {
        ::apply(info[p], tag[p], v);
    }

    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }

    void change(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x <= m) {
            change(2 * p, l, m, x, v);
        } else {
            change(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }

    void change(int p, const Info &v) {
        change(1, 1, n, p, v);
    }

    Info ask(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return ask(2 * p, l, m, x, y) + ask(2 * p + 1, m + 1, r, x, y);
    }

    Info ask(int l, int r) {
        return ask(1, 1, n, l, r);
    }

    void change(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        change(2 * p, l, m, x, y, v);
        change(2 * p + 1, m + 1, r, x, y, v);
        pull(p);
    }

    void change(int l, int r, const Tag &v) {
        return change(1, 1, n, l, r, v);
    }
};

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> pre(n + 1), nxt(n + 1);
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        {
            vector<int> last(n + 1);
            for (int i = 1; i <= n; i++) {
                pre[i] = last[a[i]];
                last[a[i]] = i;
            }
        }
        {
            vector<int> last(n + 1, n + 1);
            for (int i = n; i >= 1; i--) {
                nxt[i] = last[a[i]];
                last[a[i]] = i;
            }
        }
        vector<vector<pair<int, int>>> now(n + 1);
        for (int i = 1; i <= n; i++) {
            now[nxt[i] - 1].push_back({i, 1});
            now[i - 1].push_back({i, 0});
        }
        vector<Info> init(n);
        for (int i = 0; i < n; i++) {
            init[i] = {0, i + 1};
        }
        LazySegmentTree<Info, Tag> seg(init);
        set<pair<int, int>> s;
        for (int i = n; i >= 1; i--) {
            for (auto [x, type]: now[i]) {
                if (type) {
                    seg.change(pre[x] + 1, x, 1);
                } else {
                    seg.change(pre[x] + 1, x, -1);
                }
            }
            auto [mn, mnnow] = seg.ask(1, i);
            if (mn == 0) {
                s.insert({mnnow, i});
            }
        }
        int ans = 0;
        int tmp = n + 1;
        while (!s.empty()) {
            if (prev(s.end())->second >= tmp) {
                s.erase(prev(s.end()));
            } else {
                ans += 1;
                tmp = prev(s.end())->first;
                s.erase(prev(s.end()));
            }
        }
        cout << ans << endl;
    }
    return 0;
}

赛后交流

在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。

群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/603712.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

C++之泛型编程---有限双端队列结构容器

C++之泛型编程---有限双端队列结构容器

引言 为了解决工业领域代码容器的通用化&#xff0c;可以考虑C里的泛型编程概念。假设一个场景需要实时保存最近的n个数据并按照顺序依次处理时&#xff0c;就需要定义一种新的容器来满足要求。当容器不满时&#xff0c;添加数据直接到队尾&#xff0c;当容器数据已经为n个时&a…
阅读更多...
毕设UI设计不会前端怎么办？今天看到了一款自动生成UI的项目-OpenUI

毕设UI设计不会前端怎么办？今天看到了一款自动生成UI的项目-OpenUI

试用地址&#xff1a;Create a new Elemint (openui.fly.dev) OpenUI 是由 W&B 开发开源项目&#xff0c;旨在简化用户界面(UI)组件的构建过程。它通过允许开发者使用想象力描述 UI&#xff0c;然后实时看到渲染效果&#xff0c;使得 UI 开发变得有趣、快速且灵活。 这个…
阅读更多...
CSS-盒子模型元素溢出

CSS-盒子模型元素溢出

作用&#xff1a;控制溢出的元素的内容的显示方式 属性&#xff1a;overflow 属性值 属性值效果hidden溢出隐藏scroll溢出滚动&#xff08;无论是否溢出&#xff0c;都显示滚动条位置&#xff09;auto溢出滚动&#xff08;溢出才显示滚动条位置&#xff09; <!DOCTYPE html&…
阅读更多...
npm无法安装node-sass 的问题

npm无法安装node-sass 的问题

安装 node-sass 的问题呈现&#xff1a;4.9.0版本无法下载 Downloading binary from https://github.com/sass/node-sass/releases/download/v4.9.0/win32-x64-72_binding.node Cannot download "https://github.com/sass/node-sass/releases/download/v4.9.0/win32-x64-…
阅读更多...
Pytorch学习笔记——卷积操作

Pytorch学习笔记——卷积操作

一、认识卷积操作 卷积操作是一种数学运算&#xff0c;它涉及两个函数&#xff1a;输入函数&#xff08;通常是图像&#xff09;和卷积核&#xff08;也称为滤波器或特征检测器&#xff09;。卷积核在输入函数上滑动&#xff0c;将核中的每个元素与其覆盖的输入函数区域中的对应…
阅读更多...
华为数据之道第四部分导读

华为数据之道第四部分导读

目录 导读 第四部分 第10章 未来已来&#xff1a;数据成为企业核心竞争力 数据&#xff1a;新的生产要素 数据被列为生产要素&#xff1a;制度层面的肯定 数据将进入企业的资产负债表 数据资产的价值由市场决定 大规模数据交互的企业数据生态 数据生态离不开底层技术的…
阅读更多...
618大促买什么数码好物最划算？必囤不后悔好物清单来了！

618大促买什么数码好物最划算？必囤不后悔好物清单来了！

随着年度618购物盛宴的临近&#xff0c;作为数码领域的资深狂热者&#xff0c;满怀激情与憧憬为大家精心挑选了一系列令人瞩目的数码产品。无论你是热衷于追逐最新科技潮流的先锋&#xff0c;还是期望通过数码设备提升生活品质的优雅用户&#xff0c;这里都定有一款能触动你内心…
阅读更多...
(动画详解)LeetCode20.有效的括号

(动画详解)LeetCode20.有效的括号

题目描述 20. 有效的括号 - 力扣&#xff08;LeetCode&#xff09; 解题思路 栈的方法 遍历整个字符串 当检测到左括号的时候&#xff0c;就让左括号入栈 当检测到右括号的时候&#xff0c;就让左括号出栈与右括号对比 如果相等则继续比较直到结束&#xff0c;如果不相等…
阅读更多...
在Linux中安装Docker

在Linux中安装Docker

如果之前安装过旧版本的 Docker&#xff0c;可以使用下面命令卸载&#xff1a; yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-selinux \docker-engine-selinux \docker-engine…
阅读更多...
[华为OD]C卷 BFS 亲子游戏 200

[华为OD]C卷 BFS 亲子游戏 200

题目&#xff1a; 宝宝和妈妈参加亲子游戏&#xff0c;在一个二维矩阵&#xff08;N*N&#xff09;的格子地图上&#xff0c;宝宝和妈妈抽签决定各自 的位置&#xff0c;地图上每个格子有不同的Q糖果数量&#xff0c;部分格子有障碍物。 游戏规则Q是妈妈必须在最短的时间&a…
阅读更多...
我独自升级崛起账号注册 我独自升级怎么注册账号

我独自升级崛起账号注册 我独自升级怎么注册账号

近期&#xff0c;《我独自升级》这部动画凭借爆棚的人气&#xff0c;在各大平台上掀起了一阵观看热潮&#xff0c;其影响力不容小觑。借此时机&#xff0c;韩国游戏巨头网石集团敏捷响应&#xff0c;顺势推出了同名游戏《我独自升级&#xff1a;ARISE》&#xff0c;为粉丝们搭建…
阅读更多...
淘宝/天猫商品描述API（taobao.item_get_desc）返回值详解

淘宝/天猫商品描述API（taobao.item_get_desc）返回值详解

淘宝/天猫的商品描述API&#xff08;taobao.item_get_desc&#xff09;允许开发者获取指定商品的详细描述信息。这对于需要进行商品数据分析、构建商品详情页面或进行其他与商品相关的应用开发非常有用。下面&#xff0c;我们将详细解析这个API的返回值。 一、API概述 taobao.…
阅读更多...
接收区块链的CCF会议--NDSS 2025 截止7.10 附录用率

接收区块链的CCF会议--NDSS 2025 截止7.10 附录用率

会议名称&#xff1a;Network and Distributed System Security Symposium (NDSS) CCF等级&#xff1a;CCF A类学术会议 类别&#xff1a;网络与信息安全 录用率&#xff1a;2024年接收率19.5% Submissions are solicited in, but not limited to, the following areas: Ant…
阅读更多...
【Qt】掌握Qt界面开发：窗口属性与资源嵌入技巧解析

【Qt】掌握Qt界面开发：窗口属性与资源嵌入技巧解析

文章目录 前言&#xff1a;1. windowTitle: 窗口标题2. windowIcon&#xff1a;窗口图标3. qrc 机制&#xff1a;4. windowOpacity&#xff1a;半透明效果总结&#xff1a; 前言&#xff1a; 在软件开发中&#xff0c;用户界面&#xff08;UI&#xff09;的构建是一个重要环节…
阅读更多...
Deepsort算法研究

Deepsort算法研究

目录 1. 基于检测的多目标跟踪策略 1.1 多目标跟踪任务模型 1.2 多目标跟踪算法 SORT 1.3 DeepSORT 算法 2 . 基于轨迹的学生行为分类模型 2.1 学生行为分类规则 2.2 实际场景分析 1. 基于检测的多目标跟踪策略 多目标跟踪任务涉及跟踪多个目标的身份信息关联&#x…
阅读更多...
C++类和对象（基础篇）

C++类和对象（基础篇）

前言&#xff1a; 其实任何东西&#xff0c;只要你想学&#xff0c;没人能挡得住你&#xff0c;而且其实学的也很快。那么本篇开始学习类和对象&#xff08;C的&#xff0c;由于作者有Java基础&#xff0c;可能有些东西过得很快&#xff09;。 struct在C中的含义&#xff1a; …
阅读更多...
组件通信-props详解

组件通信-props详解

目录 一、什么是prop 二、props校验 三、组件中prop和data的区别 一、什么是prop Prop定义&#xff1a;组件上注册的一些自定义属性。 Prop作用&#xff1a;向子组件传递数据。 特点&#xff1a; 可以传递任意数量的prop可以传递任意类型的prop 二、props校验 组件的pr…
阅读更多...
智能化采购管理系统助力光伏行业提高效率

智能化采购管理系统助力光伏行业提高效率

光伏行业是指太阳能电池板的制造、安装和维护等相关产业&#xff0c;是新能源领域的重要组成部分。近年来&#xff0c;随着全球对于环保和可持续发展的重视&#xff0c;光伏行业进入全球化和智能化的新阶段。光伏企业开始加强国际合作&#xff0c;推广智能化技术&#xff0c;提…
阅读更多...
数据结构学习/复习11--二叉树分治与递归思想练习题

数据结构学习/复习11--二叉树分治与递归思想练习题

一、二叉树相关练习题 1.判断单值二叉树 2. 判断两颗树是否相同 3.先序遍历的实现 注意事项&#xff1a;此处中的数组的下标用指针控制&#xff0c;因为受到递归与函数栈帧创建与销毁的影响。最后的返回值是指向前序遍历排好后的数组指针 4.判断一棵树是否是另一棵树的子树 …
阅读更多...
速来get！多微信聚合聊天功能大揭秘！

速来get！多微信聚合聊天功能大揭秘！

随着网络时代的发展&#xff0c;微信成为了职场中不可或缺的沟通工具&#xff0c;很多人都有着多个微信号&#xff0c;而要想高效管理这些账号&#xff0c;那就少不了工具的帮忙。 通过微信管理系统&#xff0c;可以轻松实现多个微信号聚合聊天&#xff0c;提高沟通效率。 1、…
阅读更多...
最新文章

Copyright @ 2022~2023